Post-quantum rsa

D.J. Bernstein, N. Heninger, P. Lou, L. Valenta

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

25 Citations (Scopus)
2 Downloads (Pure)


This paper proposes RSA parameters for which (1) key generation, encryption, decryption, signing, and verification are feasible on today’s computers while (2) all known attacks are infeasible, even assuming highly scalable quantum computers. As part of the performance analysis, this paper introduces a new algorithm to generate a batch of primes. As part of the attack analysis, this paper introduces a new quantum factorization algorithm that is often much faster than Shor’s algorithm and much faster than pre-quantum factorization algorithms. Initial pqRSA implementation results are provided.

Original languageEnglish
Title of host publicationPost-Quantum Cryptography
Subtitle of host publication8th International Workshop, PQCrypto 2017, Utrecht, The Netherlands, June 26-28, 2017, Proceedings
EditorsT. Lange, T. Takagi
Place of PublicationDordrecht
Number of pages19
ISBN (Electronic)978-3-319-59879-6
ISBN (Print)978-3-319-59878-9
Publication statusPublished - 2017
Event8th International Conference on Post-Quantum Cryptography, (PQCrypto 2017) - Utrecht, Netherlands
Duration: 26 Jun 201728 Jun 2017
Conference number: 8

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10346 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference8th International Conference on Post-Quantum Cryptography, (PQCrypto 2017)
Abbreviated titlePQCrypto 2017
Internet address


  • ECM
  • Grover’s algorithm
  • Make RSA Great Again
  • Post-quantum cryptography
  • RSA scalability
  • Shor’s algorithm


Dive into the research topics of 'Post-quantum rsa'. Together they form a unique fingerprint.

Cite this