Computational cryptography › Public-key encryption and key exchange › Classical number theory › Factoring
PUBLIC-KEY ENCRYPTIONPrimitive

Paillier encryption

In plain words

Encryption you can do math on: add up encrypted numbers and get the encrypted total, without seeing any individual number.

The idea: Imagine sealed ballot boxes that can be merged: put two together and you get one sealed box holding the sum. With Paillier, multiplying two ciphertexts gives an encryption of the sum of their messages. A tallying server can combine all the encrypted votes into one ciphertext and hand it to the key holder, who decrypts only the total. No individual vote is ever decrypted.

Why it matters: Useful for private voting and for wallets that split one key across several devices.

The details

On the map: additively homomorphic: e-voting, aggregation

Public-key encryption where multiplying two ciphertexts adds their plaintexts: E(a) × E(b) = E(a + b)[1]. Anyone can sum encrypted votes or values without decrypting them.

Where you meet it: e-voting research, private aggregation, and threshold ECDSA wallets that split a signing key between devices[2, 3].

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

Nothing on the map depends on it: it is an end point, something people use directly.

References

  1. Pascal Paillier. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. Advances in Cryptology — EUROCRYPT ’99, 1999. doi:10.1007/3-540-48910-x_16
  2. Yehuda Lindell. Fast Secure Two-Party ECDSA Signing. Journal of Cryptology, 2021. doi:10.1007/s00145-021-09409-9
  3. Rosario Gennaro and Steven Goldfeder. Fast Multiparty Threshold ECDSA with Fast Trustless Setup. Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. doi:10.1145/3243734.3243859