Exploring Kyber Crypto System through the lense of Algebraic Lattices
You must have seen an interesting write-up in Scientific American Magazine about a new encryption system that can protect against attacks from Quantum Computers. Please read the following article for further details on this story. These kind of encryption systems are now part of a family of cryptographic algorithms known as ‘Post Quantum Cryptography’. Pioneers of mathematics and cryptography have delived in to this field of research ever since 1998. Let us refer to Wikipedia for the history of lattice based cryptography.
In 1996, Miklós Ajtai introduced the first lattice-based cryptographic construction whose security could be based on the hardness of well-studied lattice problems, and, with Cynthia Dwork showed that a certain average-case lattice problem, known as Short Integer Solutions (SIS), is at least as hard to solve as a worst-case lattice problem.
In 1998, Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman introduced a lattice-based public-key encryption scheme, known as NTRU. However, their scheme is not known to be at least as hard as solving a worst-case lattice problem.
The first lattice-based public-key encryption scheme whose security was proven under worst-case hardness assumptions was introduced by Oded Regev in 2005, together with the Learning with Errors problem (LWE). Since then, much follow-up work has focused on improving Regev’s security proof and improving the efficiency of the original scheme. Much more work has been devoted to constructing additional cryptographic primitives based on LWE and related problems. For example, in 2009, Craig Gentry introduced the first fully homomorphic encryption scheme, which was based on a lattice problem
Thus in this eventful decade from 1996 to 2009 there has been tremendous work in the field of lattice based cryptography. We have to note that serious promises on Quantum Computers started only after Peter Shor invented the Integer Factorisation Algorithm in 1994. It was implemented by IBM in 2000 in an Nuclear Magnetic Resonance (NMR) based Quantum Computer with 7 Qubits.
Hash based Cryptography is another branch of post quantum safe cryptographic algorithms. Lamport Signature, Merkle Signature, Winternitz Signature, SPHINCS signature are some of the prominent algorithms in this branch. Leslie Lamport has invented his hash based signature as early as 1979.
Thus the advent of practical quantum computing and post quantum cryptography happened two decades ago. The foundations of both the fileds are as old as 1980’s. There has been numerous post quantum algorithms invented ever since 1996. NIST Post Quantum Cryptography Competition has been a milestone in this journey. Please find the details of NIST Post Quantum Cryptography Standardisation efforts in this Wikipedia Article. We should also applaud the efforts of European Commission in funding PQCRYPTO project aimed at developing Post Quantum Cryptography ever since 2015. Please find the details of the European Commission efforts here in this portal.
Hence the history of quantum computing and post quantum cryptography are so dense and deep. When we glance through the recent popular science stories we may not get the glimpse of the ocean beneath these marvels.
Now coming to terms with the story mentioned in Scientific American. It is about one of the lattice based cryptographic algorithms which became the finalist in the NIST Post Quantum Cryptography Standardization efforts. It is known as CRYSTALS ( Cryptogrpahic Suite for Algebric Lattices ).
You can find the source code of CRYSTALS in the following github repository. The Key Encapsulation Mechanism used in CRYSTALS is known as Kyber. Kyber is a essentially a key exchange algorithm. Kyber can be considered as a secure scheme with an indistinguishable algorithm under adaptive chosen cipher attack. It is otherwise known as IND-CCA2. IND-CCA2 is considered to be strongest among the three definitions of encryption security. Kyber is IND-CCA2 secure key encapsulation mechanism based on the hardness of solving the learning with error (LWE) problem over modular lattices. As per the website, Kyber-512 aims at security roughly equivalent to AES-128, Kyber-768 aims at security roughly equivalent to AES-192, and Kyber-1024 aims at security roughly equivalent to AES-256.
It is All the instructions for setting up Kyber are in the following page. Kyber is written in C. Kyber uses polynomial based computation instead of integer based computation. Given an array of uniformly random bytes, Kyber computes polynomials with coefficients distributed according to a parametrised centered bionomial distribution. Public Key is serialised as the concatenation of a serialised vector of polynomials and the public seeed used to generate a matrix.
Polynomial multiplication is the basic and the most computationally intensive operation in lattice based cryptosystems. Kyber uses Number Theoretic Transform (NTT) to perform polynomial multiplication efficiently. The NTT is a generalisation of the classic Discrete Fourier transform (DFT) to finite fields. This effectively mens doing a transform over the quotient ring instead of the complex number. An interesting feature of the NTT is that all computations are exact. There is no round off error. This feature has been used to do fast convolutions to multiply extremely large numbers, such as needed when computing the number pi to millions of digits of precision.
There are a lot of elegant mathematical marvels like this in Kyber. Hence Kyber is a well designed and deftly engineered cryptosystem with industry grade maturity and implementations. Let us explore further about the benchmarks and performance highlights of Kyber in another article.
