Homomorphic encryption has a dark side, and it’s the same as its bright side: nobody can see what’s inside a ciphertext. That’s wonderful when a survey adds up encrypted salaries without seeing them. It’s less wonderful when someone submits an encrypted salary of a billion dollars to skew the average, an encrypted rating of 1,000 stars, or a ballot that counts as a hundred votes. The server can’t tell, because the server can’t look. Homomorphic encryption hides honest values and dishonest values equally well.
The fix is a zero-knowledge proof: the encryptor attaches a proof that the ciphertext satisfies some rule—it’s one of the allowed values, it’s within a range, the encryptor knows what’s inside—and anyone can verify the proof without learning the value itself. Think of a “Where’s Waldo?” page: you can prove you found Waldo by covering the page with a large sheet that has a small hole right over him. Your friend sees Waldo, but learns nothing about where on the page he is.
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
This is the first post of a three-part series on zero-knowledge proofs for homomorphic encryption, with LightPHE in Python, Go, Java and TypeScript. Here, we prove what’s inside a ciphertext. Next, we’ll prove that a decryption is honest. Finally, we’ll look at verifiable encryption.
What Makes a Proof Zero-Knowledge
A zero-knowledge proof has three properties:
- Completeness: An honest prover always convinces the verifier.
- Soundness: A cheating prover cannot convince the verifier of a false statement, except with a negligible probability.
- Zero-knowledge: The verifier learns nothing beyond the fact that the statement is true.
The proofs in LightPHE are built the same way. The prover commits to some fresh randomness, receives a random challenge, and answers with a response that combines the challenge, the randomness and its secret. An honest prover can answer any challenge, while a cheater could only answer a challenge it guessed in advance. To avoid a back-and-forth conversation, the challenge is computed as a hash of everything the verifier sees, as proposed by Fiat and Shamir in How to Prove Yourself (CRYPTO 1986). That turns the proof into a single message that anybody can verify, any time.
That hash also includes the ciphertext and a context, typically the identity of the prover, such as a voter ID. So a proof is welded to its ciphertext and its owner: copy it to another ciphertext, or submit it under another name, and it no longer verifies.
Proof of Knowledge: I Know What I Encrypted
With homomorphic encryption, anyone can take somebody else’s ciphertext and transform it without knowing what’s inside: add 1, multiply by 2, or re-randomize it so it looks brand new. That’s the whole point of homomorphic encryption, but in a sealed-bid auction, it’s a disaster. Mallory sees Alice’s encrypted bid, adds 1 to it, and submits it as her own. She outbids Alice by the smallest possible margin without ever knowing the amount.
A proof of knowledge shows that the encryptor knows the secret randomness behind the ciphertext, and with it what’s inside. Mallory doesn’t know either for her modified ciphertext, so she cannot produce such a proof, and Alice’s proof doesn’t fit the modified ciphertext.
from lightphe import LightPHE # auctioneer builds the cryptosystem, and publishes its public key auctioneer_cs = LightPHE(algorithm_name = "Paillier") auctioneer_cs.export_keys(target_file = "public.txt", public = True) public_cs = LightPHE(algorithm_name = "Paillier", key_file = "public.txt") # alice submits her sealed bid with a proof that she knows what she encrypted alice_bid, alice_proof = public_cs.encrypt_with_proof_of_knowledge(950, context = "alice") assert public_cs.verify_knowledge(alice_bid, alice_proof, context = "alice") is True # mallory adds 1 to alice's encrypted bid to win by the smallest margin, without knowing it mallory_bid = alice_bid + public_cs.encrypt(1) assert public_cs.verify_knowledge(mallory_bid, alice_proof, context = "mallory") is False # re-randomizing alice's bid to submit a copy that looks different fails as well copied_bid = public_cs.regenerate_ciphertext(alice_bid) assert public_cs.verify_knowledge(copied_bid, alice_proof, context = "mallory") is False # so mallory has to bid with her own money, which she can prove mallory_bid, mallory_proof = public_cs.encrypt_with_proof_of_knowledge(900, context = "mallory") assert public_cs.verify_knowledge(mallory_bid, mallory_proof, context = "mallory") is True # when the auction closes, the auctioneer opens the bids assert auctioneer_cs.decrypt(alice_bid) == 950 assert auctioneer_cs.decrypt(mallory_bid) == 900
package main
import (
"fmt"
"log"
"math/big"
"github.com/serengil/lightphe-go/lightphe"
)
func check(err error) {
if err != nil {
log.Fatal(err)
}
}
func main() {
// auctioneer builds the cryptosystem, and publishes its public key
auctioneerCs, err := lightphe.New(lightphe.Paillier)
check(err)
check(auctioneerCs.ExportKeys("public.txt", true))
publicCs, err := lightphe.New(lightphe.Paillier, lightphe.WithKeyFile("public.txt"))
check(err)
// alice submits her sealed bid with a proof that she knows what she encrypted
aliceBid, aliceProof, err := publicCs.EncryptWithProofOfKnowledge(big.NewInt(950), "alice")
check(err)
valid, err := publicCs.VerifyKnowledge(aliceBid, aliceProof, "alice")
check(err)
fmt.Println("alice's bid accepted:", valid) // true
// mallory adds 1 to alice's encrypted bid to win by the smallest margin, without knowing it
one, err := publicCs.EncryptInt(1)
check(err)
malloryBid, err := aliceBid.Add(one)
check(err)
valid, err = publicCs.VerifyKnowledge(malloryBid, aliceProof, "mallory")
check(err)
fmt.Println("mallory's +1 accepted:", valid) // false
// re-randomizing alice's bid to submit a copy that looks different fails as well
copiedBid, err := publicCs.RegenerateCiphertext(aliceBid)
check(err)
valid, err = publicCs.VerifyKnowledge(copiedBid, aliceProof, "mallory")
check(err)
fmt.Println("mallory's copy accepted:", valid) // false
// so mallory has to bid with her own money, which she can prove
malloryBid, malloryProof, err := publicCs.EncryptWithProofOfKnowledge(big.NewInt(900), "mallory")
check(err)
valid, err = publicCs.VerifyKnowledge(malloryBid, malloryProof, "mallory")
check(err)
fmt.Println("mallory's own bid accepted:", valid) // true
// when the auction closes, the auctioneer opens the bids
for _, bid := range []*lightphe.Ciphertext{aliceBid, malloryBid} {
m, err := auctioneerCs.Decrypt(bid)
check(err)
fmt.Println(m) // 950, then 900
}
}
import io.github.serengil.lightphe.LightPHE;
import io.github.serengil.lightphe.model.Ciphertext;
import io.github.serengil.lightphe.model.Proven;
import java.math.BigInteger;
import java.nio.file.Path;
// auctioneer builds the cryptosystem, and publishes its public key
LightPHE auctioneerCs = LightPHE.builder().algorithmName("Paillier").build();
auctioneerCs.exportKeys(Path.of("public.txt"), true);
LightPHE publicCs = LightPHE.builder().algorithmName("Paillier").keyFile(Path.of("public.txt")).build();
// alice submits her sealed bid with a proof that she knows what she encrypted
Proven<Ciphertext> alice = publicCs.encryptWithProofOfKnowledge(950, "alice");
assert publicCs.verifyKnowledge(alice.value(), alice.proof(), "alice");
// mallory adds 1 to alice's encrypted bid to win by the smallest margin, without knowing it
Ciphertext malloryBid = alice.value().add(publicCs.encrypt(1));
assert !publicCs.verifyKnowledge(malloryBid, alice.proof(), "mallory");
// re-randomizing alice's bid to submit a copy that looks different fails as well
Ciphertext copiedBid = publicCs.regenerateCiphertext(alice.value());
assert !publicCs.verifyKnowledge(copiedBid, alice.proof(), "mallory");
// so mallory has to bid with her own money, which she can prove
Proven<Ciphertext> mallory = publicCs.encryptWithProofOfKnowledge(900, "mallory");
assert publicCs.verifyKnowledge(mallory.value(), mallory.proof(), "mallory");
// when the auction closes, the auctioneer opens the bids
assert auctioneerCs.decrypt(alice.value()).equals(BigInteger.valueOf(950));
assert auctioneerCs.decrypt(mallory.value()).equals(BigInteger.valueOf(900));
import { LightPHE } from 'lightphe-ts';
// auctioneer builds the cryptosystem, and publishes its public key
const auctioneerCs = new LightPHE({ algorithmName: 'Paillier' });
auctioneerCs.exportKeys('public.txt', true);
const publicCs = new LightPHE({ algorithmName: 'Paillier', keyFile: 'public.txt' });
// alice submits her sealed bid with a proof that she knows what she encrypted
const [aliceBid, aliceProof] = publicCs.encryptWithProofOfKnowledge(950, { context: 'alice' });
console.assert(publicCs.verifyKnowledge(aliceBid, aliceProof, { context: 'alice' }));
// mallory adds 1 to alice's encrypted bid to win by the smallest margin, without knowing it
const plusOne = aliceBid.add(publicCs.encrypt(1));
console.assert(!publicCs.verifyKnowledge(plusOne, aliceProof, { context: 'mallory' }));
// re-randomizing alice's bid to submit a copy that looks different fails as well
const copiedBid = publicCs.regenerateCiphertext(aliceBid);
console.assert(!publicCs.verifyKnowledge(copiedBid, aliceProof, { context: 'mallory' }));
// so mallory has to bid with her own money, which she can prove
const [malloryBid, malloryProof] = publicCs.encryptWithProofOfKnowledge(900, { context: 'mallory' });
console.assert(publicCs.verifyKnowledge(malloryBid, malloryProof, { context: 'mallory' }));
// when the auction closes, the auctioneer opens the bids
console.assert(auctioneerCs.decrypt(aliceBid) === 950n);
console.assert(auctioneerCs.decrypt(malloryBid) === 900n);
Both of Mallory’s tricks fail: the +1 version and the re-randomized copy. To win, she has to bid with her own money, like everybody else. A proof of knowledge is cheap: about 1 KB and 30 milliseconds with a 1024-bit Paillier key on my laptop. Java snippets use assert for brevity, so run them with -ea to enable assertions.
Proof of Allowed Values: It’s One of These
Sometimes we need more than “I know what’s inside”. A product rating must be 1 to 5 stars, a ballot must be 0 or 1, and a vote for a party must be one of the encoded parties. A proof of allowed values shows that a ciphertext encrypts one of a list of values, without revealing which one.
Under the hood, it is an OR-proof, as introduced by Cramer, Damgård and Schoenmakers in Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols (CRYPTO 1994). The prover proves “the ciphertext encrypts 1, or 2, or 3, or 4, or 5”. For the true value, it runs an honest proof. For every other value, it simulates a proof, which it can do because it is allowed to choose those challenges itself, as long as all challenges add up to the one fixed by the hash. The verifier sees five proofs that all look exactly alike, and cannot tell which one was real.
from lightphe import LightPHE
# shop builds the cryptosystem, and publishes its public key
shop_cs = LightPHE(algorithm_name = "EllipticCurve-ElGamal")
shop_cs.export_keys(target_file = "public.txt", public = True)
public_cs = LightPHE(algorithm_name = "EllipticCurve-ElGamal", key_file = "public.txt")
# customers rate a product from 1 to 5 stars, and prove it without revealing their rating
stars = [1, 2, 3, 4, 5]
ratings = {"customer-1": 5, "customer-2": 4, "customer-3": 2}
submissions = {
customer: public_cs.encrypt_with_proof(rating, values = stars, context = customer)
for customer, rating in ratings.items()
}
# a troll encrypts 1000 stars, and attaches a valid proof of a 5-star rating to it
_, troll_proof = public_cs.encrypt_with_proof(5, values = stars, context = "troll")
submissions["troll"] = (public_cs.encrypt(1000), troll_proof)
# anyone verifies the ratings without decrypting them, and the troll's one is rejected
valid = [
rating for customer, (rating, proof) in submissions.items()
if public_cs.verify_ciphertext(rating, proof, values = stars, context = customer)
]
assert len(valid) == 3
# valid ratings are summed encrypted, and the shop decrypts only the total
total = valid[0] + valid[1] + valid[2]
assert shop_cs.decrypt(total) == 11 # average rating is 11 / 3 = 3.67 stars
package main
import (
"fmt"
"log"
"math/big"
"github.com/serengil/lightphe-go/lightphe"
)
func check(err error) {
if err != nil {
log.Fatal(err)
}
}
func main() {
// shop builds the cryptosystem, and publishes its public key
shopCs, err := lightphe.New(lightphe.EllipticCurveElGamal)
check(err)
check(shopCs.ExportKeys("public.txt", true))
publicCs, err := lightphe.New(lightphe.EllipticCurveElGamal, lightphe.WithKeyFile("public.txt"))
check(err)
// customers rate a product from 1 to 5 stars, and prove it without revealing their rating
stars := []*big.Int{big.NewInt(1), big.NewInt(2), big.NewInt(3), big.NewInt(4), big.NewInt(5)}
type submission struct {
rating *lightphe.Ciphertext
proof *lightphe.ZKProof
}
submissions := map[string]submission{}
for customer, rating := range map[string]int64{"customer-1": 5, "customer-2": 4, "customer-3": 2} {
c, proof, err := publicCs.EncryptWithProof(big.NewInt(rating), stars, customer)
check(err)
submissions[customer] = submission{c, proof}
}
// a troll encrypts 1000 stars, and attaches a valid proof of a 5-star rating to it
_, trollProof, err := publicCs.EncryptWithProof(big.NewInt(5), stars, "troll")
check(err)
trollRating, err := publicCs.EncryptInt(1000)
check(err)
submissions["troll"] = submission{trollRating, trollProof}
// anyone verifies the ratings without decrypting them, and the troll's one is rejected
var total *lightphe.Ciphertext
count := 0
for customer, s := range submissions {
valid, err := publicCs.VerifyCiphertext(s.rating, s.proof, stars, customer)
check(err)
if !valid {
fmt.Println("rejected:", customer) // troll
continue
}
// valid ratings are summed encrypted
if total == nil {
total = s.rating
} else {
total, err = total.Add(s.rating)
check(err)
}
count++
}
// shop decrypts only the total
sum, err := shopCs.Decrypt(total)
check(err)
fmt.Printf("%d ratings, %d stars in total\n", count, sum) // 3 ratings, 11 stars in total
}
import io.github.serengil.lightphe.LightPHE;
import io.github.serengil.lightphe.model.Ciphertext;
import io.github.serengil.lightphe.model.Proven;
import java.math.BigInteger;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
// shop builds the cryptosystem, and publishes its public key
LightPHE shopCs = LightPHE.builder().algorithmName("EllipticCurve-ElGamal").build();
shopCs.exportKeys(Path.of("public.txt"), true);
LightPHE publicCs = LightPHE.builder()
.algorithmName("EllipticCurve-ElGamal")
.keyFile(Path.of("public.txt"))
.build();
// customers rate a product from 1 to 5 stars, and prove it without revealing their rating
List<Long> stars = List.of(1L, 2L, 3L, 4L, 5L);
Map<String, Proven<Ciphertext>> submissions = new LinkedHashMap<>();
Map.of("customer-1", 5L, "customer-2", 4L, "customer-3", 2L).forEach((customer, rating) ->
submissions.put(customer, publicCs.encryptWithProof(rating, stars, customer)));
// a troll encrypts 1000 stars, and attaches a valid proof of a 5-star rating to it
Proven<Ciphertext> fiveStars = publicCs.encryptWithProof(5, stars, "troll");
submissions.put("troll", new Proven<>(publicCs.encrypt(1000), fiveStars.proof()));
// anyone verifies the ratings without decrypting them, and the troll's one is rejected
List<Ciphertext> valid = new ArrayList<>();
submissions.forEach((customer, submission) -> {
if (publicCs.verifyCiphertext(submission.value(), submission.proof(), stars, customer)) {
valid.add(submission.value());
}
});
assert valid.size() == 3;
// valid ratings are summed encrypted, and the shop decrypts only the total
Ciphertext total = valid.get(0).add(valid.get(1)).add(valid.get(2));
assert shopCs.decrypt(total).equals(BigInteger.valueOf(11)); // average rating is 11 / 3 = 3.67 stars
import { LightPHE } from 'lightphe-ts';
// shop builds the cryptosystem, and publishes its public key
const shopCs = new LightPHE({ algorithmName: 'EllipticCurve-ElGamal' });
shopCs.exportKeys('public.txt', true);
const publicCs = new LightPHE({ algorithmName: 'EllipticCurve-ElGamal', keyFile: 'public.txt' });
// customers rate a product from 1 to 5 stars, and prove it without revealing their rating
const stars = [1, 2, 3, 4, 5];
const ratings: [string, number][] = [
['customer-1', 5],
['customer-2', 4],
['customer-3', 2],
];
const submissions = ratings.map(([customer, rating]) => {
const [c, proof] = publicCs.encryptWithProof(rating, { values: stars, context: customer });
return { customer, rating: c, proof };
});
// a troll encrypts 1000 stars, and attaches a valid proof of a 5-star rating to it
const [, trollProof] = publicCs.encryptWithProof(5, { values: stars, context: 'troll' });
submissions.push({ customer: 'troll', rating: publicCs.encrypt(1000), proof: trollProof });
// anyone verifies the ratings without decrypting them, and the troll's one is rejected
const valid = submissions
.filter((s) => publicCs.verifyCiphertext(s.rating, s.proof, { values: stars, context: s.customer }))
.map((s) => s.rating);
console.assert(valid.length === 3);
// valid ratings are summed encrypted, and the shop decrypts only the total
const total = valid.reduce((sum, rating) => sum.add(rating));
console.assert(shopCs.decrypt(total) === 11n); // average rating is 11 / 3 = 3.67 stars
The troll’s trick was to pair a 1,000-star ciphertext with a perfectly valid proof of a 5-star rating, and it failed: a proof is bound to the ciphertext it was made for. Note that the troll can’t even create a proof for 1,000 stars, as LightPHE refuses with Plaintext must be one of the allowed values. This example uses Elliptic Curve ElGamal, whose short keys suit mobile apps, and the same proofs power the ballots of our verifiable referendum.
Proof of Range: It’s Between Low and High
Listing every allowed value works for 5 stars, but not for a salary between 0 and 500,000. For that, we need a range proof: the ciphertext encrypts a value in [low, high]. LightPHE builds it from the proofs we already have. It subtracts low, and decomposes what’s left into bits with carefully chosen weights, so that every value of the range, and nothing outside it, can be written as a weighted sum of bits. Each bit is encrypted with a proof that it is 0 or 1. For a range of width 190, for instance:
weights for width 190: 1, 2, 4, 8, 16, 32, 64, 63 (the last one is 190 - 127) largest sum: 1 + 2 + 4 + 8 + 16 + 32 + 64 + 63 = 190, so nothing above the range 127 is written as: 64 + 63, so bits are 0, 0, 0, 0, 0, 0, 1, 1 ciphertext = E(low) + 1 * E(b_1) + 2 * E(b_2) + ... + 63 * E(b_8)
The last line is the key: the verifier rebuilds the ciphertext from the encrypted bits itself, with homomorphic addition and scalar multiplication. So the proof is about exactly the ciphertext that was submitted, and every bit is 0 or 1, so the value cannot fall outside the range. The price is size: the proof grows with the number of bits of the range.
from lightphe import LightPHE
# survey authority builds the cryptosystem, and publishes its public key
authority_cs = LightPHE(algorithm_name = "Paillier")
authority_cs.export_keys(target_file = "public.txt", public = True)
public_cs = LightPHE(algorithm_name = "Paillier", key_file = "public.txt")
# employees encrypt their salaries with a proof that they are in [0, 500000]
low, high = 0, 500000
salaries = {"alice": 85000, "bob": 62000, "carol": 120000, "dave": 47000}
submissions = {
employee: public_cs.encrypt_with_range_proof(salary, low = low, high = high, context = employee)
for employee, salary in salaries.items()
}
# oscar wants to inflate the average with a billion, and reuses the proof of a valid salary
_, oscar_proof = public_cs.encrypt_with_range_proof(50000, low = low, high = high, context = "oscar")
submissions["oscar"] = (public_cs.encrypt(10**9), oscar_proof)
# trent wants to deflate it with a negative salary
_, trent_proof = public_cs.encrypt_with_range_proof(0, low = low, high = high, context = "trent")
submissions["trent"] = (public_cs.encrypt(-10**6), trent_proof)
# anyone verifies the submissions without decrypting them, and drops the invalid ones
valid = [
salary for employee, (salary, proof) in submissions.items()
if public_cs.verify_range(salary, proof, low = low, high = high, context = employee)
]
assert len(valid) == 4
# valid salaries are summed encrypted, and the authority decrypts only the total
total = valid[0]
for salary in valid[1:]:
total = total + salary
assert authority_cs.decrypt(total) / len(valid) == 78500
package main
import (
"fmt"
"log"
"math/big"
"github.com/serengil/lightphe-go/lightphe"
)
func check(err error) {
if err != nil {
log.Fatal(err)
}
}
func main() {
// survey authority builds the cryptosystem, and publishes its public key
authorityCs, err := lightphe.New(lightphe.Paillier)
check(err)
check(authorityCs.ExportKeys("public.txt", true))
publicCs, err := lightphe.New(lightphe.Paillier, lightphe.WithKeyFile("public.txt"))
check(err)
// employees encrypt their salaries with a proof that they are in [0, 500000]
low, high := big.NewInt(0), big.NewInt(500000)
type submission struct {
salary *lightphe.Ciphertext
proof *lightphe.RangeProof
}
submissions := map[string]submission{}
for employee, salary := range map[string]int64{"alice": 85000, "bob": 62000, "carol": 120000, "dave": 47000} {
c, proof, err := publicCs.EncryptWithRangeProof(big.NewInt(salary), low, high, employee)
check(err)
submissions[employee] = submission{c, proof}
}
// oscar wants to inflate the average with a billion, and reuses the proof of a valid salary
_, oscarProof, err := publicCs.EncryptWithRangeProof(big.NewInt(50000), low, high, "oscar")
check(err)
oscarSalary, err := publicCs.EncryptInt(1000000000)
check(err)
submissions["oscar"] = submission{oscarSalary, oscarProof}
// trent wants to deflate it with a negative salary
_, trentProof, err := publicCs.EncryptWithRangeProof(big.NewInt(0), low, high, "trent")
check(err)
trentSalary, err := publicCs.EncryptInt(-1000000)
check(err)
submissions["trent"] = submission{trentSalary, trentProof}
// anyone verifies the submissions without decrypting them, and drops the invalid ones
var total *lightphe.Ciphertext
count := int64(0)
for employee, s := range submissions {
valid, err := publicCs.VerifyRange(s.salary, s.proof, low, high, employee)
check(err)
if !valid {
fmt.Println("rejected:", employee) // oscar and trent
continue
}
// valid salaries are summed encrypted
if total == nil {
total = s.salary
} else {
total, err = total.Add(s.salary)
check(err)
}
count++
}
// authority decrypts only the total
sum, err := authorityCs.Decrypt(total)
check(err)
fmt.Println("average salary:", new(big.Int).Div(sum, big.NewInt(count))) // 78500
}
import io.github.serengil.lightphe.LightPHE;
import io.github.serengil.lightphe.model.Ciphertext;
import io.github.serengil.lightphe.model.Proven;
import java.math.BigInteger;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
// survey authority builds the cryptosystem, and publishes its public key
LightPHE authorityCs = LightPHE.builder().algorithmName("Paillier").build();
authorityCs.exportKeys(Path.of("public.txt"), true);
LightPHE publicCs = LightPHE.builder().algorithmName("Paillier").keyFile(Path.of("public.txt")).build();
// employees encrypt their salaries with a proof that they are in [0, 500000]
long low = 0, high = 500000;
Map<String, Proven<Ciphertext>> submissions = new LinkedHashMap<>();
Map.of("alice", 85000L, "bob", 62000L, "carol", 120000L, "dave", 47000L).forEach((employee, salary) ->
submissions.put(employee, publicCs.encryptWithRangeProof(salary, low, high, employee)));
// oscar wants to inflate the average with a billion, and reuses the proof of a valid salary
Proven<Ciphertext> oscar = publicCs.encryptWithRangeProof(50000, low, high, "oscar");
submissions.put("oscar", new Proven<>(publicCs.encrypt(1_000_000_000L), oscar.proof()));
// trent wants to deflate it with a negative salary
Proven<Ciphertext> trent = publicCs.encryptWithRangeProof(0, low, high, "trent");
submissions.put("trent", new Proven<>(publicCs.encrypt(-1_000_000L), trent.proof()));
// anyone verifies the submissions without decrypting them, and drops the invalid ones
List<Ciphertext> valid = new ArrayList<>();
submissions.forEach((employee, submission) -> {
if (publicCs.verifyRange(submission.value(), submission.proof(), low, high, employee)) {
valid.add(submission.value());
}
});
assert valid.size() == 4;
// valid salaries are summed encrypted, and the authority decrypts only the total
Ciphertext total = valid.get(0);
for (Ciphertext salary : valid.subList(1, valid.size())) {
total = total.add(salary);
}
assert authorityCs.decrypt(total).divide(BigInteger.valueOf(valid.size())).equals(BigInteger.valueOf(78500));
import { LightPHE } from 'lightphe-ts';
// survey authority builds the cryptosystem, and publishes its public key
const authorityCs = new LightPHE({ algorithmName: 'Paillier' });
authorityCs.exportKeys('public.txt', true);
const publicCs = new LightPHE({ algorithmName: 'Paillier', keyFile: 'public.txt' });
// employees encrypt their salaries with a proof that they are in [0, 500000]
const [low, high] = [0, 500000];
const salaries: [string, number][] = [
['alice', 85000],
['bob', 62000],
['carol', 120000],
['dave', 47000],
];
const submissions = salaries.map(([employee, salary]) => {
const [c, proof] = publicCs.encryptWithRangeProof(salary, low, high, { context: employee });
return { employee, salary: c, proof };
});
// oscar wants to inflate the average with a billion, and reuses the proof of a valid salary
const [, oscarProof] = publicCs.encryptWithRangeProof(50000, low, high, { context: 'oscar' });
submissions.push({ employee: 'oscar', salary: publicCs.encrypt(10 ** 9), proof: oscarProof });
// trent wants to deflate it with a negative salary
const [, trentProof] = publicCs.encryptWithRangeProof(0, low, high, { context: 'trent' });
submissions.push({ employee: 'trent', salary: publicCs.encrypt(-(10 ** 6)), proof: trentProof });
// anyone verifies the submissions without decrypting them, and drops the invalid ones
const valid = submissions
.filter((s) => publicCs.verifyRange(s.salary, s.proof, low, high, { context: s.employee }))
.map((s) => s.salary);
console.assert(valid.length === 4);
// valid salaries are summed encrypted, and the authority decrypts only the total
const total = valid.reduce((sum, salary) => sum.add(salary));
console.assert(authorityCs.decrypt(total) / BigInt(valid.length) === 78500n);
Oscar’s billion and Trent’s negative salary are both rejected, so the average of 78,500 is computed from honest submissions only. For [0, 500000], a proof consists of 20 parts, the encrypted low and 19 encrypted bits, and takes about 38 KB, 0.8 seconds to create and 0.6 seconds to verify with a 1024-bit Paillier key on my laptop. Narrow your ranges: a range of [0, 255] needs only 8 bits.
Required Cryptographic Features
1. Randomized encryption with provable structure. Every proof above is ultimately about the randomness used in encryption: the prover shows it knows the randomness, or that the ciphertext minus a candidate value is an encryption of zero. That requires a group where such statements can be proven: a group of known prime order for the ElGamal family, which is why ElGamal and Exponential ElGamal keys must be generated with prime_order = True, and the structure of n-th powers for Paillier and Damgard-Jurik.
2. Additive homomorphism. Proofs of allowed values shift the ciphertext by each candidate value, and range proofs rebuild the ciphertext from its encrypted bits. Both need homomorphic addition and scalar multiplication.
3. A hash for Fiat-Shamir, binding every proof to its ciphertext, its statement and its context.
Which Algorithms Can Be Used, and Why
| Algorithm | Proof of knowledge | Proof of allowed values | Proof of range | Notes |
| Exponential ElGamal | ✅ | ✅ | ✅ | Keys need prime_order = True |
| Elliptic Curve ElGamal | ✅ | ✅ | ✅ | Works with default keys, and suits mobile apps with its short keys |
| Paillier, Damgard-Jurik | ✅ | ✅ | ✅ | Large plaintext space, e.g. for salaries |
| ElGamal | ✅ | ❌ | ❌ | Multiplicatively homomorphic, so it cannot shift or rebuild ciphertexts by addition. LightPHE suggests Use Exponential-ElGamal instead |
| RSA, Okamoto-Uchiyama and others | ❌ | ❌ | ❌ | LightPHE refuses to create these proofs for them. RSA encryption isn’t even randomized, so there is no randomness to prove anything about |
More Scenarios
- E-voting: Each voter proves that the ballot is 0 or 1, or a vote for exactly one party, so nobody can cast a vote of 100 in the homomorphic tally without revealing how they voted.
- Age verification: A website requires visitors to be adults, and a visitor proves that the encrypted age is between 18 and 120 without revealing the exact age or birth date.
- Credit checks: A lender accepts an encrypted credit score with a proof that it is between 650 and 850, so the applicant shows eligibility without revealing the exact score.
- Participatory budgeting: Each citizen allocates up to 1,000 to public projects in encrypted form, so allocations are proven to be within the cap while individual preferences stay private.
- Crowdfunding: A backer cannot copy a large encrypted pledge of another backer and scale it to look generous, because each pledge must come with a proof that its owner knows the amount.
Caveats
- Valid is not the same as true: A range proof shows that a salary is between 0 and 500,000, not that it is the employee’s real salary. Proofs keep the data well-formed; they can’t keep people honest about facts the system cannot check.
- The context must be authenticated: A proof bound to “alice” stops others from reusing Alice’s submission, but only if the system checks that a submission for “alice” really comes from Alice.
- Prove at encryption time: The proofs need the randomness used in encryption, so they are created together with the ciphertext. You can’t prove something about an old ciphertext afterwards.
- Range proofs have a size: About 2 KB per bit of the range with a 1024-bit Paillier key. Keep ranges as narrow as your data allows.
Conclusion
Homomorphic encryption hides everything, including cheating, and zero-knowledge proofs bring the accountability back without giving up the privacy. A proof of knowledge stops people from tampering with someone else’s ciphertext, a proof of allowed values keeps ratings and ballots within their options, and a range proof keeps numbers within sensible bounds. All of them are made non-interactive with the Fiat-Shamir trick, bound to their ciphertext and their owner, and verifiable by anyone with the public key.
So far, we’ve kept the encryptors honest. In the next post of this series, we’ll turn to the other side of the table and make sure that whoever decrypts the result can’t lie about it either.
Support this blog financially if you do like!
