Criptosistema Paillier

1. Elige dos números primos grandes.${\displaystyle p}$y${\displaystyle q}$de forma aleatoria e independiente entre sí, de tal manera que${\displaystyle \gcd(pq,(p-1)(q-1))=1}$Esta propiedad se garantiza si ambos números primos tienen la misma longitud. ^{[ 1 ]}
2. Calcular${\displaystyle n=pq}$y${\displaystyle \lambda =\operatorname {lcm} (p-1,q-1)}$. lcm significa Mínimo Común Múltiplo .
3. Seleccione un número entero aleatorio.${\displaystyle g}$dónde${\displaystyle g\in \mathbb {Z} _{n^{2}}^{*}}$
4. Asegurar${\displaystyle n}$divide el orden de${\displaystyle g}$comprobando la existencia del siguiente inverso multiplicativo modular :${\displaystyle \mu =(L(g^{\lambda }{\bmod {n}}^{2}))^{-1}{\bmod {n}}}$,

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

Tenga en cuenta que la notación${\displaystyle {\frac {a}{b}}}$no denota la multiplicación modular de${\displaystyle a}$veces el inverso multiplicativo modular de${\displaystyle b}$sino más bien el cociente de${\displaystyle a}$dividido por${\displaystyle b}$, es decir, el mayor valor entero${\displaystyle v\geq 0}$para satisfacer la relación${\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 utilizan p y q de longitud equivalente, una variante más sencilla de los pasos de generación de claves anteriores sería establecer${\displaystyle g=n+1,\lambda =\varphi (n),}$y${\displaystyle \mu =\varphi (n)^{-1}{\bmod {n}}}$, dónde${\displaystyle \varphi (n)=(p-1)(q-1)}$. ^{[ 1 ]} Se recomienda la variante más simple para fines de implementación, porque en la forma general el tiempo de cálculo de${\displaystyle \mu }$puede ser muy alto con primos p,q suficientemente grandes.

1. Dejar${\displaystyle m}$ser un mensaje para ser cifrado donde${\displaystyle 0\leq m<n}$
2. Seleccionar al azar${\displaystyle r}$dónde${\displaystyle 0<r<n}$y ${\displaystyle \gcd(r,n)=1}$. (Nota: si encuentra un valor que tenga${\displaystyle \gcd(r,n)\neq 1}$Puedes usar esto para calcular la clave privada: es lo suficientemente improbable como para ignorarlo.
3. Calcula el texto cifrado como:${\displaystyle c=g^{m}\cdot r^{n}{\bmod {n}}^{2}}$

1. Dejar${\displaystyle c}$sea ​​el texto cifrado a descifrar, donde${\displaystyle c\in \mathbb {Z} _{n^{2}}^{*}}$
2. Calcula el mensaje en texto plano de la siguiente manera:${\displaystyle m=L(c^{\lambda }{\bmod {n}}^{2})\cdot \mu {\bmod {n}}}$

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

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

• Suma homomórfica de textos planos

El producto de dos textos cifrados se descifrará como la suma de sus textos planos 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 texto plano que genera${\displaystyle g}$se descifrará como la suma de los textos planos correspondientes,

${\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 planos

Un texto cifrado elevado a la potencia de un texto plano se descifrará como el producto de los dos textos planos,

${\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}}.\,}$

En términos más generales, un texto cifrado elevado a una constante k se descifrará como el producto del texto plano y la constante.

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

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

El criptosistema Paillier aprovecha el hecho de que ciertos logaritmos discretos se pueden calcular 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{potencias superiores de }}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 función${\displaystyle L}$se define como${\displaystyle L(u)={\frac {u-1}{n}}}$(cociente de división entera) y${\displaystyle x\in \mathbb {Z} _{n}}$.

El criptosistema original, tal como se muestra arriba, proporciona seguridad semántica contra ataques de texto plano elegido ( IND-CPA ). La capacidad de distinguir con éxito el texto cifrado de desafío equivale esencialmente a la capacidad de determinar la resiliencia compuesta. Se cree que la denominada suposición de resiliencia compuesta decisional (DCRA) es intratable.

Debido a las propiedades homomórficas mencionadas, el sistema es maleable y, por lo tanto, no ofrece el máximo nivel de seguridad semántica ni protección contra ataques adaptativos de texto cifrado elegido ( IND-CCA2 ). En criptografía, la maleabilidad no suele considerarse una ventaja, pero en ciertas aplicaciones, como la votación electrónica segura y los criptosistemas de umbral , esta propiedad puede resultar necesaria.

Sin embargo, Paillier y Pointcheval propusieron un criptosistema mejorado que incorpora el hash combinado del mensaje m con un valor aleatorio r . Similar en su propósito al criptosistema Cramer-Shoup , el hash impide que un atacante, conociendo solo c, pueda modificar m de manera significativa. Mediante esta adaptación, se puede demostrar que el esquema mejorado es seguro frente a ataques IND-CCA2 en el modelo de oráculo aleatorio .