Estimating Quantum Speedups for Lattice Sieves
| العنوان: | Estimating Quantum Speedups for Lattice Sieves |
|---|---|
| المؤلفون: | Vlad Gheorghiu, Martin R. Albrecht, Eamonn W. Postlethwaite, John M. Schanck |
| المصدر: | Advances in Cryptology – ASIACRYPT 2020 ISBN: 9783030648336 ASIACRYPT (2) Lecture Notes in Computer Science Lecture Notes in Computer Science-Advances in Cryptology – ASIACRYPT 2020 Advances in Cryptology – ASIACRYPT 2020-26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part II |
| بيانات النشر: | Springer International Publishing, 2020. |
| سنة النشر: | 2020 |
| مصطلحات موضوعية: | Speedup, business.industry, Computer science, Cryptography, 02 engineering and technology, 01 natural sciences, 020202 computer hardware & architecture, law.invention, Sieve, Software, law, Search algorithm, Lattice (order), 0103 physical sciences, 0202 electrical engineering, electronic engineering, information engineering, 010306 general physics, business, Algorithm, Quantum, Electronic circuit |
| الوصف: | Quantum variants of lattice sieve algorithms are routinely used to assess the security of lattice based cryptographic constructions. In this work we provide a heuristic, non-asymptotic, analysis of the cost of several algorithms for near neighbour search on high dimensional spheres. These algorithms are key components of lattice sieves. We design quantum circuits for near neighbour search algorithms and provide software that numerically optimises algorithm parameters according to various cost metrics. Using this software we estimate the cost of classical and quantum near neighbour search on spheres. For the most performant near neighbour search algorithm that we analyse we find a small quantum speedup in dimensions of cryptanalytic interest. Achieving this speedup requires several optimistic physical and algorithmic assumptions. |
| ردمك: | 978-3-030-64833-6 978-3-030-64834-3 |
| تدمد: | 0302-9743 1611-3349 |
| DOI: | 10.1007/978-3-030-64834-3_20 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::94bf7a93807afb58072b521b4483e1b2 https://doi.org/10.1007/978-3-030-64834-3_20 |
| Rights: | CLOSED |
| رقم الانضمام: | edsair.doi.dedup.....94bf7a93807afb58072b521b4483e1b2 |
| قاعدة البيانات: | OpenAIRE |
| ردمك: | 9783030648336 9783030648343 |
|---|---|
| تدمد: | 03029743 16113349 |
| DOI: | 10.1007/978-3-030-64834-3_20 |