What is Post-Quantum Cryptography

Insight from our technical advisor Professor Huaxiong Wang.

Cryptography is the fundamental pillar of cybersecurity — its main goals are the development of algorithms and tools for achieving privacy, integrity and authenticity of information.

Cryptography is ubiquitously used today to secure all kinds of electronic communication, from mobile phone and internet commerce to social network, cloud computing, blockchain and cryptocurrency. Most of these applications rely crucially on public-key cryptosystems, a class of algorithms which allow information protection between parties which have never met in person (or in more rigorous terms, have no means of exchanging information besides an open public channel); a common situation in practical applications.

The security of any public-key cryptosystem must rely on computational assumptions such as two hard Mathematical problems: the Integer Factorization (IF) and Discrete Logarithm (DL) problems. In 1994, Shor showed that both IF and DL problems are in fact easy to solve on a quantum computer, based crucially on the laws of quantum physics. As a consequence, almost all currently deployed public-key cryptosystems will become completely insecure if quantum computers become a practical reality.

Although the question of the practical realization of quantum computers is complicated and difficult to predict, experts in the field believe that it will be merely a significant engineering challenge, some even predict that within the next 5 to 15 years or so sufficiently large quantum computers to break essentially all public key schemes currently in use would be available. It is clear that there is an urgent need to prepare our security systems to be able to resist quantum computing.

Post-quantum cryptography refers to conventional cryptosystems that are secure against both quantum and classic attacks, and can interoperate with existing communication protocols and networks. It should not be confused with quantum cryptography, which uses properties of quantum mechanics to create a secure communication channel.

Although both IF and DL will fall at the moment of creation of a quantum computer, there are other related classes of well-known problems, against which quantum algorithms have been powerless so far. These classes include those based on lattices, codes, multivariate polynomials and a few others (such as those based on the conjugacy search problem and related problems on braid groups).

Various cryptographic primitives based on the above quantum-resistant problems have been proposed over the last years, design and analysis of post-quantum cryptographic algorithms are one of the most challenging efforts by the international crypto and security communities. It is unavoidable that sooner or later the modern public key cryptography infrastructure will need to move to the post-quantum one, to ensure a smooth and secure transition from the currently used public-key cryptography to its post-quantum counterparts.

In 2016, NIST (National Institute of Standards and Technology) made a call for post-quantum cryptographic algorithms for two new public-key cryptographic standards: Digital signatures and Encryption scheme/key-establishment schemes.

NIST had set the following timeline of this call: (1) Fall 2016 — formal call for proposals; (2) November 2017 — Deadline of submissions; (3) 3–5 years — public analysis phase; (4) 2 years later — draft standard ready. At the end of 2017, 82 algorithms were submitted by the submission deadline, 69 of them were selected to enter to the first round, of which 26 have just advanced to the second round on January 30, 2019 (17 encryption/key-establishment and 9 signature schemes). A further round of intense analysis and cryptanalysis will be followed in the coming 4–6 years, and finally, there will be two winners, one for each type of algorithms.

If you are interested in knowing more about the post-quantum cryptography and how we employ it to the Abelian project, please read: From Post-Quantum Cryptography to Post-Quantum Blockchains and Cryptocurrencies: an Introduction, by our CEO Dr. Duncan Wong.