15 citations · 36 across the 9 of their papers we have counts for
10 papers
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…
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…
Finding many Collisions via Reusable Quantum Walks
Xavier Bonnetain, André Chailloux, André Schrottenloher +1
Given a random function with domain and codomain , with , a collision of is a pair of distinct inputs with the same image. Collision finding is an…
Quantum Augmented Dual Attack
Martin R. Albrecht, Yixin Shen
We present a quantum augmented variant of the dual lattice attack on the Learning with Errors (LWE) problem, using classical memory with quantum random access (QRACM). Applying our…
Variational quantum solutions to the Shortest Vector Problem
Martin R. Albrecht, Miloš Prokop, Yixin Shen +1
A fundamental computational problem is to find a shortest non-zero vector in Euclidean lattices, a problem known as the Shortest Vector Problem (SVP). This problem is believed to b…
Fast Classical and Quantum Algorithms for Online -server Problem on Trees
Ruslan Kapralov, Kamil Khadiev, Joshua Mokut +2
We consider online algorithms for the -server problem on trees. Chrobak and Larmore proposed a -competitive algorithm for this problem that has the optimal competitive ratio.…
Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
Andris Ambainis, Kaspars Balodis, Jānis Iraids +6
We study the quantum query complexity of two problems. First, we consider the problem of determining if a sequence of parentheses is a properly balanced one (a Dyck word), with a d…
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…
Improved Classical and Quantum Algorithms for Subset-Sum
Xavier Bonnetain, Rémi Bricout, André Schrottenloher +1
We present new classical and quantum algorithms for solving random subset-sum instances. First, we improve over the Becker-Coron-Joux algorithm (EUROCRYPT 2011) from $\tilde{\mathc…
Quantum Query Complexity of Dyck Languages with Bounded Height
Kamil Khadiev, Yixin Shen
We consider the problem of determining if a sequence of parentheses is well parenthesized, with a depth of at most h. We denote this language as . We study the quantum quer…