تقرير
Quantum Lattice Sieving
| العنوان: | Quantum Lattice Sieving |
|---|---|
| المؤلفون: | Rodrigues, Nishant, Lackey, Brad |
| سنة النشر: | 2021 |
| المجموعة: | Quantum Physics |
| مصطلحات موضوعية: | Quantum Physics |
| الوصف: | Lattices are very important objects in the effort to construct cryptographic primitives that are secure against quantum attacks. A central problem in the study of lattices is that of finding the shortest non-zero vector in the lattice. Asymptotically, sieving is the best known technique for solving the shortest vector problem, however, sieving requires memory exponential in the dimension of the lattice. As a consequence, enumeration algorithms are often used in place of sieving due to their linear memory complexity, despite their super-exponential runtime. In this work, we present a heuristic quantum sieving algorithm that has memory complexity polynomial in the size of the length of the sampled vectors at the initial step of the sieve. In other words, unlike most sieving algorithms, the memory complexity of our algorithm does not depend on the number of sampled vectors at the initial step of the sieve. Comment: A reviewer pointed out an error in the amplitude amplification step in the analysis of Theorem 6. While we believe this error can be resolved, we are not sure how to do it at the moment and are taking down this submission |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2110.13352 |
| رقم الأكسشن: | edsarx.2110.13352 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |