Homomorphic encryption

Idea: do some useful operations, or operations, using only encrypted data.

Example: in the RSA cryptosystem with unpadded messages, multiplication of the cipher-texts corresponds to multiplication of the plaintexts.

Using a lot of processing power (and using somewhat cumbersome methods), it is possible to apply an arbitrary function (a logic function described by a boolean circuit) to the encrypted data (to know more, search for fully homomorphic encryption schemes and lattice-based cryptography).

Paillier Cryptosystem

1. Choose two large primes $p$ and $q$. Ensure that $p$ is not a factor of $q -1$, and vice-versa.

2. Compute $n = pq$ and $\lambda = lcm(p-1,q-1)$.

3. Select a random integer $g$ in the interval $]0,n^2[$ that is coprime to $n$.

4. Compute $u = g^\lambda mod n²$. It must be of the form $u = vn +1$.

5. Compute $\mu = ((u-1)/n)^{-1}mod n$.

6. The public key is $(n,g)$

7. The private key is $(\lambda, \mu)$.

8. To encrypt the plaintext $m$, with $0 \le m \lt n$, select a random $r$ such that $0 \lt r \lt n$, and compute the ciphertext $c = g^mr^n mod n²$.

9. To decrypt, compute $x = c^\lambda mod n²$, then $m = ((x-1)/n)\mu mod n$.