¿Puede el cifrado homomórfico de Paillier manejar más de un texto plano binario?

Question

Estoy leyendo sobre el Cifrado Homomórfico de Paillier, dado aquí: https://en.wikipedia.org/wiki/Paillier_cryptosystem

Tengo dos preguntas:

1) ¿Está esto restringido a sólo dos textos planos? ¿Puedo extender las propiedades homomórficas a más de dos textos planos?

2) Consulte:

$D(E(m_1, r_1)E(m_2, r_2) \mod n^2) = m_1 + m_2 \mod n$

qué pasaría si $(m_1 + m_2) > n$ ? ¿No se perderían datos?

Answer 1

1. Esto funcionará con cualquier número de textos planos, $m=\left[m_1,\cdots ,m_k\right]$ : $$ \begin{align} D\left(E\left(m_1,r_1\right)\cdots E\left(m_k,r_k\right)\right) & = D\left(g^{m_1}r_1^N\cdots g^{m_k}r_k^N\right)\\ &=D\left(\left(g^{m_1} \cdots g^{m_k}\right)\left(r_1^N\cdots r_k^N\right)\right) \\ &=D\left(\left(g^{m_1 +\cdots + m_k}\right)\left(r_1 \cdots r_k\right)^N\right)\\ &=D\left(E\left(m_1+\cdots +m_k,r_1 \cdots r_k\right)\right)\\ &=m_1 +\cdots + m_k \end{align} $$

Podemos ver que este último paso es válido, ya que $\gcd(a,N)=1$ y $\gcd(b,N)=1\implies \gcd(ab,N)=1$ que podemos extender infinitamente.

2. Eso es correcto, si $m_1 + m_2 > N$ entonces habrá una pérdida de información. Esto se indica en la ecuación original. Para sumar números más grandes, debemos elegir un $N$