In the previous post of this series, we used zero-knowledge proofs to keep the encryptors honest: no billion-dollar salaries, no 1,000-star ratings, no tampering with someone else’s bid. But there is another party in every homomorphic encryption system that we’ve simply trusted so far: whoever decrypts the result. Thousands of ballots are summed under encryption, and then the election authority decrypts the tally and announces “5,000 yes, 3,000 no”. Why should anyone believe it? Nobody else can decrypt the tally to check, because nobody else has the private key. And handing the private key out for an audit would expose every single ballot.
This post closes that gap with two proofs, built with LightPHE in Python, Go, Java and TypeScript. A proof of decryption lets the private key holder prove that an announced result is exactly what a ciphertext contains. A proof of partial decryption does the same for each member of a committee that decrypts together. Anyone with the public key can verify both, and neither reveals the private key.
🙋‍♂️ You may consider to enroll my top-rated cryptography course on Udemy
Proof of Decryption
The statement is simple: “this ciphertext decrypts to this plaintext”. How it’s proven depends on the cryptosystem, and LightPHE uses two quite different techniques.
ElGamal Family: Same Secret, Two Places
An ElGamal ciphertext is a pair (c1, c2), the public key is y = g^x, and decryption computes c1^x to remove the mask from c2. So the key holder publishes d = c1^x along with the plaintext, and proves that the same secret x was used in both places:
public key: y = g^x decryption share: d = c1^x statement: log_g(y) = log_c1(d) "the same x is behind both" if the statement holds, d is the correct mask, and m = c2 / d is the correct plaintext
This is a proof of equality of discrete logarithms, introduced by Chaum and Pedersen in Wallet Databases with Observers (CRYPTO 1992). Like the proofs in the previous post, it’s made non-interactive with Fiat-Shamir, and it’s tiny: just a challenge and a response. It reveals nothing about x.
Paillier Family: Just Show the Randomness
For Paillier and Damgard-Jurik, there is an even simpler trick. A Paillier ciphertext is c = g^m * r^n mod n^2, and the private key holder can recover not only m but also the randomness r, even if someone else encrypted it. So the proof is just r: anyone can re-encrypt the announced plaintext with it, and check that they get exactly the same ciphertext. Revealing r tells nothing about the private key or about any other ciphertext, and the plaintext is being announced anyway.
Example: A Bank’s Daily Total
A bank’s branches encrypt their transactions of the day, and the bank decrypts only their total. It publishes the total with a proof, so a regulator can verify it without the bank’s private key and without seeing a single transaction.
from lightphe import LightPHE # bank builds the cryptosystem, keeps the private key and publishes the public key bank_cs = LightPHE(algorithm_name = "Paillier") bank_cs.export_keys(target_file = "public.txt", public = True) # branches encrypt their transactions of the day with the public key, and they are summed encrypted public_cs = LightPHE(algorithm_name = "Paillier", key_file = "public.txt") transactions = [12500, 8300, 41000, 2750] total = public_cs.encrypt(transactions[0]) for amount in transactions[1:]: total = total + public_cs.encrypt(amount) # bank decrypts the total, and publishes it with a proof announced, proof = bank_cs.decrypt_with_proof(total) assert announced == 64550 # regulator verifies the announced total with the public key only regulator_cs = LightPHE(algorithm_name = "Paillier", key_file = "public.txt") assert regulator_cs.verify_decryption(total, announced, proof) is True # a massaged total doesn't verify with the same proof assert regulator_cs.verify_decryption(total, 60000, proof) is False
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() {
// bank builds the cryptosystem, keeps the private key and publishes the public key
bankCs, err := lightphe.New(lightphe.Paillier)
check(err)
check(bankCs.ExportKeys("public.txt", true))
// branches encrypt their transactions of the day with the public key, and they are summed encrypted
publicCs, err := lightphe.New(lightphe.Paillier, lightphe.WithKeyFile("public.txt"))
check(err)
var total *lightphe.Ciphertext
for _, amount := range []int64{12500, 8300, 41000, 2750} {
c, err := publicCs.EncryptInt(amount)
check(err)
if total == nil {
total = c
} else {
total, err = total.Add(c)
check(err)
}
}
// bank decrypts the total, and publishes it with a proof
announced, proof, err := bankCs.DecryptWithProof(total)
check(err)
fmt.Println("announced:", announced) // 64550
// regulator verifies the announced total with the public key only
regulatorCs, err := lightphe.New(lightphe.Paillier, lightphe.WithKeyFile("public.txt"))
check(err)
valid, err := regulatorCs.VerifyDecryption(total, announced, proof)
check(err)
fmt.Println("announced total verified:", valid) // true
// a massaged total doesn't verify with the same proof
valid, err = regulatorCs.VerifyDecryption(total, big.NewInt(60000), proof)
check(err)
fmt.Println("massaged total verified:", valid) // false
}
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.List;
// bank builds the cryptosystem, keeps the private key and publishes the public key
LightPHE bankCs = LightPHE.builder().algorithmName("Paillier").build();
bankCs.exportKeys(Path.of("public.txt"), true);
// branches encrypt their transactions of the day with the public key, and they are summed encrypted
LightPHE publicCs = LightPHE.builder().algorithmName("Paillier").keyFile(Path.of("public.txt")).build();
Ciphertext total = List.of(12500L, 8300L, 41000L, 2750L).stream()
.map(publicCs::encrypt)
.reduce(Ciphertext::add)
.orElseThrow();
// bank decrypts the total, and publishes it with a proof
Proven<BigInteger> announced = bankCs.decryptWithProof(total);
assert announced.value().equals(BigInteger.valueOf(64550));
// regulator verifies the announced total with the public key only
LightPHE regulatorCs = LightPHE.builder().algorithmName("Paillier").keyFile(Path.of("public.txt")).build();
assert regulatorCs.verifyDecryption(total, announced.value(), announced.proof());
// a massaged total doesn't verify with the same proof
assert !regulatorCs.verifyDecryption(total, BigInteger.valueOf(60000), announced.proof());
import { LightPHE } from 'lightphe-ts';
// bank builds the cryptosystem, keeps the private key and publishes the public key
const bankCs = new LightPHE({ algorithmName: 'Paillier' });
bankCs.exportKeys('public.txt', true);
// branches encrypt their transactions of the day with the public key, and they are summed encrypted
const publicCs = new LightPHE({ algorithmName: 'Paillier', keyFile: 'public.txt' });
const total = [12500, 8300, 41000, 2750]
.map((amount) => publicCs.encrypt(amount))
.reduce((sum, c) => sum.add(c));
// bank decrypts the total, and publishes it with a proof
const [announced, proof] = bankCs.decryptWithProof(total);
console.assert(announced === 64550n);
// regulator verifies the announced total with the public key only
const regulatorCs = new LightPHE({ algorithmName: 'Paillier', keyFile: 'public.txt' });
console.assert(regulatorCs.verifyDecryption(total, announced, proof));
// a massaged total doesn't verify with the same proof
console.assert(!regulatorCs.verifyDecryption(total, 60000n, proof));
The announced 64,550 verifies, and a massaged 60,000 doesn’t. A proof is also bound to its ciphertext: it doesn’t verify for a re-randomized copy, even though that copy encrypts the same total. Swap Paillier for Exponential ElGamal with prime_order = True and the code stays the same, only the proof inside changes from a randomness to a Chaum-Pedersen challenge and response. Java snippets use assert for brevity, so run them with -ea to enable assertions.
Proof of Partial Decryption
A single key holder is a single point of trust, and often a single point of failure, so many systems split the private key among a committee, any t of whom decrypt together. Each member produces a partial decryption with its own share, and anyone combines them into the plaintext. That brings a new risk: a dishonest member can send a wrong partial decryption, and the combined result is silently wrong. Worse, since the combining coefficients are public, a cheater can shift the result by any amount it likes—add 50 votes to its own party, or hide a loss in a company’s books.
The fix is the same idea as above. When the key is split, every member’s share gets a public verification key, v_i = g^(share_i) for the ElGamal family. A partial decryption is c1^(share_i), and the member proves with Chaum-Pedersen that the same share is behind both. Paillier and Damgard-Jurik use a similar proof over verification keys, which needs keys generated with safe_primes = True. The combiner checks every proof, discards the invalid ones, and as long as t honest members remain, it still gets the correct result. And anyone can check a single member’s proof to find out exactly who cheated.
Example: Two of Three Auditors
Three auditors hold the shares of a key protecting a company’s encrypted transactions, and any 2 of them can open the total. One auditor was bribed to hide a loss, so instead of its partial decryption of the total, it sends a partial decryption of another ciphertext.
from lightphe import LightPHE # dealer splits the private key among 3 auditors, any 2 of them can decrypt dealer_cs = LightPHE(algorithm_name = "Exponential-ElGamal", prime_order = True) share_keys = dealer_cs.generate_threshold_keys(threshold = 2, parties = 3) dealer_cs.export_keys(target_file = "public.txt", public = True) auditors = [LightPHE(algorithm_name = "Exponential-ElGamal", keys = keys) for keys in share_keys] public_cs = LightPHE(algorithm_name = "Exponential-ElGamal", key_file = "public.txt") # company's encrypted transactions in thousands are summed encrypted total = public_cs.encrypt(120) + public_cs.encrypt(340) + public_cs.encrypt(95) # auditor 1 was bribed to hide a loss, so it sends a partial decryption of another ciphertext. # the others decrypt the total honestly, and everyone attaches a proof bribed = auditors[0].partial_decrypt(public_cs.encrypt(900), prove = True) partials = [bribed] + [auditor.partial_decrypt(total, prove = True) for auditor in auditors[1:]] # anyone verifies each partial decryption with the public key, and finds the bribed auditor assert [public_cs.verify_partial_decryption(total, partial) for partial in partials] == [False, True, True] # the forged partial decryption is discarded, and the 2 honest auditors decrypt the total assert public_cs.combine_partial_decryptions(total, partials, verify = True) == 555
package main
import (
"fmt"
"log"
"github.com/serengil/lightphe-go/lightphe"
)
func check(err error) {
if err != nil {
log.Fatal(err)
}
}
func main() {
// dealer splits the private key among 3 auditors, any 2 of them can decrypt
dealerCs, err := lightphe.New(lightphe.ExponentialElGamal, lightphe.WithPrimeOrder(true))
check(err)
publicKey, shareKeys, err := dealerCs.GenerateThresholdKeys(2, 3)
check(err)
publicCs, err := lightphe.New(lightphe.ExponentialElGamal, lightphe.WithKeys(publicKey))
check(err)
var auditors []*lightphe.Cryptosystem
for _, keys := range shareKeys {
auditor, err := lightphe.New(lightphe.ExponentialElGamal, lightphe.WithKeys(keys))
check(err)
auditors = append(auditors, auditor)
}
// company's encrypted transactions in thousands are summed encrypted
var total *lightphe.Ciphertext
for _, amount := range []int64{120, 340, 95} {
c, err := publicCs.EncryptInt(amount)
check(err)
if total == nil {
total = c
} else {
total, err = total.Add(c)
check(err)
}
}
// auditor 1 was bribed to hide a loss, so it sends a partial decryption of another ciphertext.
// the others decrypt the total honestly, and everyone attaches a proof
other, err := publicCs.EncryptInt(900)
check(err)
bribed, err := auditors[0].PartialDecrypt(other, true)
check(err)
partials := []*lightphe.PartialDecryption{bribed}
for _, auditor := range auditors[1:] {
partial, err := auditor.PartialDecrypt(total, true)
check(err)
partials = append(partials, partial)
}
// anyone verifies each partial decryption with the public key, and finds the bribed auditor
for i, partial := range partials {
valid, err := publicCs.VerifyPartialDecryption(total, partial)
check(err)
fmt.Printf("auditor %d honest: %v\n", i+1, valid) // false, then true, true
}
// the forged partial decryption is discarded, and the 2 honest auditors decrypt the total
result, err := publicCs.CombinePartialDecryptions(total, partials, true)
check(err)
fmt.Println("total:", result) // 555
}
import io.github.serengil.lightphe.LightPHE;
import io.github.serengil.lightphe.model.Ciphertext;
import io.github.serengil.lightphe.model.Keys;
import io.github.serengil.lightphe.model.PartialDecryption;
import java.math.BigInteger;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.List;
// dealer splits the private key among 3 auditors, any 2 of them can decrypt
LightPHE dealerCs = LightPHE.builder().algorithmName("Exponential-ElGamal").primeOrder(true).build();
List<Keys> shareKeys = dealerCs.generateThresholdKeys(2, 3);
dealerCs.exportKeys(Path.of("public.txt"), true);
List<LightPHE> auditors = shareKeys.stream()
.map(keys -> LightPHE.builder().algorithmName("Exponential-ElGamal").keys(keys).build())
.toList();
LightPHE publicCs = LightPHE.builder()
.algorithmName("Exponential-ElGamal")
.keyFile(Path.of("public.txt"))
.build();
// company's encrypted transactions in thousands are summed encrypted
Ciphertext total = publicCs.encrypt(120).add(publicCs.encrypt(340)).add(publicCs.encrypt(95));
// auditor 1 was bribed to hide a loss, so it sends a partial decryption of another ciphertext.
// the others decrypt the total honestly, and everyone attaches a proof
List<PartialDecryption> partials = new ArrayList<>();
partials.add(auditors.get(0).partialDecrypt(publicCs.encrypt(900), true));
for (LightPHE auditor : auditors.subList(1, 3)) {
partials.add(auditor.partialDecrypt(total, true));
}
// anyone verifies each partial decryption with the public key, and finds the bribed auditor
List<Boolean> honest = partials.stream()
.map(partial -> publicCs.verifyPartialDecryption(total, partial))
.toList();
assert honest.equals(List.of(false, true, true));
// the forged partial decryption is discarded, and the 2 honest auditors decrypt the total
assert publicCs.combinePartialDecryptions(total, partials, true).equals(BigInteger.valueOf(555));
import { LightPHE } from 'lightphe-ts';
// dealer splits the private key among 3 auditors, any 2 of them can decrypt
const dealerCs = new LightPHE({ algorithmName: 'Exponential-ElGamal', primeOrder: true });
const shareKeys = dealerCs.generateThresholdKeys(2, 3);
dealerCs.exportKeys('public.txt', true);
const auditors = shareKeys.map((keys) => new LightPHE({ algorithmName: 'Exponential-ElGamal', keys }));
const publicCs = new LightPHE({ algorithmName: 'Exponential-ElGamal', keyFile: 'public.txt' });
// company's encrypted transactions in thousands are summed encrypted
const total = publicCs.encrypt(120).add(publicCs.encrypt(340)).add(publicCs.encrypt(95));
// auditor 1 was bribed to hide a loss, so it sends a partial decryption of another ciphertext.
// the others decrypt the total honestly, and everyone attaches a proof
const bribed = auditors[0].partialDecrypt(publicCs.encrypt(900), { prove: true });
const partials = [bribed, ...auditors.slice(1).map((auditor) => auditor.partialDecrypt(total, { prove: true }))];
// anyone verifies each partial decryption with the public key, and finds the bribed auditor
const honest = partials.map((partial) => publicCs.verifyPartialDecryption(total, partial));
console.assert(honest.join() === 'false,true,true');
// the forged partial decryption is discarded, and the 2 honest auditors decrypt the total
console.assert(publicCs.combinePartialDecryptions(total, partials, { verify: true }) === 555n);
Anyone holding the public key can see that auditor 1’s partial decryption doesn’t match its verification key, and the combiner discards it with a warning: Partial decryption of party 1 has an invalid proof. It is discarded. The two honest auditors still open the correct total of 555. With Exponential ElGamal, verification is more than a nicety: decryption ends with a discrete logarithm search, and a forged partial decryption would send that search after a meaningless value, which could take forever. So verify first, then combine.
Required Cryptographic Features
1. Decryption as an exponentiation with the secret, as c1^x in ElGamal, so that its correctness can be tied to the public key with an equality of discrete logarithms. For Paillier and Damgard-Jurik, the ability of the key holder to recover the randomness of a ciphertext serves the same purpose.
2. A group where the proofs work: one of known prime order for the ElGamal family, which is why ElGamal and Exponential ElGamal keys need prime_order = True, and a modulus built from safe primes for the partial decryption proofs of Paillier and Damgard-Jurik.
3. Public verification keys for committees, one per member, published when the key is split, so that each partial decryption can be checked against its own share.
4. Homomorphism, to decrypt aggregates only. The proofs make a decryption verifiable, and homomorphism makes sure there is only one decryption worth doing: the total, never an individual record.
Which Algorithms Can Be Used, and Why
| Algorithm | Proof of decryption | Proof of partial decryption | How |
| ElGamal, Exponential ElGamal | âś… | âś… | Chaum-Pedersen, with keys generated with prime_order = True |
| Elliptic Curve ElGamal | âś… | âś… | Chaum-Pedersen on the curve, with default keys |
| Paillier, Damgard-Jurik | âś… | âś… | The recovered randomness for decryption, and proofs over verification keys for partial decryption, which need safe_primes = True |
| RSA, Okamoto-Uchiyama, Damgard-Geisler-Kroigaard, Bresson-Catalano-Pointcheval and others | ❌ | ❌ | LightPHE refuses them with does not support proofs of correct decryption, and they don’t support threshold decryption either |
More Scenarios
- Elections: An election authority announces that 5,000 of 8,000 encrypted ballots are yes, and publishes a proof, so every voter can check the announced result without trusting the authority. That’s exactly how our verifiable referendum ends.
- Outsourced analytics: A cloud service computes the average salary over a client company’s encrypted payroll and decrypts it with a proof, so an external auditor can confirm that the reported average wasn’t altered on its way to the board.
- Election trustees: Trustees nominated by competing parties decrypt the tally together, so a trustee who tries to add 50 votes to its own party is detected and outvoted by the honest ones.
- Federated learning: Servers of a committee decrypt the sum of encrypted model updates from thousands of phones, so a compromised server cannot slip a manipulated average into the global model.
- Health statistics: Hospitals holding shares of a key decrypt the yearly average of encrypted patient statistics together, so a single hospital cannot quietly bias the published figure in its favor.
Caveats
- A correct decryption of the right ciphertext: A proof shows that a ciphertext decrypts to the announced value. Everyone must also agree on which ciphertext that is, e.g. by recomputing the encrypted tally themselves from the published ballots.
- Proofs are opt-in: Partial decryptions are not proven by default. Turn on
provefor every member andverifyfor the combiner whenever the members don’t fully trust each other—which is usually why there’s a committee in the first place. - Keys must be generated for proofs:
prime_order = Truefor ElGamal and Exponential ElGamal, andsafe_primes = Truefor partial decryption proofs of Paillier and Damgard-Jurik. Existing keys without them can’t simply be upgraded.
Conclusion
Homomorphic encryption lets us compute on data nobody can see, and that includes the result, until someone with the key decrypts it. A proof of decryption turns that someone from a party we have to trust into a party we can check: for the ElGamal family with a Chaum-Pedersen proof that the same secret is behind the public key and the decryption, and for Paillier and Damgard-Jurik by simply revealing the ciphertext’s randomness. For committees, proofs of partial decryption catch a cheating member, name it, and let the honest majority finish the job.
With the encryptors kept honest in the previous post and the decryptors in this one, there’s one more trick left in the series: proving that a ciphertext contains a secret that someone else can check against a public key. That’s verifiable encryption, and it’s the topic of the final post.
Support this blog financially if you do like!
