Finding many collisions via reusable quantum walks. Application to lattice sieving

DOI10.1007/978-3-031-30589-4_8arXiv2205.14023OpenAlexW4365936110MaRDI QIDQ6083662

André Chailloux, Yixin Shen, André Schrottenloher, Xavier Bonnetain

Publication date: 8 December 2023

Published in: Advances in Cryptology – EUROCRYPT 2023 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2205.14023

zbMATH Keywords

quantum algorithmsquantum walkslattice sievingcollision search

Mathematics Subject Classification ID

Search theory (90B40) Quantum computation (81P68) Cryptography (94A60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) (2)-body potential quantum scattering theory (81U05) Applications of sieve methods (11N36) Quantum coding (general) (81P70) Quantum cryptography (quantum-theoretic aspects) (81P94) Anomalous diffusion models (subdiffusion, superdiffusion, continuous-time random walks, etc.) (60K50)

Related Items (1)

Quantum time/memory/data tradeoff attacks

Cites Work

• Low-gate quantum golden collision finding
• A hierarchy of polynomial time lattice basis reduction algorithms
• Parallel collision search with cryptanalytic applications
• Quantum information set decoding algorithms
• An efficient quantum collision search algorithm and implications on symmetric cryptography
• Quantum algorithm for the multicollision problem
• Tight time-space lower bounds for finding multiple collision pairs and their applications
• Quantum cryptanalysis in the RAM model: claw-finding attacks on SIKE
• Quantum algorithms for the approximate \(k\)-list problem and their application to lattice sieving
• On finding quantum multi-collisions
• Improved quantum multicollision-finding algorithm
• Improved classical and quantum algorithms for subset-sum
• Breaking Symmetric Cryptosystems Using Quantum Period Finding
• Scrutinizing and Improving Impossible Differential Attacks: Applications to CLEFIA, Camellia, LBlock and Simon
• Search via Quantum Walk
• Quantum lower bounds for the collision and the element distinctness problems
• Quantum Algorithms for the Subset-Sum Problem
• Quantum Walk Algorithm for Element Distinctness
• Quantum cryptanalysis of hash and claw-free functions
• Lattice Sieving via Quantum Random Walks
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Finding many collisions via reusable quantum walks. Application to lattice sieving