Kyber: analysis of a Nist´s post-quantum cryptographic standard

Abstract

Quantum computing represents a threat to security over the internet due to its capacity to factorize composite numbers under polynomial time. This is done using Shor's algorithm and when a big enough quantum computer is built RSA will become obsolete. The cryptographic community started to look for alternatives that could work as public key cryptosystems. One of these alternatives is CRYSTALS-Kyber, considered by NIST as a possible new standard in the post-quantum era. Kyber's security depends on a computationally hard problem over Lattices, Learning With Errors. The version used in Kyber is Module LWE and relies on the polynomial ring structure to speed up matrix multiplication. This is something special in Kyber that uses the Number Theoretic Transform to map polynomials to a domain where multiplication can be done more eficiently. This carries some drawbacks as the NTT is known to be vulnerable against some attacks that target the implementation on physical devices. These are the side-channel attacks which, as for today, have become Kyber's biggest enemy. We will try to find protection against these attacks in interpreted languages that allow us to make implementations that are closer to the mathematical problem than compiled languages. We will answer how RSA works, how does Shor's algorithm break it, how big the impact in performance of the NTT is and how eficient an implementation in interpreted languages can be.

La computación cuántica está cerca de convertirse en una amenaza para la seguridad en internet gracias a su capacidad de factorizar números eficientemente. El algoritmo de Shor dejará RSA obsoleto una vez que exista un computador suficientemente grande. En la comunidad criptográfica se están buscando alternativas que sirvan como estándar de criptografía de clave pública. Una de estas alternativas es CRYSTALS-Kyber, considerado por el NIST como posible nuevo estándar en la era post-cuántica. La seguridad de Kyber depende de un problema computacionalmente difícil de retículos, Learning With Errors. La versión presente en Kyber es Module LWE que utiliza la estructura de anillo de polinomios para acelerar la multiplicación de matrices. Esto es algo característico de Kyber, que usa la Number Theoretic Transform para representar los polinomios en un dominio donde la multiplicación se puede hacer de forma eficiente. Esta decisión trae algunas desventajas ya que la NTT es vulnerable frente a ciertos ataques que aprovechan su implementación en dispositivos físicos, los ataques por canal lateral. A día de hoy estos son el mayor enemigo de Kyber. Se pretende proteger Kyber de estos ataques implementándolo en lenguajes de alto nivel que permitan mantener el código más fiel al planteamiento matemático, algo difícil en lenguajes compilados. Queremos responder cómo funciona RSA, cómo el algoritmo de Shor puede vulnerarlo, cuánto se nota el impacto en rendimiento de la NTT y cómo de eficiente puede ser una implementación en un lenguaje interpretado.