Criptosistema de mochila Naccache-Stern

El criptosistema de la mochila de Naccache-Stern es un criptosistema de clave pública atípico desarrollado por David Naccache y Jacques Stern en 1997. Este criptosistema es determinista y, por lo tanto, no es semánticamente seguro . Si bien hasta la fecha no ha sido vulnerado, este sistema tampoco cuenta con seguridad demostrable .

Descripción general del sistema

Este sistema se basa en un tipo de problema de la mochila . Específicamente, el problema subyacente es este: dados los enteros c , n , p y v0 _, ..., vn _, encontrar un vector $x\in \{0,1\}^{n}$ de tal manera que

c\equiv \prod _{i=0}^{n}v_{i}^{x_{i}}\mod p

La idea es que cuando los v _i son primos relativos y mucho menores que el módulo p, este problema se puede resolver fácilmente. Es esta observación la que permite el descifrado.

Generación de claves

Para generar un par de claves pública/privada

Elija un módulo primo grande p .
Elija un entero positivo n y para i desde 0 hasta n , establezca p _i como el i -ésimo primo, comenzando con p ₀ = 2 y tal que $\prod _{i=0}^{n}p_{i}<p$ .
Elige un número entero secreto s < p -1, tal que mcd( p -1, s ) = 1.
Colocar $v_{i}={\sqrt[{s}]{p_{i}}}\mod p$ .

La clave pública es entonces p , n y v ₀ ,..., v _n . La clave privada es s .

Cifrado

Para cifrar un mensaje m de n bits de longitud , calcule

c=\prod _{i=0}^{n}v_{i}^{m_{i}}\mod p

donde m _i es el i- ésimo bit del mensaje m .

Descifrado

Para descifrar un mensaje c , calcule

m=\sum _{i=0}^{n}{\frac {2^{i}}{p_{i}-1}}\times \left(\gcd(p_{i},c^{s}\mod p)-1\right)

Esto funciona porque la fracción

{\frac {\gcd(p_{i},c^{s}\mod p)-1}{p_{i}-1}}

es 0 o 1 dependiendo de si p _i divide a c ^s mod p .

Seguridad

La seguridad de la función de puerta trasera se basa en la dificultad del siguiente problema de la mochila multiplicativa : dado $c=\prod _{i=0}^{n}v_{i}^{m_{i}}{\pmod {p}},$ recuperar el $m_{i}$ A diferencia de los criptosistemas aditivos basados en el problema de la mochila, como Merkle-Hellman , técnicas como la reducción de retículos euclidianos no se aplican a este problema.

El ataque genérico más conocido consiste en resolver el problema del logaritmo discreto para recuperar $s$ de $p,p_{i},v_{i}$ lo cual se considera difícil para una computadora clásica. Sin embargo, el algoritmo cuántico de Shor resuelve este problema de manera eficiente. Además, actualmente (2023), no existe prueba de que el problema de la mochila de Naccache-Stern se reduzca al problema del logaritmo discreto.

El ataque específico más conocido (en 2018) utiliza el teorema del cumpleaños para invertir parcialmente la función sin conocer la puerta trasera, suponiendo que el mensaje tiene un peso de Hamming muy bajo . ^{[ 1 ]}

Referencias

↑ Anastasiadis, M.; Chatzis, N.; Draziotis, KA (octubre de 2018). "Ataques de tipo cumpleaños al criptosistema de mochila Naccache-Stern". Information Processing Letters . 138 : 39–43 . doi : 10.1016/j.ipl.2018.06.002 .

Documento original
Mejora reciente del ancho de banda

Véase también

[1] Anastasiadis, M.; Chatzis, N.; Draziotis, KA (octubre de 2018). "Ataques de tipo cumpleaños al criptosistema de mochila Naccache-Stern". Information Processing Letters . 138 : 39–43 . doi : 10.1016/j.ipl.2018.06.002 .

[ 1 ]