Criptografı́a post-cuántica, desafı́os y direcciones de investigación
Fernando Virdia
[Link]
Universidade NOVA de Lisboa
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Resumen
Motivación: Criptografı́a y Computación Cuántica
Fundamentos: Nuevas Suposiciones de Dificultad
Estandares: El proceso del NIST de EE. UU.
Implementación: Algunos desafı́os
Diapositivas en [Link]
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Criptografı́a “Pre-Post-Cuántica”
Normalmente, la criptografı́a se presenta como compuesta por dos componentes:
Criptografı́a simétrica, que se encarga de las comunicaciones seguras entre partes
que comparten una clave secreta o una contraseña.
Criptografı́a asimétrica (o criptografı́a de clave pública), que permite a partes
distantes acordar una clave secreta compartida a través de un canal no seguro.
Juntas, posibilitan el despliegue en gran escala de la criptografı́a que vemos hoy en dı́a
en Internet y en los sistemas de pago electronico.
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Ambos tipos de primitivas se construyen utilizando diferentes grados de estructura
matemática.
La estructura usada deberı́a implicar que un adversario que intenta romper la
primitiva necesita resolver algún problema matemático difı́cil.
Formalizamos estos problemas en “suposiciones de dificultad” concisas.
Parte del trabajo de los criptógrafos es identificar suposiciones de dificultad,
intentar romperlas y construir primitivas a partir de ellas.
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Los sistemas de clave pública (PKC) de hoy en dı́a se basan principalmente en
suposiciones de dificultad relacionadas con dos problemas matemáticos:
Factorización
Sean p y q dos números primos aleatorios diferentes y de tamaño similar, log p ≈ log q.
Dado N = p · q, encontrar p y q.
Logaritmo discreto (DLOG)
Sean G un grupo finito y g ∈ G un elemento que genera un subgrupo grande ⟨g⟩ ⊂ G.
Sea x un número entero al azar en {0, . . . , |⟨g⟩| − 1}.
Dado g x , encontrar x .
Estos problemas han sido ampliamente estudiados y se utilizan en todas partes en
software y hardware.
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
¿Qué entendemos por ”la factorización es difı́cil”?
Intuitivamente, resolver una instancia aleatoria deberı́a requerir muchos recursos
(cálculos, memoria, energı́a, dinero, etc.).
Para determinar si esto es cierto, investigamos algoritmos para resolver el
problema (criptoanálisis) y encontramos una fórmula para el costo te tales
algorithms en función de los parámetros del problema (e.g., en funcion de log N).
Teniendo en cuenta los ataques conocidos, utilizamos estas fórmulas para elegir
los parámetros del problema de manera que el costo sea “suficientemente alto”
(por ejemplo, de manera que requiera ≥ 2128 ciclos de CPU para resolverlo).
También investigamos las relaciones matemáticas del problema con otros similares.
NOTA: No podemos tener certeza absoluta de que el problema sea difı́cil. (Por
ejemplo, tal vez P = NP).
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Ejemplo: la dificultad de la factorización
Sea N = p · q con p y q aleatorios, de manera que log p ≈ log q.
log N
Para factorizar N, se requiere un máximo de 2log p ≈ 2 2 intentos de división
(intentando adivinar p).
Pero existen ataques mucho más rápidos, como la criba general de cuerpos de
números (GNFS), que requiere
q
1 2
3 64
exp 9 + o(1) (ln N) (ln ln N)
3 3 operaciones de CPU.
Al elegir adecuadamente ln N, podemos asegurarnos de que GNFS sea demasiado
costoso de ejecutar.
¿Sabemos con certeza que no existe un ataque mejor? ¡No! La única opción es hacer
nuestro mejor esfuerzo para estudiar el problema y posibles ataques nuevos.
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
¿Preguntas hasta el momento?
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Computación Cuántica
Hasta ahora, las suposiciones de dificultad relacionadas con la factorización y el
logaritmo discreto funcionaron bien. ¿Qué cambió?
En la década de 1980, algunos fı́sicos comenzaron a considerar el uso de
fenómenos mecánicos cuánticos para realizar cálculos.
Durante mucho tiempo, hubo mejoras prácticas muy pequeñas.
En la última década, muchas inversiones de la industria se destinaron a esta
tecnologı́a [MQT18, MN18, AAB+ 19, Gib19, WFG21].
Las computadoras cuánticas representarı́an un nuevo tipo de “recurso” en manos de los
atacantes.¿Cómo amenaza esto a la criptografı́a? Hasta ahora, en forma de dos
algoritmos: Grover y Shor.
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
El algoritmo de Grover
Supongamos que tenemos una lista L de N elementos diferentes, ordenados al
azar.
Digamos que sabemos que x ∈ L, pero necesitamos encontrar su ı́ndice.
Clásicamente, esto requerirı́a O(N) comparaciones.L[0]=x ?L[1]=x ? . . .
√
El algoritmo de Grover te permite encontrar x en O( N) comparaciones
superpuestas.
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
El algoritmo de Grover
¿Cómo afecta a la criptografı́a?
Ejemplo
Supongamos que tienes un cifrado con 2128 posibles claves secretas.
Clásicamente, encontrar la clave correcta requiere aproximadamente 2128 intentos.
√
Cuánticamente, podrı́a requerir aproximadamente 2128 = 264 intentos.
Cualquier cifrado se debilita automáticamente.
¡Podrı́as necesita claves el doble de largas!
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
El algoritmo de Shor
Recordemos el tiempo de ejecución del mejor algoritmo de factorización, GNFS:
q
1 2
3 64
exp 9 + o(1) (ln N) (ln ln N)3 3 ciclos de CPU.
En 1994, Peter Shor desarrolla un algoritmo cuántico que se ejecuta en
O (log N)2 (log log N)(log log log N) operaciones cuánticas.
De subexponencial en log N (¡difı́cil!) a polilogarı́tmico (¡fácil!)
Peor aún: no solo afecta la factorización, ¡sino también el logaritmo discreto!
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
En el lapso de un solo algoritmo, perdimos dos familias de suposiciones de
dificultad.
En particular, las dos en las que la mayorı́a de la criptografı́a de clave pública
comercial se basa.
Esto significa que si/en cuanto una computadora cuántica capaz de ejecutar el
algoritmo de Shor esté disponible, las futuras comunicaciones encriptadas estarán
en riesgo.
También significa que cualquier mensaje encriptado compartido hasta ese
momento y almacenado estará en riesgo de descifrado, incluso si hoy son seguros.
Necesitamos nuevas suposiciones de dificultad que no puedan resolverse con
computadoras cuánticas. Necesitamos criptografı́a “post-cuántica” (PQC).
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Hacia la Criptografı́a Post-Cuántica
¿En qué consistirı́a esta actualización? Implicarı́a varios pasos.
Identificar nuevas suposiciones de dificultad que sean resistentes a la computación
cuántica.
Diseñar primitivas criptográficas basadas en estas suposiciones, usarlas para
actualizar protocolos más complejos.
Producir implementaciones seguras y estándares legales.
Desplegar en sistemas del mundo real.
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
¿Preguntas hasta el momento?
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Suposiciones de dificultad
Hay muchos tipos, algunos más nuevos, otros más antiguos.
Se utilizan diversas estructuras matemáticas, por ejemplo
Códigos de corrección de errores
Anillos polinómicos y retı́culos algebraicos
Sistemas de ecuaciones cuadráticas multivariables
Problemas relativos a isogenias de curvas elipticas
Problemas relativos a funciones de hash
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Suposiciones de dificultad
Hay muchos tipos, algunos más nuevos, otros más antiguos.
Se utilizan diversas estructuras matemáticas, por ejemplo
Códigos de corrección de errores
Anillos polinómicos y retı́culos algebraicos
Sistemas de ecuaciones cuadráticas multivariables
Problemas relativos a isogenias de curvas elipticas
Problemas relativos a funciones de hash
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Suposiciones de dificultad
Hay muchos tipos, algunos más nuevos, otros más antiguos.
Se utilizan diversas estructuras matemáticas, por ejemplo
Códigos de corrección de errores
Anillos polinómicos y retı́culos algebraicos ← demos un ejemplo
Sistemas de ecuaciones cuadráticas multivariables
Problemas relativos a isogenias de curvas elipticas
Problemas relativos a funciones de hash
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Recordatorio matemático: polinomios
Dado un anillo algebraico R (como los enteros, Z, o los enteros módulo q, Zq )
y una variable desconocida x ,
se puede definir el anillo de polinomios Z[x ] con elementos p(x ) tales que:
p(x ) = p0 + p1 · x + p2 · x 2 + · · · + pn · x n ,
donde p0 , . . . , pn ∈ R, pn ̸= 0. Decimos que n es el grado de p.
Podemos sumar, multiplicar y dividir polinomios.
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
PQC utilizando anillos polinómicos [Reg05, SSTX09, LPR10]
Definamos
q ∈ Z, y ϕ = x n + 1 donde n := 2k para algun k ∈ Z+ ,
R := Zq [x ]/(ϕ),
a ← U(R) y s, e ∈ R aleatorios de manera que los coeficientes sigan una
distribución gaussiana redondeada al entero más cercano en [−q/2, q/2).
Search Ring Learning With Errors (RLWE)
Dados (a, b := a · s + e mod q) ∈ R × R, recuperar s.
Decision Ring Learning With Errors (RLWE)
Dados (a, b) ∈ R × R, adivinar si b ∼ U(R) o si b = a · s + e mod q.
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Dadas las nuevas suposiciones, se necesitan nuevos diseños.
A veces, las similitudes entre las suposiciones ”precuánticas” y ”poscuánticas”
significan que los diseños pueden ser similares.
Incluso en esos casos, se pueden introducir diferencias sutiles.
Similitud entre RLWE y DLOG
“dados (a, a · s + e), recuperar s” ∼ “dados (g, g x ), recuperar x ”
Intentemos usar esto para adaptar una primitiva DLOG a RLWE.
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Presentaré el cifrado ElGamal (seguro de contra atacantes pasiva).
Este es un esquema clásico de cifrado de clave pública, muy similar al intercambio
de claves Diffie-Hellman.
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Presentaré el cifrado ElGamal (seguro de contra atacantes pasiva).
Este es un esquema clásico de cifrado de clave pública, muy similar al intercambio
de claves Diffie-Hellman.
Alice Bob
𝑠𝑘, 𝑝𝑘 = 𝐾𝐺𝑒𝑛()
𝑝𝑘
𝑚∈ℳ
𝑐 = 𝐸𝑛𝑐(𝑝𝑘, 𝑚)
𝑐
𝑚 = 𝐷𝑒𝑐(𝑠𝑘, 𝑐)
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Presentaré el cifrado ElGamal (seguro de contra atacantes pasiva).
Este es un esquema clásico de cifrado de clave pública, muy similar al intercambio
de claves Diffie-Hellman.
Alice Bob
𝑠𝑘, 𝑝𝑘 = 𝐾𝐺𝑒𝑛()
𝑝𝑘
𝑚∈ℳ
𝑐 = 𝐸𝑛𝑐(𝑝𝑘, 𝑚)
𝑐
𝑚 = 𝐷𝑒𝑐(𝑠𝑘, 𝑐)
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Presentaré el cifrado ElGamal (seguro de contra atacantes pasiva).
Este es un esquema clásico de cifrado de clave pública, muy similar al intercambio
de claves Diffie-Hellman.
Alice Bob
𝑠𝑘, 𝑝𝑘 = 𝐾𝐺𝑒𝑛()
𝑝𝑘
𝑚∈ℳ
𝑐 = 𝐸𝑛𝑐(𝑝𝑘, 𝑚)
𝑐
𝑚 = 𝐷𝑒𝑐(𝑠𝑘, 𝑐)
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Sea ⟨g⟩ un subgrupo grande de F×
q.
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Sea ⟨g⟩ un subgrupo grande de F×
q.
KGen():
sk ← x ∼ U(Z|⟨g⟩| ),
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Sea ⟨g⟩ un subgrupo grande de F×
q.
KGen():
sk ← x ∼ U(Z|⟨g⟩| ),
pk ← (g, h := g x ),
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Sea ⟨g⟩ un subgrupo grande de F×
q.
KGen():
sk ← x ∼ U(Z|⟨g⟩| ),
pk ← (g, h := g x ),
Enc(pk, m):
y ∼ U(Z|⟨g⟩| ),
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Sea ⟨g⟩ un subgrupo grande de F×
q.
KGen():
sk ← x ∼ U(Z|⟨g⟩| ),
pk ← (g, h := g x ),
Enc(pk, m):
y ∼ U(Z|⟨g⟩| ),
c1 ← g y ,
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Sea ⟨g⟩ un subgrupo grande de F×
q.
KGen():
sk ← x ∼ U(Z|⟨g⟩| ),
pk ← (g, h := g x ),
Enc(pk, m):
y ∼ U(Z|⟨g⟩| ),
c1 ← g y ,
c2 ← hy · m,
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Sea ⟨g⟩ un subgrupo grande de F×
q.
KGen():
sk ← x ∼ U(Z|⟨g⟩| ),
pk ← (g, h := g x ),
Enc(pk, m):
y ∼ U(Z|⟨g⟩| ),
c1 ← g y ,
c2 ← hy · m,
Dec(sk, (c1 , c2 )):
m′ ← c2 /c1x = hy · m/g y x
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Sea ⟨g⟩ un subgrupo grande de F×
q.
KGen():
sk ← x ∼ U(Z|⟨g⟩| ),
pk ← (g, h := g x ),
Enc(pk, m):
y ∼ U(Z|⟨g⟩| ),
c1 ← g y ,
c2 ← hy · m,
Dec(sk, (c1 , c2 )):
m′ ← c2 /c1x = hy · m/g y x = (g x )y · m/g y x
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Sea ⟨g⟩ un subgrupo grande de F×
q.
KGen():
sk ← x ∼ U(Z|⟨g⟩| ),
pk ← (g, h := g x ),
Enc(pk, m):
y ∼ U(Z|⟨g⟩| ),
c1 ← g y ,
c2 ← hy · m,
Dec(sk, (c1 , c2 )):
m′ ← c2 /c1x = hy · m/g y x = (g x )y · m/g y x = m,
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Sea ⟨g⟩ un subgrupo grande de F×
q . Sea a ∼ U(R).
KGen():
sk ← x ∼ U(Z|⟨g⟩| ),
pk ← (g, h := g x ),
Enc(pk, m):
y ∼ U(Z|⟨g⟩| ),
c1 ← g y ,
c2 ← hy · m,
Dec(sk, (c1 , c2 )):
m′ ← c2 /c1x = hy · m/g y x = (g x )y · m/g y x = m,
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Sea ⟨g⟩ un subgrupo grande de F×
q . Sea a ∼ U(R).
KGen():
sk ← x ∼ U(Z|⟨g⟩| ), sk ← (s, e) ∼ χ(R) × χ(R),
pk ← (g, h := g x ),
Enc(pk, m):
y ∼ U(Z|⟨g⟩| ),
c1 ← g y ,
c2 ← hy · m,
Dec(sk, (c1 , c2 )):
m′ ← c2 /c1x = hy · m/g y x = (g x )y · m/g y x = m,
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Sea ⟨g⟩ un subgrupo grande de F×
q . Sea a ∼ U(R).
KGen():
sk ← x ∼ U(Z|⟨g⟩| ), sk ← (s, e) ∼ χ(R) × χ(R),
pk ← (g, h := g x ), pk ← (a, b := a · s + e),
Enc(pk, m):
y ∼ U(Z|⟨g⟩| ),
c1 ← g y ,
c2 ← hy · m,
Dec(sk, (c1 , c2 )):
m′ ← c2 /c1x = hy · m/g y x = (g x )y · m/g y x = m,
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Sea ⟨g⟩ un subgrupo grande de F×
q . Sea a ∼ U(R).
KGen():
sk ← x ∼ U(Z|⟨g⟩| ), sk ← (s, e) ∼ χ(R) × χ(R),
pk ← (g, h := g x ), pk ← (a, b := a · s + e),
Enc(pk, m):
y ∼ U(Z|⟨g⟩| ), (r , f , f ′ ) ∼ χ(R) × χ(R) × χ(R),
c1 ← g y ,
c2 ← hy · m,
Dec(sk, (c1 , c2 )):
m′ ← c2 /c1x = hy · m/g y x = (g x )y · m/g y x = m,
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Sea ⟨g⟩ un subgrupo grande de F×
q . Sea a ∼ U(R).
KGen():
sk ← x ∼ U(Z|⟨g⟩| ), sk ← (s, e) ∼ χ(R) × χ(R),
pk ← (g, h := g x ), pk ← (a, b := a · s + e),
Enc(pk, m):
y ∼ U(Z|⟨g⟩| ), (r , f , f ′ ) ∼ χ(R) × χ(R) × χ(R),
c1 ← g y , c1 ← a · r + f ,
c2 ← hy · m,
Dec(sk, (c1 , c2 )):
m′ ← c2 /c1x = hy · m/g y x = (g x )y · m/g y x = m,
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Sea ⟨g⟩ un subgrupo grande de F×
q . Sea a ∼ U(R).
KGen():
sk ← x ∼ U(Z|⟨g⟩| ), sk ← (s, e) ∼ χ(R) × χ(R),
pk ← (g, h := g x ), pk ← (a, b := a · s + e),
Enc(pk, m):
y ∼ U(Z|⟨g⟩| ), (r , f , f ′ ) ∼ χ(R) × χ(R) × χ(R),
c1 ← g y , c1 ← a · r + f ,
q
c2 ← hy · m, c2 ← b · r + f ′ + 2 · m,
Dec(sk, (c1 , c2 )):
m′ ← c2 /c1x = hy · m/g y x = (g x )y · m/g y x = m,
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Sea ⟨g⟩ un subgrupo grande de F×
q . Sea a ∼ U(R).
KGen():
sk ← x ∼ U(Z|⟨g⟩| ), sk ← (s, e) ∼ χ(R) × χ(R),
pk ← (g, h := g x ), pk ← (a, b := a · s + e),
Enc(pk, m):
y ∼ U(Z|⟨g⟩| ), (r , f , f ′ ) ∼ χ(R) × χ(R) × χ(R),
c1 ← g y , c1 ← a · r + f ,
q
c2 ← hy · m, c2 ← b · r + f ′ + 2 · m,
Dec(sk, (c1 , c2 )):
m′ ← c2 /c1x = hy · m/g y x = (g x )y · m/g y x = m,
m′ ← c2 − s · c1
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Sea ⟨g⟩ un subgrupo grande de F×
q . Sea a ∼ U(R).
KGen():
sk ← x ∼ U(Z|⟨g⟩| ), sk ← (s, e) ∼ χ(R) × χ(R),
pk ← (g, h := g x ), pk ← (a, b := a · s + e),
Enc(pk, m):
y ∼ U(Z|⟨g⟩| ), (r , f , f ′ ) ∼ χ(R) × χ(R) × χ(R),
c1 ← g y , c1 ← a · r + f ,
q
c2 ← hy · m, c2 ← b · r + f ′ + 2 · m,
Dec(sk, (c1 , c2 )):
m′ ← c2 /c1x = hy · m/g y x = (g x )y · m/g y x = m,
m′ ← c2 − s · c1 = (b · r + f ′ + q2 · m) − s · (a · r + f )
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Sea ⟨g⟩ un subgrupo grande de F×
q . Sea a ∼ U(R).
KGen():
sk ← x ∼ U(Z|⟨g⟩| ), sk ← (s, e) ∼ χ(R) × χ(R),
pk ← (g, h := g x ), pk ← (a, b := a · s + e),
Enc(pk, m):
y ∼ U(Z|⟨g⟩| ), (r , f , f ′ ) ∼ χ(R) × χ(R) × χ(R),
c1 ← g y , c1 ← a · r + f ,
q
c2 ← hy · m, c2 ← b · r + f ′ + 2 · m,
Dec(sk, (c1 , c2 )):
m′ ← c2 /c1x = hy · m/g y x = (g x )y · m/g y x = m,
m′ ← c2 − s · c1 = (b · r + f ′ + q2 · m) − s · (a · r + f ) = q
2 ·m+ e ·r −s ·f +f ′
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Sea ⟨g⟩ un subgrupo grande de F×
q . Sea a ∼ U(R).
KGen():
sk ← x ∼ U(Z|⟨g⟩| ), sk ← (s, e) ∼ χ(R) × χ(R),
pk ← (g, h := g x ), pk ← (a, b := a · s + e),
Enc(pk, m):
y ∼ U(Z|⟨g⟩| ), (r , f , f ′ ) ∼ χ(R) × χ(R) × χ(R),
c1 ← g y , c1 ← a · r + f ,
q
c2 ← hy · m, c2 ← b · r + f ′ + 2 · m,
Dec(sk, (c1 , c2 )):
m′ ← c2 /c1x = hy · m/g y x = (g x )y · m/g y x = m,
m′ ← ⌊c2 − s · c1 ⌉ = ⌊(b · r + f ′ + q2 · m) − s · (a · r + f )⌉ = ⌊ q2 · m + e · r − s · f + f ′ ⌉
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Sea ⟨g⟩ un subgrupo grande de F×
q . Sea a ∼ U(R).
KGen():
sk ← x ∼ U(Z|⟨g⟩| ), sk ← (s, e) ∼ χ(R) × χ(R),
pk ← (g, h := g x ), pk ← (a, b := a · s + e),
Enc(pk, m):
y ∼ U(Z|⟨g⟩| ), (r , f , f ′ ) ∼ χ(R) × χ(R) × χ(R),
c1 ← g y , c1 ← a · r + f ,
q
c2 ← hy · m, c2 ← b · r + f ′ + 2 · m,
Dec(sk, (c1 , c2 )):
m′ ← c2 /c1x = hy · m/g y x = (g x )y · m/g y x = m,
m′ ← ⌊c2 − s · c1 ⌉ = ⌊(b · r + f ′ + q2 · m) − s · (a · r + f )⌉ = ⌊ q2 · m + e · r − s · f + f ′ ⌉
= q2 · m con alta probabilidad.
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
¿Preguntas hasta ahora?
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Implementaciones seguras y estándares legales
Las implementaciones seguras son un campo amplio en criptografı́a.
No es especı́fico de la criptografı́a poscuántica, por lo que no lo abordaré.
Sin embargo, hay mucha investigación en criptografı́a poscuántica a medida que
se acerca la implementación.
Estén atentos a las publicaciones de la conferencia CHES:
[Link]
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
En términos de estandarización, se están llevando a cabo múltiples procesos.
El esfuerzo más prominente ha sido dirigido por el Instituto Nacional de
Estándares y Tecnologı́a de los Estados Unidos (NIST).
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
En 2016 realizaron una convocatoria abierta para propuestas de diseño de firmas
digitales post-cuánticas (DSA) y mecanismos de encapsulación de claves (KEM,
piensen en PKE)
En 2017 se presentaron 69 propuestas.
Después de múltiples rondas de revisión, en 2023 se han publicado los primeros
estándares provisionales para comentarios en
[Link]
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Se están estandarizando cuatro algoritmos:
ML-KEM: un mecanismo de encapsulación de clave basado en retı́culos propuesto
con el nombre Kyber.
ML-DSA y NT-DSA: dos esquemas de firma basados en retı́culos propuestos
como Dilithium y Falcon.
SLH-DSA: un esquema de firma basado en funciones hash conocido como
Sphincs+.
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Mientras tanto, algunos esquemas de KEM están aún en consideración como
parte del proceso original.
NIST también inició un segundo proceso exclusivamente para firmas digitales
adicionales.
Las discusiones sobre la estandarización se pueden seguir en
[Link]
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Bueno, tenemos nuevas suposiciones de dificultad, primitivas y estándares. ¿Podemos
desplegarlos ahora, verdad?
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Bueno, tenemos nuevas suposiciones de dificultad, primitivas y estándares. ¿Podemos
desplegarlos ahora, verdad?
No es tan fácil en la práctica.
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Bueno, tenemos nuevas suposiciones de dificultad, primitivas y estándares. ¿Podemos
desplegarlos ahora, verdad?
No es tan fácil en la práctica.
Los algoritmos PQC tienden a tener claves públicas y/o cifrados más grandes.
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Bueno, tenemos nuevas suposiciones de dificultad, primitivas y estándares. ¿Podemos
desplegarlos ahora, verdad?
No es tan fácil en la práctica.
Los algoritmos PQC tienden a tener claves públicas y/o cifrados más grandes.
RSA EC-DLOG PQC
Cifrado |pk| = |c| = 384 B |pk| = 32 B, |c| = 64 B
Table: Cifrados y firmas con 128-bits de seguridad.
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Bueno, tenemos nuevas suposiciones de dificultad, primitivas y estándares. ¿Podemos
desplegarlos ahora, verdad?
No es tan fácil en la práctica.
Los algoritmos PQC tienden a tener claves públicas y/o cifrados más grandes.
RSA EC-DLOG PQC
Cifrado |pk| = |c| = 384 B |pk| = 32 B, |c| = 64 B |pk| = 800 B, |c| = 768 B
Table: Cifrados y firmas con 128-bits de seguridad.
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Bueno, tenemos nuevas suposiciones de dificultad, primitivas y estándares. ¿Podemos
desplegarlos ahora, verdad?
No es tan fácil en la práctica.
Los algoritmos PQC tienden a tener claves públicas y/o cifrados más grandes.
RSA EC-DLOG PQC
Cifrado |pk| = |c| = 384 B |pk| = 32 B, |c| = 64 B |pk| = 800 B, |c| = 768 B
Firmas |pk| = |c| = 384 B |pk| = 32 B, |σ| = 65 B
Table: Cifrados y firmas con 128-bits de seguridad.
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Bueno, tenemos nuevas suposiciones de dificultad, primitivas y estándares. ¿Podemos
desplegarlos ahora, verdad?
No es tan fácil en la práctica.
Los algoritmos PQC tienden a tener claves públicas y/o cifrados más grandes.
RSA EC-DLOG PQC
Cifrado |pk| = |c| = 384 B |pk| = 32 B, |c| = 64 B |pk| = 800 B, |c| = 768 B
Firmas |pk| = |c| = 384 B |pk| = 32 B, |σ| = 65 B |pk| = 32 B, |σ| = 7856 B
Table: Cifrados y firmas con 128-bits de seguridad.
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
¿Por qué es esto un problema?
Si tu protocolo envı́a muchas claves, texto cifrado o firmas, esto conlleva un
aumento en los costos y retrasos.
Aún peor: ¿qué sucede si la implementación de tu protocolo asume tamaños fijos?
unsigned char ciphertext[64]
Una gran cantidad de código sensible requerirá ser reescrito, con todos los riesgos
que esto conlleva. (E.g., CVE-2022-21449: Firmas Psı́quicas en Java)
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
No solo hay problemas con el tamaño.
No todo problema ha recibido el mismo estudio. ¿Podrı́an romperse?
A pesar de que RSA y DLOG existen desde la década de 1970 y estándares como
PKCS #1 v1.1 datan de 1992, su criptoanálisis no se estabilizó hasta mediados de
la década de 1990 [Len93].
De la misma manera, Rainbow (un DSA finalista de NIST definido por primera
vez en 2005) fue vulnerado en 2022 [Beu22].
Y el esquema SIKE (un KEM finalista de NIST, definido en 2011) fue vulnerado
2022 [CD23].
¡Mucho trabajo en criptoanálisis por hacer!
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Pero necesitamos PQC lo antes posible!
¡Usa esquemas hı́bridos!
Para PKE: cifra con EC-ElGamal y cifra el resultado con ML-KEM
Para firmas: firma con (por ejemplo) EC-DSA y ML-DSA, verifica ambas firmas
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Conclusiones
PQC ha recibido un impulso significativo en investigación y esfuerzo industrial.
Independientemente de si QC alguna vez sucede, los requisitos legales significan
que PQC se implementará en un futuro cercano.
Actualmente se está llevando a cabo mucha investigación: problemas teóricos y
prácticos siguen abiertos, lo que brinda un buen espacio para realizar
investigaciones.
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Conclusiones
PQC ha recibido un impulso significativo en investigación y esfuerzo industrial.
Independientemente de si QC alguna vez sucede, los requisitos legales significan
que PQC se implementará en un futuro cercano.
Actualmente se está llevando a cabo mucha investigación: problemas teóricos y
prácticos siguen abiertos, lo que brinda un buen espacio para realizar
investigaciones.
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Conclusiones
PQC ha recibido un impulso significativo en investigación y esfuerzo industrial.
Independientemente de si QC alguna vez sucede, los requisitos legales significan
que PQC se implementará en un futuro cercano.
Actualmente se está llevando a cabo mucha investigación: problemas teóricos y
prácticos siguen abiertos, lo que brinda un buen espacio para realizar
investigaciones.
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Conclusiones
PQC ha recibido un impulso significativo en investigación y esfuerzo industrial.
Independientemente de si QC alguna vez sucede, los requisitos legales significan
que PQC se implementará en un futuro cercano.
Actualmente se está llevando a cabo mucha investigación: problemas teóricos y
prácticos siguen abiertos, lo que brinda un buen espacio para realizar
investigaciones.
Gracias
Diapositivas en [Link]
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas,
Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben
Chiaro, Roberto Collins, and William et al. Courtney.
Quantum supremacy using a programmable superconducting processor.
Nature, 574(7779):505–510, Oct 2019.
Ward Beullens.
Breaking rainbow takes a weekend on a laptop.
IACR Cryptol. ePrint Arch., page 214, 2022.
Wouter Castryck and Thomas Decru.
An efficient key recovery attack on sidh.
In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages
423–447. Springer, 2023.
Elizabeth Gibney.
Quantum gold rush: the private funding pouring into quantum start-ups.
Nature, 574(7776):22–24, October 2019.
Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman.
NTRU: A ring-based public key cryptosystem.
In Third Algorithmic Number Theory Symposium (ANTS), volume 1423 of LNCS, pages 267–288.
Springer, Heidelberg, June 1998.
H. W. Lenstra.
The number field sieve: An annotated bibliography.
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
In Arjen K. Lenstra and Hendrik W. Lenstra, editors, The development of the number field sieve, pages
1–3, Berlin, Heidelberg, 1993. Springer Berlin Heidelberg.
Vadim Lyubashevsky, Chris Peikert, and Oded Regev.
On ideal lattices and learning with errors over rings.
In Henri Gilbert, editor, EUROCRYPT 2010, volume 6110 of LNCS, pages 1–23. Springer, Heidelberg,
May / June 2010.
Robert J. McEliece.
A public-key cryptosystem based on algebraic coding theory.
The deep space network progress report 42-44, Jet Propulsion Laboratory, California Institute of
Technology, January/February 1978.
[Link]
Samuel K. Moore and Amy Nordrum.
Intel’s new path to quantum computing.
IEEE Spectrum, 2018.
Microsoft Quantum Team.
Developing a topological qubit.
Cloud Perspectives Blog, 2018.
Oded Regev.
On lattices, learning with errors, random linear codes, and cryptography.
In Harold N. Gabow and Ronald Fagin, editors, 37th ACM STOC, pages 84–93. ACM Press, May 2005.
Criptografı́a Pre-Cuántica Computación Cuántica Suposiciones y primitivas: un Ejemplo Implementaciones, Estandares, Depliegue Conclusion
Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, and Keita Xagawa.
Efficient public key encryption based on ideal lattices.
In Mitsuru Matsui, editor, ASIACRYPT 2009, volume 5912 of LNCS, pages 617–635. Springer,
Heidelberg, December 2009.
Karl Wehden, Ismael Faro, and Jay Gambetta.
IBM’s roadmap for building an open quantum software ecosystem.
IBM Research Blog, 2021.