Recently the paper Quantum Search for Scaled Hash Function Preimages has been published in arXiv as a preprint. This is a joint work of S. Ramos-Calderer, E. Bellini, J. I. Latorre, Marc Manzano and Victor Mateu
We provide an explicit implementation of Grover’s algorithm for a search of preimages of Scaled down Hash functions. This allows for a thorough understanding of the scaling and difficulties when addressing particular hash constructions.
Hash primitives based on Addition Rotation and Exclusive OR (ARX) operations are easier to attack due to their easier mapping to a quantum circuit, while AND and OR gates need extra quantum resources.
An entanglement entropy analysis during the application of Grover’s algorithm reveals that maximum entanglement is reached during the first application of the Grover oracle, which implies that no classical simulation based on Tensor Networks would be of relevance.