Criptosistema Paillier

El criptosistema Paillier , inventado y nombrado en honor a Pascal Paillier en 1999, es un algoritmo asimétrico probabilístico para la criptografía de clave pública . Se cree que el problema de calcular n -ésimas clases de residuos es computacionalmente difícil. El supuesto de residuosidad compuesta decisional es la hipótesis de intratabilidad en la que se basa este criptosistema.

El esquema es un criptosistema homomórfico aditivo ; esto significa que, dada solo la clave pública y el cifrado de y , se puede calcular el cifrado de . ${\ Displaystyle m_ {1}}$ ${\ Displaystyle m_ {2}}$ ${\ Displaystyle m_ {1} + m_ {2}}$

Si usa p, q de longitud equivalente, una variante más simple de los pasos de generación de claves anteriores sería establecer y , donde . ^[1] ${\ Displaystyle g = n + 1, \ lambda = \ varphi (n),}$ ${\ Displaystyle \ mu = \ varphi (n) ^ {- 1} {\ bmod {n}}}$ ${\ Displaystyle \ varphi (n) = (p-1) (q-1)}$

Como señala el artículo original , el descifrado es "esencialmente un módulo de exponenciación ". ${\ Displaystyle n ^ {2}}$

Una característica notable del criptosistema Paillier son sus propiedades homomórficas junto con su cifrado no determinista (consulte Voto electrónico en Aplicaciones para conocer su uso). Como la función de cifrado es aditivamente homomórfica, se pueden describir las siguientes identidades:

Sin embargo, dadas las encriptaciones de Paillier de dos mensajes, no existe una forma conocida de calcular una encriptación del producto de estos mensajes sin conocer la clave privada.