Applying Grover's Algorithm to Hash Functions: A Software Perspective
Richard H. Preston
Abstract
Quantum software frameworks provide software engineers with the tools to study quantum algorithms as applied to practical problems. We implement classical hash functions MD5, SHA-1, SHA-2, and SHA-3 as quantum oracles to study the computational resource requirements of conducting a preimage attack with Grover's Algorithm. We introduce an improvement to the SHA-3 oracle that reduces the number of logical qubits required in the Keccak block permutation by 40%. The source code is available at <uri xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">https://github.com/rhpreston/grovers-hash-functions</uri> .
Topics & Concepts
Hash functionComputer scienceOracleSHA-2Theoretical computer scienceCryptographic hash functionSoftwarePermutation (music)AlgorithmSecure Hash AlgorithmQuantum algorithmMD5QuantumCollision resistanceDouble hashingProgramming languageQuantum mechanicsPhysicsAcousticsQuantum Computing Algorithms and ArchitectureQuantum Information and CryptographyCryptographic Implementations and Security