El criptosistema Naccache-Stern es un criptosistema homomórfico de clave pública cuya seguridad se basa en el problema de la mayor residuosidad . El criptosistema Naccache-Stern fue descubierto por David Naccache y Jacques Stern en 1998.
Definición de esquema
Como muchos criptosistemas de clave pública , este esquema funciona en el grupodonde n es un producto de dos números primos grandes . Este esquema es homomórfico y, por tanto, maleable .
Generación de claves
- Elija una familia de k pequeños primos distintos p 1 , ..., p k .
- Divida el conjunto por la mitad y coloque y .
- Colocar
- Elija números primos grandes a y b tales que tanto p = 2 au 1 y q = 2 bv 1 son primos.
- Establecer n = pq .
- Elija un g mod n aleatorio tal que g tenga el orden φ ( n ) / 4.
La clave pública son los números σ, n , gy 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.
- Elige un aleatorio .
- Calcular
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.
Dado un texto cifrado c , para descifrar, calculamos
- . Por lo tanto
dónde .
- Dado que p i se elige para que sea pequeño, m i puede recuperarse mediante una búsqueda exhaustiva, es decir, comparando a para j de 1 ap i -1.
- Una vez que se conoce m i para cada i , m puede recuperarse mediante una aplicación directa del teorema chino del resto.
Seguridad
La seguridad semántica del criptosistema 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 más altos". Actas de la 5ª Conferencia de la ACM sobre seguridad informática y de comunicaciones . CCS '98. ACM. págs. 59–66. doi : 10.1145 / 288090.288106 . ISBN 1-58113-007-4.