The Paillier Cryptosystem

Imagine sealing two numbers in envelopes, handing both to a stranger, and asking them to give you back a single sealed result — without ever peeking inside either envelope. When you finally open the result yourself, it holds the sum of the two originals. The stranger learned nothing.

This is not science fiction. Pascal Paillier published exactly this construction in 1999. His public-key cryptosystem is additively homomorphic: if you multiply two ciphertexts together (a simple modular multiplication), the decrypted result is the sum of the two plaintexts. The inputs are never revealed. The server doing the arithmetic learns nothing.

The magic rests on a number-theoretic trapdoor called the Decisional Composite Residuosity (DCR) assumption — a problem believed to be hard even for powerful computers. Unlike RSA, which builds hardness from factoring, Paillier builds it from a subtler property of modular arithmetic, one that also happens to carry addition through encryption for free.

Pick any two numbers, then press Encrypt both. The demo encrypts each one with a small set of Paillier parameters (toy key, real math). Press Multiply ciphertexts — that single modular multiplication on the encrypted side is all the arithmetic the server ever does. Then press Decrypt result and watch the sum appear. The two original inputs were never combined in the clear.

<p class="hint">{{hint}}</p>
<div class="inputs">
  <label>{{label_a}} <input id="aVal" type="number" min="0" max="99" value="17"></label>
  <label>{{label_b}} <input id="bVal" type="number" min="0" max="99" value="25"></label>
</div>
<div class="btns">
  <button id="btnEncrypt" type="button">{{btn_encrypt}}</button>
  <button id="btnMul"     type="button" disabled>{{btn_mul}}</button>
  <button id="btnDecrypt" type="button" disabled>{{btn_decrypt}}</button>
  <button id="btnReset"   type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="log" id="log"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 15px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.inputs { display: flex; gap: 1rem; margin-bottom: .8rem; flex-wrap: wrap; }
.inputs label { display: flex; flex-direction: column; font-size: .85rem; font-weight: 600;
                color: #1d3557; gap: .2rem; }
.inputs input { width: 80px; padding: .3rem .5rem; border: 1px solid #adb1b8;
                border-radius: 6px; font-size: 1rem; text-align: center; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .9rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .8rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button:disabled { opacity: .4; cursor: default; }
button.ghost { background: #fff; color: #1d3557; }
.log { display: flex; flex-direction: column; gap: .55rem; }
.row { background: #f0f4f8; border-radius: 8px; padding: .55rem .75rem;
       border-left: 3px solid #1d3557; }
.row.good { border-color: #0a7d33; }
.row.highlight { border-color: #e07b00; background: #fef9f0; }
.label { font-size: .75rem; font-weight: 700; color: #555; text-transform: uppercase;
         letter-spacing: .05em; margin-bottom: .18rem; }
.val { font: 700 13px ui-monospace, monospace; word-break: break-all; color: #1d3557; }
.val.big { color: #8b2500; }
.val.sum  { color: #0a7d33; font-size: 1.1rem; }

// Code not found

Notice the asymmetry. The server sees only big opaque numbers — the ciphertexts — and multiplies them modulo $n^2$. It learns nothing about the plaintexts. Yet when you decrypt with the private key, the arithmetic you asked for has already been done: $\text{Dec}(E(a) \cdot E(b) \bmod n^2) = a + b \pmod{n}$. That equation is the whole point of homomorphic encryption.

How secure is Paillier, really? And how does the homomorphic trick work mathematically?

The key generation picks two large primes $p$ and $q$, sets $n = pq$ and $n^2$ as the working modulus. The public key is $(n, g)$ where $g$ is a carefully chosen element of $\mathbb{Z}_{n^2}^*$. The private key is $\lambda = \text{lcm}(p-1, q-1)$.

Encryption of a message $m$ with random $r$: $E(m) = g^m \cdot r^n \bmod n^2$.

Decryption uses the private $\lambda$ to cancel the random factor and recover $m$.

Why multiplication of ciphertexts adds plaintexts:

$$E(a) \cdot E(b) = g^a r_1^n \cdot g^b r_2^n = g^{a+b}(r_1 r_2)^n \pmod{n^2}$$

This is just $E(a+b)$ with a fresh random factor — so decryption yields $a + b$. The randomness $r$ is what makes the scheme semantically secure: encrypting the same plaintext twice gives different ciphertexts, so an eavesdropper can't tell when two messages are equal.

The security assumption is the Decisional Composite Residuosity (DCR) problem: given a random element of $\mathbb{Z}_{n^2}^*$, decide whether it is an $n$-th power residue. This is believed hard — no polynomial-time classical algorithm is known. Note: unlike factoring, no quantum speedup for DCR is known either, though Paillier's reliance on the difficulty of factoring $n$ means a large quantum computer could still break it via Shor's algorithm.

The status: Paillier (1999) is a proven construction — its semantic security reduces to DCR under chosen-plaintext attack. It is not "open" or "conjectured hard" in the same way as P vs NP; it is a concrete security proof, contingent on the hardness of DCR and the difficulty of factoring $n$.

"Compute on data without seeing it" is one of the most wanted primitives in modern privacy engineering, and Paillier is one of the most practical ways to get it:

• Private electronic voting: each voter encrypts their ballot; the server tallies by multiplying ciphertexts; a threshold of trustees decrypts only the final sum. Individual votes are never revealed.
• Federated learning: devices encrypt local model updates; a central server aggregates the ciphertexts; only the combined gradient is decrypted. No individual device's data is exposed.
• Secure multiparty computation: parties can jointly compute aggregate statistics — salary surveys, health data studies — without a trusted third party ever seeing individual values.
• Genomic privacy: hospitals sum allele counts across encrypted patient records to run population-scale studies without sharing raw genotypes.
• Financial auditing: a bank can prove the sum of a set of encrypted transactions meets a threshold without revealing individual amounts.

Paillier is not a cure-all: it supports only addition natively (you can also multiply a ciphertext by a plaintext constant). Fully general computation on encrypted data requires fully homomorphic encryption (FHE) — a far heavier tool. Paillier's simplicity and efficiency make it the go-to choice whenever addition is enough.

Pascal Paillier's 1999 scheme is a small miracle of mathematical engineering: a public-key system where the operation of multiplying two ciphertexts secretly adds the underlying numbers, with provable security resting on a well-studied number-theoretic assumption.

It is not magic — the security still depends on the difficulty of factoring and of the DCR problem, and a large quantum computer would break it. But for classical adversaries, and for the applications that need only addition, Paillier remains one of the most elegant and widely deployed privacy-preserving tools we have.

The next time you vote in a cryptographically private election, or your phone contributes to a federated model without sending its raw data, there is a good chance that somewhere in the pipeline, two big numbers were quietly multiplied together — and their secrets added up exactly as intended.