Towards Post-Quantum Cryptography in TLS

In the field of cryptography, Post-Quantum Cryptography (PQC) is an area of research focused on designing and implementing cryptographic algorithms that are secure against both classical and quantum computers. The motivation behind PQC arises from the potential development of efficient quantum computers in the future, which could break many existing public-key cryptosystems based on number theory problems such as factoring large integers or computing discrete logarithms. PQC algorithms are designed to be resistant against attacks by quantum computers and can be broadly classified into three categories: lattice-based cryptography, code-based cryptography, and multivariate polynomial cryptography. Each of these categories has its own advantages and disadvantages in terms of security, performance, and implementation complexity. In this post, we will discuss two PQC algorithms that have been implemented into BoringSSL: NTRU and SIKE. NTRU (Nth Degree Truncated Polynomial Ring Unrestricted Encryption) is a lattice-based public key cryptosystem introduced in 1996 by Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. The main idea behind NTRU is to use the difficulty of distinguishing random elements from certain structured subsets of polynomial rings over finite fields as the basis for encryption and decryption operations. The hard problem assumed in NTRU is that given two polynomials f and g whose coefficients are short compared to the modulus q, it is difficult to find f and g given only their quotient pk = f / g modulo q. It means that it’s hard to find f and g given only public key pk. The NTRU cryptosystem consists of three main procedures: key generation, encryption, and decryption. In the key generation procedure, two random polynomials are generated as part of the private key (f and g), and their quotient is computed modulo q to obtain the public key pk. The encryption process involves multiplying a plaintext message by the public key pk and adding some noise term to it. Decryption uses both the secret value f and to recover the plaintext as v = f * ct mod q, where ct is the received ciphertext. HRSS (High Rate Subset Sum) is another lattice-based cryptosystem that improves upon NTRU in terms of efficiency and security. HRSS uses a different approach for key generation and decryption compared to NTRU but still relies on the hardness of certain problems related to lattice theory. SIKE (Supersingular Isogeny Key Encapsulation) is an isogeny-based post-quantum cryptographic algorithm that was proposed in 2018 by Craig Costello, David Jao, and Patrick Schmidt. The main idea behind SIKE is to use the difficulty of computing isogenies between supersingular elliptic curves as the basis for key exchange and encryption/decryption operations. An elliptic curve is a set of points that satisfy a specific mathematical equation. In cryptography, we are interested in using elliptic curves with certain properties (e.g., being supersingular) to design secure public-key cryptosystems. The key exchange process in SIKE involves both parties performing random walks on an isogeny graph of supersingular elliptic curves and then sharing some information about their respective walks to compute a shared secret value. In conclusion, Post-Quantum Cryptography plays a crucial role in ensuring the long-term security of our digital communications against potential threats posed by quantum computers. By implementing PQC algorithms like NTRU and SIKE into widely used libraries such as BoringSSL, we can take proactive steps towards preparing for this future scenario while continuing to benefit from the performance advantages offered by today's classical computers.