Criptosistema de Paillier

Algoritmo para criptografía de clave pública

El criptosistema de Paillier , inventado por Pascal Paillier en 1999 y que lleva su nombre, es un algoritmo asimétrico probabilístico para criptografía de clave pública . Se cree que el problema de calcular las clases de residuos n -ésimos 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 sólo 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}}$

Algoritmo

El esquema funciona de la siguiente manera:

Generación de claves

1. Elija dos números primos grandes y de forma aleatoria e independiente entre sí de modo que . Esta propiedad se garantiza si ambos primos tienen la misma longitud. ^[1] ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle \gcd(pq,(p-1)(q-1))=1}$
2. Calcular y . mcm significa mínimo común múltiplo . ${\displaystyle n=pq}$ ${\displaystyle \lambda =\operatorname {lcm} (p-1,q-1)}$
3. Seleccione un entero aleatorio donde ${\displaystyle g}$ ${\displaystyle g\in \mathbb {Z} _{n^{2}}^{*}}$
4. Asegúrese de dividir el orden de comprobando la existencia del siguiente inverso multiplicativo modular : , ${\displaystyle n}$ ${\displaystyle g}$ ${\displaystyle \mu =(L(g^{\lambda }{\bmod {n}}^{2}))^{-1}{\bmod {n}}}$

donde la función se define como . ${\displaystyle L}$ ${\displaystyle L(x)={\frac {x-1}{n}}}$

Nótese que la notación no denota la multiplicación modular de por el inverso multiplicativo modular de sino más bien el cociente de dividido por , es decir, el valor entero más grande para satisfacer la relación . ${\displaystyle {\frac {a}{b}}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle v\geq 0}$ ${\displaystyle a\geq vb}$

• La clave pública (de cifrado) es . ${\displaystyle (n,g)}$
• La clave privada (de descifrado) es ${\displaystyle (\lambda ,\mu ).}$

Si se utiliza p,q de longitud equivalente, una variante más simple de los pasos de generación de clave anteriores sería establecer y , donde . ^[1] La variante más simple se recomienda para fines de implementación, porque en la forma general el tiempo de cálculo de puede ser muy alto con primos p,q suficientemente grandes. ${\displaystyle g=n+1,\lambda =\varphi (n),}$ ${\displaystyle \mu =\varphi (n)^{-1}{\bmod {n}}}$ ${\displaystyle \varphi (n)=(p-1)(q-1)}$ ${\displaystyle \mu }$

Encriptación

1. Sea un mensaje a cifrar donde ${\displaystyle m}$ ${\displaystyle 0\leq m<n}$
2. Seleccione aleatorio donde y . (Nota: si encuentra un valor que tiene , puede usarlo para calcular la clave privada: es lo suficientemente improbable como para ignorarlo). ${\displaystyle r}$ ${\displaystyle 0<r<n}$ ${\displaystyle \gcd(r,n)=1}$
   ${\displaystyle \gcd(r,n)\neq 1}$
3. Calcular el texto cifrado como: ${\displaystyle c=g^{m}\cdot r^{n}{\bmod {n}}^{2}}$

Descifrado

1. Sea el texto cifrado a descifrar, donde ${\displaystyle c}$ ${\displaystyle c\in \mathbb {Z} _{n^{2}}^{*}}$
2. Calcular el mensaje de texto simple como: ${\displaystyle m=L(c^{\lambda }{\bmod {n}}^{2})\cdot \mu {\bmod {n}}}$

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

Propiedades homomorfas

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

• Adición homomórfica de textos simples

El producto de dos textos cifrados se descifrará como la suma de sus textos simples correspondientes.

${\displaystyle D(E(m_{1},r_{1})\cdot E(m_{2},r_{2}){\bmod {n}}^{2})=m_{1}+m_{2}{\bmod {n}}.\,}$

El producto de un texto cifrado con un aumento de texto simple se descifrará como la suma de los textos simples correspondientes. ${\displaystyle g}$

${\displaystyle D(E(m_{1},r_{1})\cdot g^{m_{2}}{\bmod {n}}^{2})=m_{1}+m_{2}{\bmod {n}}.\,}$

• Multiplicación homomórfica de textos claros

Un texto cifrado elevado a la potencia de un texto simple se descifrará como el producto de los dos textos simples.

${\displaystyle D(E(m_{1},r_{1})^{m_{2}}{\bmod {n}}^{2})=m_{1}m_{2}{\bmod {n}},\,}$

${\displaystyle D(E(m_{2},r_{2})^{m_{1}}{\bmod {n}}^{2})=m_{1}m_{2}{\bmod {n}}.\,}$

De manera más general, un texto cifrado elevado a una constante k se descifrará como el producto del texto simple y la constante,

${\displaystyle D(E(m_{1},r_{1})^{k}{\bmod {n}}^{2})=km_{1}{\bmod {n}}.\,}$

Sin embargo, dados los cifrados de Paillier de dos mensajes, no se conoce ninguna forma de calcular un cifrado del producto de estos mensajes sin conocer la clave privada.

Fondo

El criptosistema de Paillier aprovecha el hecho de que ciertos logaritmos discretos pueden calcularse fácilmente.

Por ejemplo, por el teorema del binomio ,

${\displaystyle (1+n)^{x}=\sum _{k=0}^{x}{x \choose k}n^{k}=1+nx+{x \choose 2}n^{2}+{\text{higher powers of }}n}$

Esto indica que:

${\displaystyle (1+n)^{x}\equiv 1+nx{\pmod {n^{2}}}}$

Por lo tanto, si:

${\displaystyle y=(1+n)^{x}{\bmod {n}}^{2}}$

entonces

${\displaystyle x\equiv {\frac {y-1}{n}}{\pmod {n}}}$.

De este modo:

${\displaystyle L((1+n)^{x}{\bmod {n}}^{2})\equiv x{\pmod {n}}}$,

donde la función se define como (cociente de división de enteros) y . ${\displaystyle L}$ ${\displaystyle L(u)={\frac {u-1}{n}}}$ ${\displaystyle x\in \mathbb {Z} _{n}}$

Seguridad semántica

El criptosistema original que se muestra arriba sí proporciona seguridad semántica contra ataques de texto simple elegido ( IND-CPA ). La capacidad de distinguir con éxito el texto cifrado de desafío equivale esencialmente a la capacidad de decidir la residuosidad compuesta. Se cree que el llamado supuesto de residuosidad compuesta decisional (DCRA) es intratable.

Sin embargo, debido a las propiedades homomórficas mencionadas anteriormente, el sistema es maleable y, por lo tanto, no disfruta del nivel más alto de seguridad semántica, protección contra ataques de texto cifrado seleccionado adaptativo ( IND-CCA2 ). Por lo general, en criptografía, la noción de maleabilidad no se considera una "ventaja", pero en ciertas aplicaciones, como la votación electrónica segura y los criptosistemas de umbral , esta propiedad puede ser necesaria.

Sin embargo, Paillier y Pointcheval propusieron un criptosistema mejorado que incorpora el hash combinado del mensaje m con r aleatorio . De forma similar al criptosistema Cramer-Shoup , el hash impide que un atacante, dado solo c, pueda cambiar m de forma significativa. A través de esta adaptación, se puede demostrar que el esquema mejorado es seguro según IND-CCA2 en el modelo de oráculo aleatorio .

Aplicaciones

Votación electrónica

La seguridad semántica no es la única consideración. Existen situaciones en las que la maleabilidad puede ser deseable. Los sistemas de votación electrónica segura pueden utilizar las propiedades homomórficas anteriores. Consideremos un voto binario simple ("a favor" o "en contra"). Supongamos que m votantes emiten un voto de 1 (a favor) o 0 (en contra). Cada votante encripta su elección antes de emitir su voto. El funcionario electoral toma el producto de los m votos encriptados y luego desencripta el resultado y obtiene el valor n , que es la suma de todos los votos. El funcionario electoral entonces sabe que n personas votaron a favor y mn personas votaron en contra . El papel del r aleatorio asegura que dos votos equivalentes se encriptarán al mismo valor solo con una probabilidad insignificante, asegurando así la privacidad del votante.

Dinero electrónico

Otra característica mencionada en el artículo es la noción de autocegamiento . Se trata de la capacidad de cambiar un texto cifrado por otro sin cambiar el contenido de su descifrado. Esto tiene aplicación en el desarrollo del dinero electrónico , un esfuerzo encabezado originalmente por David Chaum . Imagine pagar un artículo en línea sin que el vendedor necesite saber su número de tarjeta de crédito y, por lo tanto, su identidad. El objetivo tanto del dinero electrónico como del voto electrónico es garantizar que la moneda electrónica (y también el voto electrónico) sea válida, sin revelar al mismo tiempo la identidad de la persona con la que está asociada en ese momento.

Subasta electrónica

El criptosistema de Paillier desempeña un papel crucial en la mejora de la seguridad de las subastas electrónicas . Previene actividades fraudulentas, como subastadores deshonestos y colusiones entre postores y subastadores que manipulan las ofertas. Al garantizar la confidencialidad de los valores reales de las ofertas y revelar los resultados de las subastas, el criptosistema de Pailler promueve con éxito las prácticas justas. ^[3]

Criptosistema de umbral

La propiedad homomórfica del criptosistema de Paillier se utiliza a veces para construir la firma ECDSA de umbral . ^[4]

Véase también

• El criptosistema Naccache-Stern y el criptosistema Okamoto-Uchiyama son antecedentes históricos de Paillier.
• El criptosistema Damgård-Jurik es una generalización de Paillier.

Referencias

• Paillier, Pascal (1999). "Sistemas criptográficos de clave pública basados ​​en clases de residuosidad de grado compuesto" (PDF) . Avances en criptología – EUROCRYPT '99. EUROCRYPT . Springer. doi :10.1007/3-540-48910-X_16.
• Paillier, Pascal; Pointcheval, David (1999). "Sistemas criptográficos de clave pública eficientes que son demostrablemente seguros contra adversarios activos". ASIACRYPT . Springer. págs. 165–179. doi : 10.1007/978-3-540-48000-6_14 .
• Paillier, Pascal (1999). Criptosistemas basados ​​en residuosidad compuesta (tesis doctoral). Escuela Nacional Superior de Telecomunicaciones.
• Paillier, Pascal (2002). "Criptografía basada en residuosidad compuesta: una descripción general" (PDF) . CryptoBytes . 5 (1). Archivado desde el original (PDF) el 20 de octubre de 2006.

Notas

1. Jonathan Katz, Yehuda Lindell, "Introducción a la criptografía moderna: principios y protocolos", Chapman & Hall/CRC, 2007
2. Paillier, Pascal (1999). "Sistemas criptográficos de clave pública basados ​​en clases de residuosidad de grado compuesto". Avances en criptología — EUROCRYPT '99 . Apuntes de clase en informática. Vol. 1592. Springer. págs. 223–238. doi : 10.1007/3-540-48910-X_16 . ISBN 978-3-540-65889-4.
3. Pan, M., Sun, J. y Fang, Y. (2011). Purging the Back-Room Dealing: Secure Spectrum Auction Leveraging Paillier Cryptosystem [Depuración de los negocios clandestinos: subasta segura de espectro que aprovecha el criptosistema Paillier]. IEEE Journal on Selected Areas in Communications, 29(4), 866–876. https://doi.org/10.1109/JSAC.2011.110417
4. Canetti, Ran; Gennaro, Rosario; Goldfeder, Steven; Makriyannis, Nikolaos; Peled, Udi (30 de octubre de 2020). "UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts". Actas de la Conferencia ACM SIGSAC de 2020 sobre seguridad informática y de las comunicaciones . Association for Computing Machinery. págs. 1769–1787. doi :10.1145/3372297.3423367. ISBN . 9781450370899. Número de identificación del sujeto  226228099.

Enlaces externos

• El Proyecto de Cifrado Homomórfico implementa el criptosistema Paillier junto con sus operaciones homomórficas.
• Encounter: una biblioteca de código abierto que proporciona una implementación del criptosistema Paillier y una construcción de contadores criptográficos basada en el mismo.
• python-paillier es una biblioteca para cifrado parcialmente homomórfico en Python, que incluye soporte completo para números de punto flotante.
• El simulador interactivo del criptosistema Paillier Archivado el 18 de febrero de 2012 en Wayback Machine demuestra una aplicación de votación.
• Una demostración interactiva del criptosistema Paillier.
• Una implementación de Javascript de prueba de concepto del criptosistema Paillier con una demostración interactiva.
• Un vídeo de Googletechtalk sobre la votación mediante métodos criptográficos.
• Una implementación en Ruby de la adición homomórfica de Paillier y un protocolo de prueba de conocimiento cero (documentación)