Low-gate quantum golden collision finding

DOI10.1007/978-3-030-81652-0_13zbMATH Open1487.81067OpenAlexW3111500848MaRDI QIDQ832353FDOQ832353

Authors Samuel Jaques, André Schrottenloher

Publication date 25 March 2022

Full work available at URL https://doi.org/10.1007/978-3-030-81652-0_13

zbMATH Keywords

quantum walksquantum cryptanalysisgolden collision searchSIKE

Mathematics Subject Classification ID

Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) Cryptography (94A60) Quantum coding (general) (81P70) Quantum cryptography (quantum-theoretic aspects) (81P94) Collisions in celestial mechanics, regularization (70F16) Computer security (68M25)

Recommendations

• An efficient quantum collision search algorithm and implications on symmetric cryptography
• Quantum collision-finding in non-uniform random functions
• Quantum multicollision-finding algorithm
• Quantum lower bounds for the collision and the element distinctness problems
• Quantum algorithm for the multicollision problem

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 16479 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
• A framework for reducing the overhead of the quantum oracle for use with Grover's algorithm with applications to cryptanalysis of SIKE
• An Improved Claw Finding Algorithm Using Quantum Walk
• An efficient quantum collision search algorithm and implications on symmetric cryptography
• Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• Applying Grover's algorithm to AES: quantum resource estimates
• Efficient distributed quantum computing
• Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3
• Implementing Grover oracles for quantum key search on AES and LowMC
• Improved classical cryptanalysis of SIKE in practice
• Low-communication parallel quantum multi-target preimage search
• Lower bounds for sorting on mesh-connected architectures
• On the concrete hardness of learning with errors
• On the cost of computing isogenies between supersingular elliptic curves
• On the height of trees
• On the robustness of bucket brigade quantum RAM
• Optimal merging in quantum \(k\)-xor and \(k\)-sum algorithms
• Parallel collision search with cryptanalytic applications
• Quantum Algorithms for Element Distinctness
• Quantum Walk Algorithm for Element Distinctness
• Quantum cryptanalysis in the RAM model: claw-finding attacks on SIKE
• Quantum cryptanalysis of hash and claw-free functions
• Quantum lower bounds for the collision and the element distinctness problems
• Search via Quantum Walk
• Time/Space Trade-Offs for Reversible Computation

Cited in

(6)

• Finding many collisions via reusable quantum walks. Application to lattice sieving
• Breaking the Quadratic Barrier: Quantum Cryptanalysis of Milenage, Telecommunications’ Cryptographic Backbone
• On the security of OSIDH
• A new adaptive attack on SIDH
• Quantum attacks on hash constructions with low quantum random access memory
• An efficient quantum collision search algorithm and implications on symmetric cryptography

This page was built for publication: Low-gate quantum golden collision finding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q832353)