Criptografía Naccache-Stern

El criptosistema de Naccache-Stern es un criptosistema de clave pública homomórfico cuya seguridad se basa en el problema de residuosidad superior . El criptosistema de Naccache-Stern fue descubierto por David Naccache y Jacques Stern en 1998.

Definición del esquema

Al igual que muchos criptosistemas de clave pública , este esquema funciona en el grupo donde n es un producto de dos primos grandes . Este esquema es homomórfico y, por lo tanto, maleable . ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$

Generación de claves

• Elija una familia de k primos pequeños distintos p ₁ ,..., p _k .
• Divida el conjunto en dos y establezca y . ${\displaystyle u=\prod _{i=1}^{k/2}p_{i}}$ ${\displaystyle v=\prod _{k/2+1}^{k}p_{i}}$
• Colocar ${\displaystyle \sigma =uv=\prod _{i=1}^{k}p_{i}}$
• Elija primos grandes a y b tales que tanto p = 2 au +1 como q = 2 bv +1 sean primos.
• Establezca n = pq .
• Elija un g mod n aleatorio tal que g tenga orden φ( n )/4.

La clave pública son los números σ, n , g y la clave privada es el par p , q .

Cuando k = 1 este es esencialmente el criptosistema Benaloh .

Cifrado de mensajes

Este sistema permite el cifrado de un mensaje m en el grupo . ${\displaystyle \mathbb {Z} /\sigma \mathbb {Z} }$

• Elige un . ${\displaystyle x\in \mathbb {Z} /n\mathbb {Z} }$
• Calcular ${\displaystyle E(m)=x^{\sigma }g^{m}\mod n}$

Entonces E(m) es un cifrado del mensaje m .

Descifrado de mensajes

Para descifrar, primero encontramos m mod p _i para cada i , y luego aplicamos el teorema del resto chino para calcular m mod . ${\displaystyle \sigma }$

Dado un texto cifrado c , para descifrarlo, calculamos

• ${\displaystyle c_{i}\equiv c^{\phi (n)/p_{i}}\mod n}$. De este modo

${\displaystyle {\begin{matrix}c^{\phi (n)/p_{i}}&\equiv &x^{\sigma \phi (n)/p_{i}}g^{m\phi (n)/p_{i}}\mod n\\&\equiv &g^{(m_{i}+y_{i}p_{i})\phi (n)/p_{i}}\mod n\\&\equiv &g^{m_{i}\phi (n)/p_{i}}\mod n\end{matrix}}}$

dónde . ${\displaystyle m_{i}\equiv m\mod p_{i}}$

• Como se elige que p _i sea pequeño, m _{i se puede recuperar mediante una} búsqueda exhaustiva, es decir, comparando con j desde 1 hasta p i -1. ${\displaystyle c_{i}}$ ${\displaystyle g^{j\phi (n)/p_{i}}}$
• Una vez que se conoce m _i para cada i , m se puede recuperar mediante una aplicación directa del teorema del resto chino.

Seguridad

La seguridad semántica del criptosistema de Naccache-Stern se basa en una extensión del problema de residuosidad cuadrática conocido como el problema de residuosidad superior .

Referencias

Naccache, David; Stern, Jacques (1998). "Un nuevo criptosistema de clave pública basado en residuos superiores". Actas de la 5.ª Conferencia de la ACM sobre seguridad informática y de las comunicaciones . CCS '98. ACM. págs. 59–66. doi : 10.1145/288090.288106 . ISBN . 1-58113-007-4.