Introduction

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.

Try It

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">Enter two numbers (0–99), then follow the three steps. The ciphertexts are huge opaque numbers — yet multiplying them adds the originals. The inputs are never combined in the clear.</p>
<div class="inputs">
  <label>Number A <input id="aVal" type="number" min="0" max="99" value="17"></label>
  <label>Number B <input id="bVal" type="number" min="0" max="99" value="25"></label>
</div>
<div class="btns">
  <button id="btnEncrypt" type="button">1. Encrypt both</button>
  <button id="btnMul"     type="button" disabled>2. Multiply ciphertexts</button>
  <button id="btnDecrypt" type="button" disabled>3. Decrypt result</button>
  <button id="btnReset"   type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Toy Paillier with small safe primes so it runs instantly in-browser.
// Real Paillier uses 1024-2048-bit primes; the math is identical.
//
// Key: p=61, q=53 → n=3233, n²=10452289
// λ = lcm(p-1, q-1) = lcm(60,52) = 780
// g = n+1 = 3234   (canonical choice; L(g^λ mod n²)=1 ensures μ=1)
// μ = L(g^λ mod n²)^{-1} mod n  where L(x)=(x-1)/n
//
// Enc(m, r) = g^m * r^n mod n²
// Dec(c)    = L(c^λ mod n²) * μ mod n
// Hom:  Dec(c1*c2 mod n²) = m1+m2 mod n

const N  = 3233n;
const N2 = N * N;          // 10452289n
const G  = N + 1n;         // 3234n
const LAM = 780n;          // lcm(p-1, q-1) = lcm(60, 52)
const MU  = 1173n;         // modInverse(L(G^λ mod N²), N) = modInverse(780, 3233)

function modpow(base, exp, mod) {
  let result = 1n; base = base % mod;
  while (exp > 0n) {
    if (exp & 1n) result = result * base % mod;
    exp >>= 1n; base = base * base % mod;
  }
  return result;
}

function L(x) { return (x - 1n) / N; }

function encrypt(m, r) {
  // E(m, r) = g^m * r^n mod n²
  return modpow(G, m, N2) * modpow(r, N, N2) % N2;
}

function decrypt(c) {
  // D(c) = L(c^λ mod n²) * μ mod n
  return L(modpow(c, LAM, N2)) * MU % N;
}

// Secure-ish random BigInt in [2, n-1]
function randR() {
  const arr = new Uint32Array(1);
  crypto.getRandomValues(arr);
  return 2n + BigInt(arr[0]) % (N - 3n);
}

let cA, cB, cMul, rA, rB;

function row(label, value, cls='') {
  return `<div class="row ${cls}">
    <div class="label">${label}</div>
    <div class="val ${cls}">${value}</div>
  </div>`;
}

function log(html) {
  document.getElementById('log').insertAdjacentHTML('beforeend', html);
}

function setBtn(id, en) { document.getElementById(id).disabled = !en; }

document.getElementById('btnEncrypt').addEventListener('click', () => {
  const a = BigInt(+document.getElementById('aVal').value);
  const b = BigInt(+document.getElementById('bVal').value);
  if (a < 0n || a > 99n || b < 0n || b > 99n) { alert('Use values 0–99'); return; }

  rA = randR(); rB = randR();
  cA = encrypt(a, rA);
  cB = encrypt(b, rB);

  document.getElementById('log').innerHTML = '';
  log(row('Plaintext A (your input)',   String(a)));
  log(row('Plaintext B (your input)',   String(b)));
  log(row('Ciphertext E(A)  — server sees this', String(cA), 'big'));
  log(row('Ciphertext E(B)  — server sees this', String(cB), 'big'));

  setBtn('btnMul', true);
  setBtn('btnDecrypt', false);
});

document.getElementById('btnMul').addEventListener('click', () => {
  cMul = cA * cB % N2;
  log(row('E(A) × E(B) mod n²  — server’s only operation', String(cMul), 'big highlight'));
  setBtn('btnDecrypt', true);
  setBtn('btnMul', false);
});

document.getElementById('btnDecrypt').addEventListener('click', () => {
  const result = decrypt(cMul);
  const a = BigInt(+document.getElementById('aVal').value);
  const b = BigInt(+document.getElementById('bVal').value);
  const expected = (a + b) % N;
  const ok = result === expected;
  log(row(
    ok ? '✓ Decrypted result = A + B  (inputs were never revealed!)' : '✗ Unexpected result',
    String(result) + (ok ? ` = ${a} + ${b}` : ''),
    ok ? 'sum good' : 'sum'
  ));
  setBtn('btnDecrypt', false);
  console.log(fmt('Paillier demo: E(%a%)*E(%b%) mod n² => Dec => %result% (expected %expected%)', { a: a, b: b, result: result, expected: expected }));
});

document.getElementById('btnReset').addEventListener('click', () => {
  document.getElementById('log').innerHTML = '';
  setBtn('btnMul', false);
  setBtn('btnDecrypt', false);
});
Result
Console

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

The Real Complexity

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

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

Encryption of a message mm with random rr: E(m)=gm⋅rn mod n2E(m) = g^m \cdot r^n \bmod n^2.

Decryption uses the private λ\lambda to cancel the random factor and recover mm.

Why multiplication of ciphertexts adds plaintexts:

E(a)⋅E(b)=gar1n⋅gbr2n=ga+b(r1r2)n(modn2)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)E(a+b) with a fresh random factor — so decryption yields a+ba + b. The randomness rr 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 Zn2∗\mathbb{Z}_{n^2}^*, decide whether it is an nn-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 nn 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 nn.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/paillier-cryptosystem/Content licensed under CC BY-NC 4.0.