El criptosistema Benaloh es una extensión del criptosistema (GM) Goldwasser-Micali creado en 1985 por Josh (Cohen) Benaloh. La principal mejora del criptosistema Benaloh sobre GM es que los bloques de datos más largos se pueden cifrar a la vez, mientras que en GM cada bit se cifra individualmente. [1] [2] [3]
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
Dado el tamaño de bloque r , se genera un par de claves pública / privada de la siguiente manera:
- Elija grandes números primos p y q tal que y
- Colocar
- Escoger tal que .
- Nota: Si r es compuesto, Fousse et al. en 2011 [4] que las condiciones anteriores (es decir, las establecidas en el documento original) son insuficientes para garantizar un correcto descifrado, es decir, para garantizar que en todos los casos (como debería ser el caso). Para abordar esto, los autores proponen la siguiente verificación: dejemos ser la factorización prima de r . Escoger tal que para cada factor , es el caso que .
- Colocar
La clave pública es entonces , y la clave privada es .
Cifrado de mensajes
Para cifrar el mensaje :
- Elige un aleatorio
- Colocar
Descifrado de mensajes
Para descifrar un texto cifrado :
- Calcular
- Producción , es decir, encuentre m tal que
Para comprender el descifrado, primero observe que para cualquier y tenemos:
Para recuperar m de a , tomamos el logaritmo discreto de una base x . Si r es pequeño, podemos recuperar m mediante una búsqueda exhaustiva, es decir, comprobando si para todos . Para valores mayores de r , el algoritmo de pasos gigantes de Baby-step se puede utilizar para recuperar m en tiempo y espacio.
Seguridad
La seguridad de este restos esquema sobre el problema residuosity Superior , específicamente, dado z , r y n donde la factorización de n es desconocido, es computacionalmente imposible determinar si z es un r º mod residuo n , es decir, si existe un x tal que.
Referencias
- ^ Cohen, Josh; Ficsher, Michael (1985). Un esquema electoral robusto y verificable, criptográficamente seguro (PDF) . Actas del 26º Simposio del IEEE sobre fundamentos de la informática. págs. 372–382.
- ^ Benaloh, Josh (1987). Elecciones verificables con boleta secreta (tesis de doctorado) (PDF) .
- ^ Benaloh, Josh (1994). Cifrado probabilístico denso (PDF) . Taller sobre áreas seleccionadas de criptografía. págs. 120-128.
- ^ Fousse, Laurent; Lafourcade, Pascal; Alnuaimi, Mohamed (2011). "Cifrado probabilístico denso de Benaloh revisitado". arXiv : 1008.2991 [ cs.CR ].