3 papers
quant-ph2025
A Tight Quantum Algorithm for Multiple Collision Search
Xavier Bonnetain, Johanna Loyer, André Schrottenloher +1
Searching for collisions in random functions is a fundamental computational problem, with many applications in symmetric and asymmetric cryptanalysis. When one searches for a singl…
cs.DS2025
Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding
Divesh Aggarwal, Yanlin Chen, Rajendra Kumar +1
The most important computational problem on lattices is the Shortest Vector Problem (SVP). In this paper, we present new algorithms that improve the state-of-the-art for provable c…
quant-ph2024
Does quantum lattice sieving require quantum RAM?
Beomgeun Cho, Minki Hhan, Taehyun Kim +2
In this paper, we study the requirement for quantum random access memory (QRAM) in quantum lattice sieving, a fundamental algorithm for lattice-based cryptanalysis. First, we obtai…