Post-Quantum Cryptography (PQC): a classical solution to the quantum threat

Introduction

Public key (or asymmetric) cryptography is one of the bases on which all communication protocols rest which, starting from an insecure channel, must achieve multiple security properties, such as secrecy or integrity of information. Various cryptographic techniques relate to this area, including key negotiation algorithms and digital signature algorithms. These hold a prominent place, both for technological maturity and for adoption in widely used protocols such as TLS, IPsec, or WireGuard.

Asymmetric cryptographic techniques base their security on the presumed intractability of some mathematical problems, i.e. problems for which no algorithm is known capable of tracing the solution in a computationally efficient way and, while relying on the most powerful computing systems available today, an eventual resolution would take impractical times (thousands of years). Some examples are the integer factorization problem and the discrete logarithm problem, the former underlying the RSA cryptosystem, and the latter of the Diffie-Hellman protocol.

These two problems constitute the totality of those employed in standardized asymmetric algorithms and although they have withstood decades of cryptanalysis, recent developments in quantum computing could pose a real threat. In particular, if a suitable quantum computer were created, Shor’s quantum algorithm (1994) would be able to break the two problems mentioned above in a reasonable time, impacting the security of all public-key cryptography in use today.

Although the medium-long term implementability of Shor’s algorithm remains doubtful given the important technological challenges posed by the development of quantum computers, the American National Security Agency (NSA) publicly expressed in 2015 the need for a transition plan to algorithms quantum-resistant cryptographic, i.e. resistant to attacks by a quantum computer.

In fact, although it is still complex to express a precise assessment of the time horizon in which quantum computers could pose a concrete threat to public-key cryptography, it is desirable that a transition process be concluded as soon as possible, in order to minimize risks related to long-term security information. In fact, already today an attacker could adopt strategies such as “store now, decrypt later”, intercepting and storing the encrypted traffic with the aim of using a quantum computer for the decryption of data in the future. At the same time, the transition period to new cryptographic techniques is not negligible and, in this case, it is necessary to complete it by anticipating the creation of an appropriate quantum computer, otherwise the information will be exposed.

The main quantum-resistant techniques addressed in this scenario are Quantum Key Distribution (QKD) and Post-Quantum Cryptography (PQC). The first is a physical and infrastructural response to the problem of key exchange over an insecure channel: using the principles of quantum physics it is possible to establish a protocol with unconditional security that allows two parties to negotiate a cryptographic key with which subsequently protect their communication. This technique is not based on the assumption that some mathematical problems are intractable but has its roots in the laws of physics.

Post-Quantum Cryptography (PQC) is, on the other hand, a classic response to the advent of quantum computing. In fact, PQC deals with the design of public-key cryptographic schemes that can be implemented on classical computers and are also resistant to quantum-type attacks. Consequently, post-quantum cryptographic techniques base their security on mathematical problems for which efficient solution algorithms are not known, regardless of their classical or quantum nature. For example, RSA and Diffie-Hellman, based on problems solvable with Shor’s quantum algorithm, cannot be considered post-quantum.

Click the link to read the full article.

For other articles related to Quantum and Cryptography topics, please refer to the related categories in the blog.

The authors

Edoardo Signorini, graduated in Mathematics with a curriculum in cryptography at the University of Trento, in 2020 carried out the Master’s thesis in the field of Post-Quantum Cryptography (PQC) at Telsy. He currently holds the role of cryptographer within the Telsy research group and carries out an industrial research doctorate in Pure and Applied Mathematics at the Politecnico di Torino. His activity focuses on PQC research and on the analysis and development of cryptographic protocols.

Giuseppe D’Alconzo, graduated in Mathematics with a specialization in Cryptography at the University of Trento, in 2019 he carried out an internship at Telsy, dealing with Multiparty Computation and Attribute-Based Encryption. He is currently a PhD student in Pure and Applied Mathematics at the Politecnico di Torino, with a “Post-Quantum Cryptography” scholarship within the UniversiTIM program and in collaboration with the Telsy Research Group.