The DOI matches its Crossref record; 58 of the 58 references it cites were found in a registry or an index.
Frodo: Take off the Ring! Practical, Quantum-Secure Key Exchange from LWE
Open accessAbstract
Lattice-based cryptography offers some of the most attractive primitives believed to be resistant to quantum computers. Following increasing interest from both companies and government agencies in building quantum computers, a number of works have proposed instantiations of practical post-quantum key exchange protocols based on hard problems in ideal lattices, mainly based on the Ring Learning With Errors (R-LWE) problem. While ideal lattices facilitate major efficiency and storage benefits over their non-ideal counterparts, the additional ring structure that enables these advantages also raises concerns about the assumed difficulty of the underlying problems. Thus, a question of significant interest to cryptographers, and especially to those currently placing bets on primitives that will withstand quantum adversaries, is how much of an advantage the additional ring structure actually gives in practice. Despite conventional wisdom that generic lattices might be too slow and unwieldy, we demonstrate that LWE-based key exchange is quite practical: our constant time implementation requires around 1.3ms computation time for each party; compared to the recent NewHope R-LWE scheme, communication sizes increase by a factor of 4.7x, but remain under 12 KiB in each direction. Our protocol is competitive when used for serving web pages over TLS; when partnered with ECDSA signatures, latencies increase by less than a factor of 1.6x, and (even under heavy load) server throughput only decreases by factors of 1.5x and 1.2x when serving typical 1 KiB and 100 KiB pages, respectively. To achieve these practical results, our protocol takes advantage of several innovations. These include techniques to optimize communication bandwidth, dynamic generation of public parameters (which also offers additional security against backdoors), carefully chosen error distributions, and tight security parameters.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Gaussian elimination is not optimal
Strassen, V. (1969) · Numerische Mathematik · doi:10.1007/bf02165411 · Cited by 2,509 · cited 1×
“We make this choice because our matrix dimensions are not large enough for the asymptotically faster methods [61, 23] to offer a worthwhile trade-off (see [25]).”
BackgroundTrapdoors for hard lattices and new cryptographic constructions
Gentry, C., Peikert, C., & Vaikuntanathan, V. (2008) · Proceedings of the fortieth annual ACM symposium on Theory of computing · doi:10.1145/1374376.1374407 · Cited by 2,435
On lattices, learning with errors, random linear codes, and cryptography
Regev, O. (2009) · Journal of the ACM · doi:10.1145/1568318.1568324 · Cited by 2,315
On lattices, learning with errors, random linear codes, and cryptography
Regev, O. (2005) · Proceedings of the thirty-seventh annual ACM symposium on Theory of computing · doi:10.1145/1060590.1060603 · Cited by 2,313
Superconducting Circuits for Quantum Information: An Outlook
Devoret, M. H., & Schoelkopf, R. J. (2013) · Science · doi:10.1126/science.1231930 · Cited by 2,114
NTRU: A ring-based public key cryptosystem
Hoffstein, J., Pipher, J., & Silverman, J. H. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0054868 · Cited by 1,947
Efficient Fully Homomorphic Encryption from (Standard) LWE
Brakerski, Z., & Vaikuntanathan, V. (2011) · 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2011.12 · Cited by 1,449
Generating hard instances of lattice problems (extended abstract)
Ajtai, M. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237838 · Cited by 1,405
Authentication and authenticated key exchanges
Diffie, W., Van Oorschot, P. C., & Wiener, M. J. (1992) · Designs, Codes and Cryptography · doi:10.1007/bf00124891 · Cited by 1,154
Secure Integration of Asymmetric and Symmetric Encryption Schemes
Fujisaki, E., & Okamoto, T. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48405-1_34 · Cited by 1,132
Report on Post-Quantum Cryptography
Chen, L., Jordan, S., Liu, Y.-K., Moody, D., Peralta, R., Perlner, R., & Smith-Tone, D. (2016) · doi:10.6028/nist.ir.8105 · Cited by 1,034
A close examination of performance and power characteristics of 4G LTE networks
Huang, J., Qian, F., Gerber, A., Mao, Z. M., Sen, S., & Spatscheck, O. (2012) · Proceedings of the 10th international conference on Mobile systems, applications, and services · doi:10.1145/2307636.2307658 · Cited by 995
Efficient Lattice (H)IBE in the Standard Model
Agrawal, S., Boneh, D., & Boyen, X. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-13190-5_28 · Cited by 976
State preservation by repetitive error detection in a superconducting quantum circuit
Kelly, J., Barends, R., Fowler, A. G., Megrant, A., Jeffrey, E., White, T. C., Sank, D., Mutus, J. Y., Campbell, B., Chen, Y., et al. (2015) · Nature · doi:10.1038/nature14270 · Cited by 916
On the concrete hardness of Learning with Errors
Albrecht, M. R., Player, R., & Scott, S. (2015) · Journal of Mathematical Cryptology · doi:10.1515/jmc-2015-0016 · Cited by 861
On Ideal Lattices and Learning with Errors over Rings
Lyubashevsky, V., Peikert, C., & Regev, O. (2013) · Journal of the ACM · doi:10.1145/2535925 · Cited by 836
Public-key cryptosystems from the worst-case shortest vector problem: extended abstract
Peikert, C. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536461 · Cited by 813
Better Key Sizes (and Attacks) for LWE-Based Encryption
Lindner, R., & Peikert, C. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-19074-2_21 · Cited by 688
Matrix multiplication via arithmetic progressions
Coppersmith, D., & Winograd, S. (1987) · Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC '87 · doi:10.1145/28395.28396 · Cited by 632
Classical hardness of learning with errors
Brakerski, Z., Langlois, A., Peikert, C., Regev, O., & Stehlé, D. (2013) · Proceedings of the forty-fifth annual ACM symposium on Theory of Computing · doi:10.1145/2488608.2488680 · Cited by 627
BKZ 2.0: Better Lattice Security Estimates
Chen, Y., & Nguyen, P. Q. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-25385-0_1 · Cited by 598
Post-quantum key exchange - a new hope.Preprint
Alkım, E., Ducas, L., Pöppelmann, T., & Schwabe, P. (2015) · IACR Cryptology ePrint Archive · Cited by 586
Self-citationFast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems
Applebaum, B., Cash, D., Peikert, C., & Sahai, A. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-03356-8_35 · Cited by 562
A Remark Concerning m-Divisibility and the Discrete Logarithm in the Divisor Class Group of Curves
Frey, G., & Ruck, H.-G. (1994) · Mathematics of Computation · doi:10.2307/2153546 · Cited by 551
Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$
Brakerski, Z., & Vaikuntanathan, V. (2014) · SIAM Journal on Computing · doi:10.1137/120868669 · Cited by 538
A Decade of Lattice Cryptography
Peikert, C. (2016) · Foundations and TrendsŴ in Theoretical Computer Science · doi:10.1561/0400000074 · Cited by 504
Shor's discrete logarithm quantum algorithm for elliptic curves
Proos, J., & Zalka, C. (2003) · Quantum Information and Computation · doi:10.26421/qic3.4-3 · Cited by 421
Lattice Basis Delegation in Fixed Dimension and Shorter-Ciphertext Hierarchical IBE
Agrawal, S., Boneh, D., & Boyen, X. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-14623-7_6 · Cited by 416
Recommendation for Key Management Part 1: General
Barker, E. (2016) · doi:10.6028/nist.sp.800-57pt1r4 · Cited by 396
Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice
Adrian, D., Bhargavan, K., Durumeric, Z., Gaudry, P., Green, M., Halderman, J. A., Heninger, N., Springall, D., Thomé, E., Valenta, L., et al. (2015) · Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2810103.2813707 · Cited by 348
Reducing elliptic curve logarithms to logarithms in a finite field
Menezes, A., Vanstone, S., & Okamoto, T. (1991) · Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC '91 · doi:10.1145/103418.103434 · Cited by 337
Post-Quantum Key Exchange for the TLS Protocol from the Ring Learning with Errors Problem
Bos, J. W., Costello, C., Naehrig, M., & Stebila, D. (2015) · 2015 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2015.40 · Cited by 329
Self-citationA Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem.Preprint
Ding, J. (2012) · IACR Cryptology ePrint Archive · Cited by 328
Hardness of SIS and LWE with Small Parameters
Micciancio, D., & Peikert, C. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-40041-4_2 · Cited by 299
Bonsai Trees, or How to Delegate a Lattice Basis
Cash, D., Hofheinz, D., Kiltz, E., & Peikert, C. (2012) · Journal of Cryptology · doi:10.1007/s00145-011-9105-2 · Cited by 297
New directions in nearest neighbor searching with applications to lattice sieving
Becker, A., Ducas, L., Gama, N., & Laarhoven, T. (2016) · Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms · doi:10.1137/1.9781611974331.ch2 · Cited by 287
Self-citationLattice Enumeration Using Extreme Pruning
Gama, N., Nguyen, P. Q., & Regev, O. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-13190-5_13 · Cited by 284
Speeding up the Number Theoretic Transform for Faster Ideal Lattice-Based Cryptography
Longa, P., & Naehrig, M. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-48965-0_8 · Cited by 268
Self-citationA Decade of Lattice Cryptography
Peikert, C. (2016) · now publishers, Inc. eBooks · doi:10.1561/9781680831139 · Cited by 256
New Algorithms for Learning in Presence of Errors
Arora, S., & Ge, R. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-22006-7_34 · Cited by 243
Efficient Algorithms for Supersingular Isogeny Diffie-Hellman
Costello, C., Longa, P., & Naehrig, M. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-53018-4_21 · Cited by 230
Self-citationOn the Security of the TLS Protocol: A Systematic Analysis
Krawczyk, H., Paterson, K. G., & Wee, H. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-40041-4_24 · Cited by 215
On the Security of TLS-DHE in the Standard Model
Jager, T., Kohlar, F., Schäge, S., & Schwenk, J. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-32009-5_17 · Cited by 211
Who killed my battery?: analyzing mobile browser energy consumption
Thiagarajan, N., Aggarwal, G., Nicoara, A., Boneh, D., & Singh, J. P. (2012) · Proceedings of the 21st international conference on World Wide Web · doi:10.1145/2187836.2187843 · Cited by 189
Authenticated Key Exchange from Ideal Lattices
Zhang, J., Zhang, Z., Ding, J., Snook, M., & Dagdelen, Ö. (2015) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-46803-6_24 · Cited by 177
Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing
Laarhoven, T. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-47989-6_1 · Cited by 171
McBits: Fast Constant-Time Code-Based Cryptography
Bernstein, D. J., Chou, T., & Schwabe, P. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40349-1_15 · Cited by 158
Recommendation for key management, part 1: general (revision 3)
Barker, E. B., Barker, W. C., Burr, W. E., Polk, W. T., & Smid, M. E. (2012) · doi:10.6028/nist.sp.800-57p1r3 · Cited by 120
An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices
Kirchner, P., & Fouque, P.-A. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-47989-6_3 · Cited by 109
Bai, S., Roux-Langlois, A., Lepoint, T., Stehlé, D., & Steinfeld, R. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-48797-6_1 · Cited by 102
How (Not) to Instantiate Ring-LWE
Peikert, C. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-44618-9_22 · Cited by 90
Sieving for Shortest Vectors in Ideal Lattices
Schneider, M. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38553-7_22 · Cited by 33
Sieving for shortest vectors in ideal lattices: a practical perspective
Bos, J. W., Naehrig, M., & van de Pol, J. (2017) · International Journal of Applied Cryptography · doi:10.1504/ijact.2017.089353 · Cited by 24
Self-citationD’Alberto, P., & Nicolau, A. (2005) · International Conference on High Performance Computing in Asia-Pacific Region (HPC Asia) · doi:10.1109/hpcasia.2005.18 · Cited by 15
Albrecht, M. R., Faugère, J., Farshim, P., Herold, G., & Perret, L. (2015) · Designs Codes and Cryptography · doi:10.1007/s10623-015-0048-8 · Cited by 11
Shor's discrete logarithm quantum algorithm for elliptic curves
ProosJohn, & ZalkaChristof (2003) · Quantum Information and Computation · doi:10.5555/2011528.2011531 · Cited by 6
Cited by
CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM
Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J. M., Schwabe, P., Seiler, G., & Stehle, D. (2018) · 2018 IEEE European Symposium on Security and Privacy (EuroS&P) · doi:10.1109/eurosp.2018.00032 · Cited by 1,192
Self-citationFernandez-Carames, T. M., & Fraga-Lamas, P. (2020) · IEEE Access · doi:10.1109/access.2020.2968985 · Cited by 607
A Modular Analysis of the Fujisaki-Okamoto Transformation
Hofheinz, D., Hövelmanns, K., & Kiltz, E. (2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-70500-2_12 · Cited by 451
Status report on the third round of the NIST Post-Quantum Cryptography Standardization process
Alagic, G., Apon, D., Cooper, D., Dang, Q., Dang, T., Kelsey, J., Lichtinger, J., Liu, Y.-K., Miller, C., Moody, D., et al. (2022) · doi:10.6028/nist.ir.8413 · Cited by 395
Fernandez-Carames, T. M. (2020) · IEEE Internet of Things Journal · doi:10.1109/jiot.2019.2958788 · Cited by 317
Metadata
- Authors
- Bos, J., Costello, C., Ducas, L., Mironov, I., Naehrig, M., Nikolaenko, V., Raghunathan, A., & Stebila, D.
- Venue
- Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security
- Publisher
- ACM
- Published
- 2016-10-24
- Pages
- 1006-1018
- OpenAlex
- W2514893051
- Cited by
- 320
- References
- 58
- FWCI
- 21.42
- Type
- conference paper
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.