The DOI matches its Crossref record; 49 of the 49 references it cites were found in a registry or an index.
Post-Quantum Key Exchange for the TLS Protocol from the Ring Learning with Errors Problem
Open accessAbstract
Lattice-based cryptographic primitives are believed to offer resilience against attacks by quantum computers. We demonstrate the practicality of post-quantum key exchange by constructing cipher suites for the Transport Layer Security (TLS) protocol that provide key exchange based on the ring learning with errors (R-LWE) problem, we accompany these cipher suites with a rigorous proof of security. Our approach ties lattice-based key exchange together with traditional authentication using RSA or elliptic curve digital signatures: the post-quantum key exchange provides forward secrecy against future quantum attackers, while authentication can be provided using RSA keys that are issued by today's commercial certificate authorities, smoothing the path to adoption. Our cryptographically secure implementation, aimed at the 128-bit security level, reveals that the performance price when switching from non-quantum-safe key exchange is not too high. With our R-LWE cipher suites integrated into the Open SSL library and using the Apache web server on a 2-core desktop computer, we could serve 506 RLWE-ECDSA-AES128-GCM-SHA256 HTTPS connections per second for a 10 KiB payload. Compared to elliptic curve Diffie-Hellman, this means an 8 KiB increased handshake size and a reduction in throughput of only 21%. This demonstrates that provably secure post-quantum key-exchange can already be considered practical.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
New directions in cryptography
Diffie, W., & Hellman, M. (1976) · IEEE Transactions on Information Theory · doi:10.1109/tit.1976.1055638 · Cited by 14,713
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1978) · Communications of the ACM · doi:10.1145/359340.359342 · Cited by 13,462
An algorithm for the machine calculation of complex Fourier series
Cooley, J. W., & Tukey, J. W. (1965) · Mathematics of Computation · doi:10.1090/s0025-5718-1965-0178586-1 · Cited by 13,154
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1983) · Communications of the ACM · doi:10.1145/357980.358017 · Cited by 13,012
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
Fully homomorphic encryption using ideal lattices
Gentry, C. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536440 · Cited by 6,806
Koblitz, N. (1987) · Mathematics of Computation · doi:10.1090/s0025-5718-1987-0866109-5 · Cited by 5,634
Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems
Kocher, P. C. (1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-68697-5_9 · Cited by 4,387
Use of Elliptic Curves in Cryptography
Miller, V. S. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-39799-x_31 · Cited by 3,946
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
The Transport Layer Security (TLS) Protocol Version 1.1
Dierks, T., & Rescorla, E. (2006) · doi:10.17487/rfc4346 · Cited by 2,278
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 · cited 4×
“3https://github.com/NTRUOpenSourceProject/ntru-crypto Notation.”
BackgroundInfluentialThe Transport Layer Security (TLS) Protocol Version 1.3
Rescorla, E. (2018) · doi:10.17487/rfc8446 · Cited by 1,897
Entity Authentication and Key Distribution
Bellare, M., & Rogaway, P. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48329-2_21 · Cited by 1,752
The Transport Layer Security (TLS) Protocol Version 1.2
Dierks, T., & Rescorla, E. (2008) · doi:10.17487/rfc5246 · Cited by 1,576
Cache Attacks and Countermeasures: The Case of AES
Osvik, D. A., Shamir, A., & Tromer, E. (2006) · Lecture Notes in Computer Science · doi:10.1007/11605805_1 · Cited by 1,352
Schnelle Multiplikation großer Zahlen
Schönhage, A., & Strassen, V. (1971) · Computing · doi:10.1007/bf02242355 · Cited by 1,107
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
Candidate Multilinear Maps from Ideal Lattices
Garg, S., Gentry, C., & Halevi, S. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38348-9_1 · Cited by 744
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
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
Micciancio, D., & Regev, O. (2009) · Post-Quantum Cryptography · doi:10.1007/978-3-540-88702-7_5 · Cited by 615
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
Regev, O. (2006) · Lecture Notes in Computer Science · doi:10.1007/11818175_8 · Cited by 485
A Toolkit for Ring-LWE Cryptography
Lyubashevsky, V., Peikert, C., & Regev, O. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-38348-9_3 · Cited by 416
SIGMA: The ‘SIGn-and-MAc’ Approach to Authenticated Diffie-Hellman and Its Use in the IKE Protocols
Krawczyk, H. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-45146-4_24 · Cited by 382
Lattice Cryptography for the Internet
Peikert, C. (2014) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-11659-4_12 · Cited by 356
How to Enhance the Security of Public-Key Encryption at Minimum Cost
Fujisaki, E., & Okamoto, T. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-49162-7_5 · Cited by 342
Elliptic Curve Cryptography in Practice
Bos, J. W., Halderman, J. A., Heninger, N., Moore, J., Naehrig, M., & Wustrow, E. (2014) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-45472-5_11 · Cited by 321
Self-citationA framework for fast quantum mechanical algorithms
Grover, L. K. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276712 · Cited by 240
On 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
A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem.
Ding, J. (2012) · 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
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
A Comparison of the Homomorphic Encryption Schemes FV and YASHE
Lepoint, T., & Naehrig, M. (2014) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-06734-6_20 · Cited by 173
Self-citationSmooth Projective Hashing and Password-Based Authenticated Key Exchange from Lattices
Katz, J. I., & Vaikuntanathan, V. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-10366-7_37 · Cited by 144
Tag Size Does Matter: Attacks and Proofs for the TLS Record Protocol
Paterson, K. G., Ristenpart, T., & Shrimpton, T. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-25385-0_20 · Cited by 125
Sampling from discrete Gaussians for lattice-based cryptography on a constrained device
Dwarakanath, N. C., & Galbraith⋆, S. D. (2014) · Applicable Algebra in Engineering Communication and Computing · doi:10.1007/s00200-014-0218-3 · Cited by 121
Fast polynomial transform algorithms for digital convolution
Nussbaumer, H. (1980) · IEEE Transactions on Acoustics Speech and Signal Processing · doi:10.1109/tassp.1980.1163372 · Cited by 104
Finding shortest lattice vectors faster using quantum search
Laarhoven, T., Mosca, M., & van de Pol, J. (2015) · Designs Codes and Cryptography · doi:10.1007/s10623-015-0067-5 · Cited by 97
Strongly Secure Authenticated Key Exchange from Factoring, Codes, and Lattices
Fujioka, A., Suzuki, K., Xagawa, K., & Yoneyama, K. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-30057-8_28 · Cited by 93
A Note on Quantum Security for Post-Quantum Cryptography
Song, F. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-11659-4_15 · Cited by 74
Quantum Key Distribution in the Classical Authenticated Key Exchange Framework
Mosca, M., Stebila, D., & Ustaoğlu, B. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38616-9_9 · Cited by 61
Self-citationBos, J. W., Costello, C., Hışıl, H., & Lauter, K. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38348-9_12 · Cited by 61
Self-citationFujioka, A., Suzuki, K., Xagawa, K., & Yoneyama, K. (2013) · ACM Asia Conference on Computer and Communications Security (ASIA CCS) · doi:10.1145/2484313.2484323 · Cited by 55
Estimating Key Sizes for High Dimensional Lattice-Based Systems
van de Pol, J., & Smart, N. P. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-45239-0_17 · Cited by 41
Multi-Ciphersuite Security of the Secure Shell (SSH) Protocol
Bergsma, F., Dowling, B., Kohlar, F., Schwenk, J., & Stebila, D. (2014) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2660267.2660286 · Cited by 32
Self-citationAuthenticated Key Exchange from Ideal Lattices.
Zhang, J., Zhang, Z., Ding, J., & Snook, M. (2014) · Cited by 3
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-citationA 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
Frodo: Take off the Ring! Practical, Quantum-Secure Key Exchange from LWE
Bos, J., Costello, C., Ducas, L., Mironov, I., Naehrig, M., Nikolaenko, V., Raghunathan, A., & Stebila, D. (2016) · Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2976749.2978425 · Cited by 320
Self-citationFernandez-Carames, T. M. (2020) · IEEE Internet of Things Journal · doi:10.1109/jiot.2019.2958788 · Cited by 317
Post-Quantum Lattice-Based Cryptography Implementations: A Survey
Nejatollahi, H., Dutt, N., Ray, S., Regazzoni, F., Banerjee, I., & Cammarota, R. (2019) · ACM Computing Surveys · doi:10.1145/3292548 · Cited by 277
Metadata
- Authors
- Bos, J. W., Costello, C., Naehrig, M., & Stebila, D.
- Venue
- 2015 IEEE Symposium on Security and Privacy
- Publisher
- IEEE
- Published
- 2015-05
- Pages
- 553-570
- ISSN
- 1081-6011 (ISSN-L)
- OpenAlex
- W1595771334
- Cited by
- 329
- References
- 49
- FWCI
- 24.05
- Type
- conference paper
- Language
- en
- Open access
- hybrid
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.