Introduction
Want to see arithmetic performed on encrypted data without decrypting it first? This tool implements the Paillier cryptosystem, a partially homomorphic encryption scheme that supports addition and scalar multiplication directly on ciphertexts. Set two plaintext values, encrypt them, multiply the ciphertexts to add the plaintexts, and decrypt the result to verify. Everything runs in your browser using BigInt arithmetic. No data leaves your device.
What this tool does
- Generate Paillier key pairs from small primes (preset sizes or custom primes you provide), with full key generation step output showing n, g, lambda, and mu
- Encrypt two plaintext integers m1 and m2 using the Paillier formula c = g^m * r^n mod n^2, with a random r for each encryption
- Perform homomorphic addition: multiply two ciphertexts modulo n^2 to get an encryption of m1 + m2, then decrypt to verify
- Perform homomorphic scalar multiplication: raise a ciphertext to the power k modulo n^2 to get an encryption of m1 * k, then decrypt to verify
- Display the full computation trace: individual ciphertexts, their decryptions, the homomorphic operation result, and whether it matches the expected plaintext value
- Run entirely client-side using JavaScript BigInt arithmetic, with no server calls or external libraries
How this tool works
The tool implements the Paillier cryptosystem using JavaScript BigInt for arbitrary-precision arithmetic. Key generation takes two primes p and q and computes n = p * q, n^2 = n * n, g = n + 1 (a valid generator), lambda = lcm(p-1, q-1), and mu = L(g^lambda mod n^2)^(-1) mod n, where L(x) = (x - 1) / n. The tool offers three preset prime pairs (tiny, small, medium) or custom primes you enter.
Encryption follows the Paillier formula: c = g^m * r^n mod n^2, where m is the plaintext (must be in [0, n)) and r is a random value coprime to n. The tool generates a fresh random r for each encryption. Decryption computes m = L(c^lambda mod n^2) * mu mod n.
The homomorphic operations are where Paillier shines. To add two encrypted values, you multiply their ciphertexts modulo n^2: c_add = c1 * c2 mod n^2. Decrypting c_add yields m1 + m2 mod n. To multiply an encrypted value by a scalar k, you raise the ciphertext to the power k: c_scalar = c1^k mod n^2. Decrypting c_scalar yields m1 * k mod n. The tool performs both operations and verifies the decrypted results match the expected plaintext values.
The tool auto-generates a key on mount and whenever you change the prime preset or custom primes. The output panel shows the full key, key generation steps, individual encryptions and decryptions, the homomorphic addition result with a match confirmation, and the scalar multiplication result with a match confirmation.
How Paillier homomorphic encryption works (Paillier 1999)
The Paillier cryptosystem was introduced by Pascal Paillier in his 1999 paper Public-Key Cryptosystems Based on Composite Degree Residuosity Classes, presented at EUROCRYPT '99. It is an additively homomorphic encryption scheme, meaning the sum of two plaintexts can be computed from their ciphertexts without decryption.
The scheme works over the group Z_{n^2}^*, where n = p * q is an RSA modulus. The key insight is that raising g = n + 1 to the power m modulo n^2 produces a value that encodes m in a recoverable way: (n+1)^m = 1 + m*n mod n^2. The random term r^n blinds this encoding so that the same plaintext produces different ciphertexts each time (semantic security).
The homomorphic properties follow from the algebraic structure. Multiplying two ciphertexts adds the exponents: g^{m1} * r1^n * g^{m2} * r2^n = g^{m1+m2} * (r1*r2)^n mod n^2. Raising a ciphertext to the power k multiplies the exponent: (g^{m1} * r1^n)^k = g^{m1*k} * (r1^k)^n mod n^2. Both operations preserve the ciphertext structure, so decryption recovers the correct result.
Paillier is called 'partially homomorphic' because it supports addition (and scalar multiplication, which is repeated addition) but not multiplication of two ciphertexts. You can compute E(m1) * E(m2) = E(m1 + m2), but you cannot compute E(m1 * m2) from E(m1) and E(m2) alone. A 'fully homomorphic' encryption (FHE) scheme supports both addition and multiplication of ciphertexts.
Fully homomorphic encryption was first constructed by Craig Gentry in his 2009 PhD thesis Fully Homomorphic Encryption Using Ideal Lattices. Gentry's breakthrough used bootstrapping (homomorphically evaluating the decryption circuit) to reduce noise accumulation. Modern FHE schemes (BFV, CKKS, BGV) are based on the learning with errors (LWE) problem and are used in privacy-preserving machine learning, encrypted databases, and secure multiparty computation. See the Post-Quantum Playground for the LWE problem visualization.
Paillier is used in practice for e-voting (Benaloh, Helios), privacy-preserving data aggregation, and secure multiparty computation where only additive homomorphism is needed. It is simpler and faster than FHE schemes, making it practical for applications that do not require multiplication of ciphertexts.
How to use this tool
- Select a prime preset (Tiny, Small, or Medium) or toggle to custom primes and enter your own p and q (both must be prime, and gcd(p*q, (p-1)*(q-1)) must be 1)
- Enter two plaintext integers m1 and m2 in the message fields. Values must be in [0, n) where n = p * q
- Enter a scalar k for the scalar multiplication demonstration
- Click Regenerate Key if you changed primes, or the key auto-generates when you change the preset
- Read the output: the tool shows the key components, encryption of m1 and m2, and their individual decryptions (which should match m1 and m2)
- Check the Homomorphic Addition section: Decrypt(E(m1) * E(m2)) should equal m1 + m2, confirmed by a Match indicator
- Check the Homomorphic Scalar Multiplication section: Decrypt(E(m1)^k) should equal m1 * k, confirmed by a Match indicator
- Try different values for m1, m2, and k to see the homomorphic properties hold across different inputs
Real-world examples
Adding two encrypted salaries
Set m1 = 75000 and m2 = 62000 (two salaries). The tool encrypts both values with the Paillier key. The homomorphic addition section shows c_add = E(m1) * E(m2) mod n^2, and Decrypt(c_add) = 137000, which matches m1 + m2 = 137000. The match indicator confirms the result. This demonstrates how an aggregator can compute the total salary from encrypted individual salaries without learning any individual value.
Scalar multiplication for weighted sums
Set m1 = 100 and k = 5. The tool computes c_scalar = E(100)^5 mod n^2, and Decrypt(c_scalar) = 500, matching 100 * 5 = 500. This is homomorphic scalar multiplication: raising the ciphertext to the power k multiplies the plaintext by k. Combined with addition, this lets you compute weighted sums (a*m1 + b*m2) entirely on ciphertexts, which is useful for encrypted statistics and machine learning inference.
Custom primes and key validation
Toggle to custom primes and enter p = 101 and q = 103. The tool computes n = 10403, n^2 = 108222409, and the key components. Now try p = 4 and q = 6: the tool shows an error because 4 and 6 are not prime. Try p = 2 and q = 4: the error explains that gcd(n, (p-1)*(q-1)) must be 1. This validation prevents invalid keys that would break the decryption formula.
Semantic security via random r
Set m1 = 42 and click Regenerate Key multiple times (or change the scalar to trigger recomputation). Each encryption of 42 produces a different ciphertext because the random r changes each time. An attacker seeing multiple ciphertexts cannot tell which ones encrypt the same value. This is semantic security (IND-CPA), a requirement for practical encryption. Without the random r, the same plaintext would always produce the same ciphertext, leaking information.
Modular arithmetic wraparound
Set the tiny preset (n = 10403) and m1 = 8000, m2 = 8000. The homomorphic addition yields Decrypt(E(8000) * E(8000)) = 16000, which is correct. Now set m1 = 8000, m2 = 8000, and note that 16000 > n = 10403. The result wraps around modulo n: 16000 mod 10403 = 5597. The tool shows the decrypted result as 5597, not 16000. This is a limitation of modular arithmetic: plaintext values must stay within [0, n) and sums must not exceed n, or the result wraps. Real deployments use large primes (1024+ bits) to make wraparound unlikely.
Comparison with similar methods
| Method | Complexity | Typical use |
|---|---|---|
| Paillier | Partially homomorphic (addition + scalar mul) | E-voting, encrypted aggregation, secure sum |
| RSA (textbook) | Multiplicatively homomorphic only | Educational, not semantically secure |
| ElGamal (textbook) | Multiplicatively homomorphic | E-voting (re-encryption), mix-nets |
| BFV / BGV (FHE) | Fully homomorphic (add + multiply), LWE-based | Privacy-preserving ML, encrypted databases |
| CKKS (FHE) | Fully homomorphic, approximate arithmetic | Encrypted floating-point computation |
Limitations or considerations
This tool uses small primes (101, 103, 1009, 1013, 10007, 10009) for educational purposes. Real Paillier deployments use primes of at least 1024 bits, making n at least 2048 bits. The small primes here are for understanding the math, not for security. An attacker can factor n = 101 * 103 = 10403 trivially and recover the private key.
Paillier is only partially homomorphic. It supports addition of ciphertexts and scalar multiplication, but not multiplication of two ciphertexts. You cannot compute E(m1 * m2) from E(m1) and E(m2). For full homomorphic encryption (both addition and multiplication), you need FHE schemes like BFV, BGV, or CKKS, which are based on the learning with errors problem and are far more complex.
The random number generator in this tool uses Math.random(), which is not cryptographically secure. Real implementations must use a CSPRNG (crypto.getRandomValues) for the random value r. Using a weak RNG could allow an attacker to predict r and break semantic security.
Plaintext values must be non-negative integers in [0, n). The tool does not support negative numbers or fractions. For negative numbers, you would use modular representation (e.g., n-1 represents -1). For fractions, you would scale by a fixed factor and round.
The scalar multiplication c^k mod n^2 works for integer k, but k must also be reduced modulo n for large values. The tool does not enforce this, so very large k values may produce unexpected results due to BigInt behavior.
Frequently asked questions
What is homomorphic encryption?
Homomorphic encryption lets you perform computations on encrypted data without decrypting it first. In Paillier, multiplying two ciphertexts adds the underlying plaintexts. This means a server can compute the sum of encrypted values without ever seeing the plaintexts. The term comes from homomorphisms in algebra: the encryption function preserves the structure of the operation (multiplication of ciphertexts maps to addition of plaintexts).
What is the difference between partial and fully homomorphic encryption?
Partially homomorphic encryption (like Paillier) supports one operation: either addition or multiplication of ciphertexts, but not both. Fully homomorphic encryption (FHE) supports both, which means you can evaluate arbitrary circuits on encrypted data. FHE was first constructed by Craig Gentry in 2009 using a technique called bootstrapping. Paillier is simpler and faster but limited to additive operations.
Why does multiplying ciphertexts add the plaintexts?
Paillier encryption is c = g^m * r^n mod n^2. When you multiply two ciphertexts, the g terms add their exponents: g^{m1} * g^{m2} = g^{m1+m2}. The r terms also combine: r1^n * r2^n = (r1*r2)^n. So c1 * c2 = g^{m1+m2} * (r1*r2)^n mod n^2, which is a valid encryption of m1 + m2. Decryption recovers m1 + m2 mod n.
Is Paillier secure?
Paillier's security reduces to the composite residuosity problem, which is related to the difficulty of factoring n = p * q. With sufficiently large primes (1024+ bits each), it is considered secure against classical attacks. Like RSA, it is not post-quantum secure: Shor's algorithm can factor n and break the scheme. For post-quantum alternatives, see the Post-Quantum Playground.
What are real-world uses of Paillier?
Paillier is used in electronic voting (the Helios system), where ballots are encrypted and tallied homomorphically without decrypting individual votes. It is also used in privacy-preserving data aggregation (computing statistics over encrypted data), secure multiparty computation, and federated learning. Any application that needs to compute sums of encrypted values without decrypting them can use Paillier.
Can I use this tool for real encryption?
No. The small primes used here are trivially factorable. The random number generator (Math.random) is not cryptographically secure. This tool is for understanding the math behind homomorphic encryption. For real deployments, use a library like libpaillier, Microsoft SEAL (for FHE), or PALISADE with 2048-bit keys and a CSPRNG.
Conclusion
Paillier's cryptosystem demonstrates that computation on encrypted data is possible: you can add plaintexts by multiplying ciphertexts, and multiply by a scalar by exponentiating. This tool shows the full cycle with small primes and BigInt arithmetic. For digital signatures and authentication, see the Digital Signature Verifier. For quantum-resistant algorithms, see the Post-Quantum Playground. For symmetric encryption, see the AES Encrypt / Decrypt tool.