Paillier Homomorphic Encryption crypto

How the Paillier cryptosystem works and how to use each CLI command
Pixelbadger Toolkit — pbtk crypto

Overview

The Paillier cryptosystem is a probabilistic, asymmetric encryption scheme with a remarkable property: arithmetic can be performed directly on encrypted data — no decryption required. The server performing the computation never sees the underlying values.

This implementation exposes a set of CLI commands under the crypto topic that let you generate keys, encrypt and decrypt integers and strings, and perform addition, subtraction, and scalar multiplication on ciphertext.

Property
Additive HE

Add, subtract, and multiply (by a scalar) without decrypting.

Security
2048-bit RSA

Keys use 2048-bit primes, matching NIST minimum for asymmetric encryption.

Randomness
Probabilistic

Each encryption of the same value produces a different ciphertext.

Key files
JSON

Keys are stored as human-readable JSON with BigInteger fields.

How the Paillier Cryptosystem Works

Key Components

Paillier encryption uses four mathematical values. Two form the public key (safe to share) and three form the private key (must be kept secret).

Symbol Name Visibility Description
n Modulus Public Product of two large primes p × q. All arithmetic is performed mod n².
g Generator Public Fixed as n + 1 in this implementation (a common simplification).
λ Lambda Private lcm(p-1, q-1). Used as the decryption exponent.
μ Mu Private Modular inverse of λ mod n. Scales the result during decryption.

Encryption

To encrypt a plaintext integer m, a fresh random value r (coprime with n) is chosen. The ciphertext is:

c = g^m · r^n (mod n²)

Because r is random and discarded, encrypting the same m twice produces different ciphertexts — this is the probabilistic nature of the scheme.

Decryption

Given the private key, the original plaintext is recovered in two steps. First, the L-function removes the randomness; then μ rescales the result:

L(x, n) = (x - 1) / n
m = L(c^λ mod n², n) · μ (mod n)

Homomorphic Addition

Multiplying two ciphertexts together in the encrypted domain produces the ciphertext of their plaintext sum:

Enc(m₁ + m₂) = Enc(m₁) · Enc(m₂) (mod n²)

Homomorphic Subtraction

Multiplication by the modular inverse of a ciphertext computes the difference:

Enc(m₁ - m₂) = Enc(m₁) · Enc(m₂)⁻¹ (mod n²)

Homomorphic Scalar Multiplication

Raising a ciphertext to an integer power multiplies the plaintext by that scalar:

Enc(m · k) = Enc(m)^k (mod n²)

Note: this is multiplication by a known plaintext scalar, not by another encrypted value. Fully encrypted multiplication requires a different (more expensive) scheme.

Limitation: Paillier is additively homomorphic only. Multiplying two encrypted values together is not supported in this scheme.

Key Generation

The generate-key command creates a fresh Paillier key pair and writes two JSON files: a public key (safe to distribute) and a private key (keep secret).

$ pbtk crypto generate-key --public-key-file public.json --private-key-file private.json
flowchart TD A([Start]) --> B[Generate large prime p\n~1024 bits] A --> C[Generate large prime q\n~1024 bits] B --> D{p ≠ q and\nn ≥ 2048 bits?} C --> D D -- No --> B D -- Yes --> E[n = p × q] E --> F[λ = lcm p−1, q−1] F --> G[μ = λ⁻¹ mod n] G --> H[Public key: n\nwrite to file] G --> I[Private key: n, λ, μ\nwrite owner-only file] H --> J([Done]) I --> J

Public key file (public.json)

Contains only N (the modulus). Safe to share freely.

{ "N": "2650...7391" }

Private key file (private.json)

Contains N, Lambda, and Mu. Written with owner-only Unix permissions (600) and must never be shared.

{ "N": "2650...7391", "Lambda": "1325...8432", "Mu": "9812...2049" }
Prime candidates are tested using the Miller-Rabin primality test with 20 witness rounds, giving a false-positive probability of less than 4⁻²⁰ ≈ 10⁻¹².

Numeric Operations

Encrypt a number

Takes a non-negative integer and a public key file. Writes the ciphertext to a JSON file.

$ pbtk crypto encrypt --number 42 --public-key-file public.json --out-file enc42.json
flowchart LR M[Plaintext\nm = 42] --> E PK[public.json\nn, g] --> E R([Random r\ncoprime with n]) --> E E[["c = gᵐ · rⁿ mod n²"]] --> OF[enc42.json\nciphertext, n]

Decrypt a number

Reads an encrypted number file and private key, writes the plaintext to stdout.

$ pbtk crypto decrypt --in-file enc42.json --private-key-file private.json
flowchart LR EF[enc42.json\nciphertext c] --> D SK[private.json\nn, λ, μ] --> D D[["m = L(cλ mod n², n) · μ mod n"]] --> OUT([stdout: 42])

Homomorphic Operations on Encrypted Numbers

These commands operate entirely on ciphertext. No private key is needed and the plaintext values are never revealed to the process performing the computation.

add pbtk crypto add

Enc(a) · Enc(b) mod n² → Enc(a + b)

Multiplies the two ciphertexts together. Decrypting the result yields a + b.

pbtk crypto add --in-file1 enc_a.json --in-file2 enc_b.json --out-file enc_sum.json

subtract pbtk crypto subtract

Enc(a) · Enc(b)⁻¹ mod n² → Enc(a − b)

Multiplies the first ciphertext by the modular inverse of the second.

pbtk crypto subtract --in-file1 enc_a.json --in-file2 enc_b.json --out-file enc_diff.json

multiply pbtk crypto multiply

Enc(m)^k mod n² → Enc(m × k)

Raises the ciphertext to the power of a known plaintext scalar k.

pbtk crypto multiply --in-file enc_m.json --scalar 3 --out-file enc_product.json
flowchart TD A([Enc a]) --> ADD["add\nEnc(a) · Enc(b) mod n²"] B([Enc b]) --> ADD A --> SUB["subtract\nEnc(a) · Enc(b)⁻¹ mod n²"] B --> SUB A --> MUL["multiply\nEnc(a)^k mod n²"] K([Scalar k]) --> MUL ADD --> RA([Enc a+b]) SUB --> RS([Enc a−b]) MUL --> RM([Enc a×k])

String Operations

Strings are encrypted character-by-character: each Unicode code point is independently encrypted as an integer using the Paillier scheme. The result is a JSON array of encrypted numbers, one per character. This representation enables position-aware operations on the ciphertext without decryption.

Strings are limited to 100 characters. Each character is encrypted independently, so the ciphertext reveals the length of the plaintext string but nothing else.

encrypt-string

Encrypts a UTF-8 string as an array of encrypted Unicode code points.

$ pbtk crypto encrypt-string --string "Hello" --public-key-file public.json --out-file enc_str.json
flowchart LR S["Plaintext string\n\"Hello\""] --> RUNES["Enumerate\nUnicode runes\nH=72, e=101, l=108, l=108, o=111"] RUNES --> ENC["Encrypt each\ncode point\nwith public key"] PK["public.json"] --> ENC ENC --> OUT["enc_str.json\n[EncryptedNumber × 5]"]

decrypt-string

Decrypts each code point and reconstructs the original string.

$ pbtk crypto decrypt-string --in-file enc_str.json --private-key-file private.json
flowchart LR EF["enc_str.json\n[EncryptedNumber × 5]"] --> DEC["Decrypt each\ncode point\nwith private key"] SK["private.json"] --> DEC DEC --> CHARS["Code points\n72, 101, 108, 108, 111"] CHARS --> STR(["stdout: \"Hello\""])

replace

Overwrites characters at a known position in an encrypted string without decrypting it. The replacement plaintext is re-encrypted with the same public key (recovered from the ciphertext metadata) and substituted into the array at the specified index.

$ pbtk crypto replace --in-file enc_str.json --start 0 --replacement "J" --out-file enc_str2.json
flowchart LR EF["enc_str.json\n[Enc H, Enc e, Enc l, Enc l, Enc o]"] --> CLONE[Clone array] REP["Replacement\n\"J\" at index 0"] --> RUNES2["Enumerate runes\nJ=74"] RUNES2 --> REENC["Re-encrypt each\nrune with public key\n(from ciphertext N)"] CLONE --> SPLICE["Splice at start index"] REENC --> SPLICE SPLICE --> OUT["enc_str2.json\n[Enc J, Enc e, Enc l, Enc l, Enc o]"]

substring

Slices an encrypted string by position, returning a new encrypted array of the selected range. No private key is needed.

$ pbtk crypto substring --in-file enc_str.json --start 1 --length 3 --out-file enc_sub.json
flowchart LR EF["enc_str.json\n[Enc H, Enc e, Enc l, Enc l, Enc o]"] --> SLICE["Slice [start .. start+length)\ne.g. [1..4)"] SLICE --> OUT["enc_sub.json\n[Enc e, Enc l, Enc l]"]

Command Reference

Command Required options Optional options Output
crypto generate-key --public-key-file --private-key-file — Two JSON files (public + private key)
crypto encrypt --number --public-key-file --out-file — Encrypted number JSON file
crypto decrypt --in-file --private-key-file — Plaintext integer (stdout)
crypto add --in-file1 --in-file2 --out-file — Encrypted sum JSON file
crypto subtract --in-file1 --in-file2 --out-file — Encrypted difference JSON file
crypto multiply --in-file --scalar --out-file — Encrypted product JSON file
crypto encrypt-string --string --public-key-file --out-file — Encrypted string JSON file (array of encrypted code points)
crypto decrypt-string --in-file --private-key-file — Plaintext string (stdout)
crypto replace --in-file --start --replacement --out-file — Updated encrypted string JSON file
crypto substring --in-file --start --out-file --length (defaults to end of string) Encrypted substring JSON file

Constraints and Limits

ConstraintValueReason
Minimum key size 2048 bits NIST minimum recommendation for asymmetric security
Plaintext range (numbers) 0 ≤ m < n Paillier requires the message to be smaller than the modulus
Plaintext integers Non-negative only Paillier works in Z/nZ; negative values are not natively supported
Max string length 100 characters Each character requires one full 2048-bit ciphertext; enforced to limit file size
String character set Full Unicode (UTF-32 code points) Characters are stored as Unicode scalar values, supporting any language
Scalar multiplier Non-negative integer Negative scalars not supported; multiply by 0 produces Enc(0)