Post-quantum cryptography

from Wikipedia, the free encyclopedia

Post-quantum cryptography ( English post-quantum cryptography , PQC ) denotes a branch of cryptography that deals with cryptographic primitives concerned, which, unlike most currently used asymmetric cryptosystems even using quantum computers are virtually impossible to decipher. The term post-quantum cryptography was introduced by Daniel J. Bernstein , who was also involved in the organization of the first PQCrypto conference on this topic in 2006 .

Asymmetrical procedure

The term was coined because the first asymmetric cryptosystems were based on the difficulty of prime factorization and the calculation of discrete logarithms , two problems that theoretically - with sufficiently powerful quantum computers - can be solved by the Shor algorithm .

The performance of previous quantum computers is by far not sufficient for such calculations and a scientific breakthrough or milestone is hardly predictable; In 2001, IBM was only able to factorize the number 15 ; in 2012, it succeeded in factoring the number 21.

Symmetrical procedure

For symmetric encryption methods such as AES , quantum computers are a relatively small threat, since the Grover algorithm would reduce the security of a key, measured in bits, by half. The increased computing power could be counteracted with correspondingly longer keys.

future

The development of PQ-safe encryption algorithms based on mathematical lattices , which are used, for example, in Ring-LWE or in NTRUEncrypt, which was patented until 2016, seems promising . In addition, there is research based on

Another research area is the adaptation of cryptographic evidence techniques to quantum attackers. For example, the security evidence of a classic zero-knowledge evidence procedure uses a technique called rewinding , in which the internal state of the attacker is copied. However, according to the no-cloning theorem , the state of a quantum attacker can not always be copied; the proof technique must be adapted accordingly.

A standardization process has been running at NIST since 2016 to test and standardize an algorithm for key exchange / encryption and digital signatures. This has been in the third round since July 22, 2020 and could last until 2021/22. As NIST itself now also writes, it is likely that a lattice-based algorithm will become the standard. There are currently seven algorithms in the selection process, five of which are grid-based, one algorithm is based on multivariate polynomials and one on error-correcting codes.

Web links

  • PQCrypto - Post-Quantum Cryptography Conference

Individual evidence

  1. Jump up ↑ Johannes Buchmann, Carlos Coronado, Martin Döring, Daniela Engelbert, Christoph Ludwig, Raphael Overbeck, Arthur Schmidt, Ulrich Vollmer, Ralf-Philipp Weinmann: Post-Quantum Signatures . 2004, Section 1 Introduction, p. 1 ( iacr.org [PDF]).
  2. ↑ Homepage of PQCrypto 2006
  3. ^ Daniel J. Bernstein : Introduction to post-quantum cryptography . 2009 (English, springer.com/cda [PDF] introductory chapter of the book Post-quantum cryptography ).
  4. ↑ a b c cryptography according to the quantum computer. In: Telepolis . Retrieved September 18, 2013.
  5. ↑ Enrique Martín-López, Anthony Laing, Thomas Lawson, Roberto Alvarez, Xiao-Qi Zhou, Jeremy L. O'Brien: Experimental realization of Shor's quantum factoring algorithm using qubit recycling (=  Nature Photonics . Volume 6 ). 2012, p. 773-776 ( nature.com ).
  6. ^ Q&A With Post-Quantum Computing Cryptography Researcher Jintai Ding (en) , IEEE Spectrum . November 1, 2008. 
  7. ^ John Watrous: Zero-Knowledge against Quantum Attacks . In: SIAM J. Comput. . 39, No. 1, 2009, pp. 25-58. doi : 10.1137 / 060670997 .
  8. ^ Information Technology Laboratory Computer Security Division: Post-Quantum Cryptography | CSRC | CSRC. January 3, 2017, accessed July 31, 2020 (American English).
  9. ↑ Google Groups. Accessed July 31, 2020 .