Threshold decryption
With ElGamal encryption, whoever holds the secret key can read
every ciphertext. For an election, a sealed-bid market or a shared treasury, that’s too much
trust in one party. Threshold decryption splits the key among n trustees so that:
- any
t + 1of them can decrypt together; - any
tor fewer learn nothing, even if they collude; - the full secret key never exists anywhere, not even during setup.
The trustees create the key together with a distributed key generation (DKG): each trustee deals secret shares to the others and publishes commitments that let everyone check the shares, so a cheating dealer is caught and excluded. Afterwards each trustee holds one share, and everyone knows the joint public key that voters encrypt to.
ZeroJ implements the New-DKG protocol of Gennaro, Jarecki, Krawczyk and Rabin
(J. Cryptology 2007) as the profile
elgamal-jubjub-threshold-v1
(ADR-0053).
The private shares can travel over a public board, encrypted with HPKE (RFC 9180), following
dkg-share-delivery-hpke-v1
(ADR-0054).
Status
Section titled “Status”| Area | Status |
|---|---|
Threshold key generation and decryption (DkgParticipant, ThresholdKeyContext, ElGamal.decrypt with shares) | Experimental, pending review and external review |
Encrypted share delivery over a board (DkgShareDelivery, DkgShareDeliveryKeys, DkgKeyDirectory) | Experimental. Assumption A1 (HPKE envelopes can stand in for private channels) and the delivery contract await external review. |
| Secret operations (dealing, decryption shares) | Offline/isolated only: variable-time arithmetic, no constant-time claim |
Everything is in zeroj-circuit-lib, the same dependency as the
ElGamal guide.
Choose t and n
Section titled “Choose t and n”t is the number of corrupted trustees the scheme tolerates, not the number needed to
decrypt. Decrypting needs t + 1. The protocol requires an honest majority, 2t + 1 ≤ n, and
supports up to 64 trustees.
DkgConfig.create(t, n, …) | Decrypting needs | Tolerates |
|---|---|---|
create(1, 3, …) | any 2 of 3 | 1 corrupted trustee |
create(2, 5, …) | any 3 of 5 | 2 |
create(3, 7, …) | any 4 of 7 | 3 |
A 4-of-5 policy isn’t possible: it would need t = 3 with n = 5, which breaks the honest
majority. And remember the other side of the threshold: any t + 1 trustees who collude can
decrypt any single ciphertext, not just the total.
1. Run the key generation and decrypt a tally
Section titled “1. Run the key generation and decrypt a tally”This program runs a 2-of-3 key generation in one process, encrypts five 0/1 votes to the joint key, adds them, and has two trustees decrypt only the total. In a real deployment each trustee is a separate, isolated machine, and the messages travel over your own channels.
import org.zeroj.circuit.lib.jubjub.DkgConfig;import org.zeroj.circuit.lib.jubjub.DkgMessage;import org.zeroj.circuit.lib.jubjub.DkgParticipant;import org.zeroj.circuit.lib.jubjub.ElGamal;import org.zeroj.circuit.lib.jubjub.ElGamalCiphertext;import org.zeroj.circuit.lib.jubjub.ThresholdKeyContext;import org.zeroj.circuit.lib.jubjub.ThresholdKeyShare;import org.zeroj.circuit.lib.jubjub.VerifiedDecryptionShare;
import java.nio.charset.StandardCharsets;import java.security.SecureRandom;import java.util.ArrayList;import java.util.List;
/** * Three trustees run a threshold key generation (t = 1, n = 3: any 2 can decrypt), voters * encrypt 0/1 votes, the ciphertexts are added, and two trustees decrypt only the tally. * Everything runs in one process here; in reality each trustee is a separate, isolated host. */public class ThresholdTally {
public static void main(String[] args) { SecureRandom random = new SecureRandom();
// 1. Configuration, agreed by everyone (e.g. published in an election manifest). // t = faults tolerated; any t + 1 trustees decrypt; the rule is 2t + 1 <= n. List<byte[]> roster = List.of( // each trustee's authentication key (demo bytes) "trustee-1-auth-key".getBytes(StandardCharsets.UTF_8), "trustee-2-auth-key".getBytes(StandardCharsets.UTF_8), "trustee-3-auth-key".getBytes(StandardCharsets.UTF_8)); DkgConfig config = DkgConfig.create(1, 3, roster, "demo-election-2026".getBytes(StandardCharsets.UTF_8), 1);
// 2. Key generation: 7 rounds. Broadcasts go to everyone (sender included); // SHARE messages go privately to one recipient. List<DkgParticipant> trustees = new ArrayList<>(); for (int id = 1; id <= 3; id++) trustees.add(DkgParticipant.create(config, id, random)); List<DkgMessage> outgoing = new ArrayList<>(); for (DkgParticipant p : trustees) outgoing.addAll(p.start()); for (int round = 1; round <= 7; round++) { for (DkgMessage m : outgoing) { for (DkgParticipant p : trustees) { if (m.kind() != DkgMessage.Kind.SHARE) p.receiveBroadcast(m.sender(), m.encode()); else if (m.subject() == p.id()) p.receivePrivate(m.sender(), m.encode()); } } outgoing = new ArrayList<>(); for (DkgParticipant p : trustees) outgoing.addAll(p.closeRound()); // round deadline } List<ThresholdKeyShare> shares = new ArrayList<>(); for (DkgParticipant p : trustees) shares.add(p.result()); // each trustee keeps its own ThresholdKeyContext election = shares.get(0).context(); System.out.println("Threshold t = " + election.threshold() + ", qualified trustees " + election.qual()); System.out.println("All trustees agree on the key: " + (election.equals(shares.get(1).context()) && election.equals(shares.get(2).context())));
// 3. Voters encrypt 0 or 1 (width 1) under the joint key; the ciphertexts are added. int[] votes = {1, 0, 1, 1, 0}; List<ElGamalCiphertext> ballots = new ArrayList<>(); for (int vote : votes) ballots.add(ElGamal.encrypt(election, vote, 1, random)); ElGamalCiphertext total = ElGamalCiphertext.sum(ballots); System.out.println("Encrypted tally bound: " + total.bound());
// 4. Any t + 1 = 2 trustees publish decryption shares of the *total* only. List<VerifiedDecryptionShare> published = List.of( ElGamal.decryptionShare(shares.get(0), total), // trustee 1 ElGamal.decryptionShare(shares.get(2), total)); // trustee 3 (trustee 2 is away) long yes = ElGamal.decrypt(total, published, total.bound().longValueExact()); System.out.println("Yes votes: " + yes + " of " + votes.length);
// One share is not enough. try { ElGamal.decrypt(total, published.subList(0, 1), total.bound().longValueExact()); } catch (IllegalArgumentException e) { System.out.println("Refused: " + e.getMessage()); } }}Threshold t = 1, qualified trustees [1, 2, 3]All trustees agree on the key: trueEncrypted tally bound: 5Yes votes: 3 of 5Refused: threshold decryption needs at least t + 1 = 2 verified shares, got 1The key generation is seven rounds. In each round every trustee processes what it received and
sends its next messages. closeRound() is the round deadline: whatever didn’t arrive in time
counts as missing, which is how a silent trustee gets excluded instead of blocking everyone.
Two rules of the in-memory loop matter in real code too:
- Every trustee also receives its own broadcasts, and
SHAREmessages go only to their one recipient, throughreceivePrivate. - An abort is final. Start a new attempt with a new
attemptnumber inDkgConfig.create; never reuse one.
2. Deliver private shares over a public board (HPKE)
Section titled “2. Deliver private shares over a public board (HPKE)”Each trustee’s SHARE messages are secrets meant for one recipient. If you don’t have private
channels between trustees, ZeroJ can encrypt them with HPKE (RFC 9180, Base mode, with X25519,
HKDF-SHA256 and ChaCha20-Poly1305) and post the encrypted envelopes on the same public board
as everything else. The order of posts is part of the security, so the API enforces round
barriers:
- Round 0: announce. Each trustee generates fresh delivery keys for this attempt and posts the
announcement (106 bytes). Once the round-0 window is final, every trustee builds the same
DkgKeyDirectoryfrom it. - Round 1: envelopes first.
DkgShareDelivery.startreplacesstart(). Post the envelopes (223 bytes each,n(n−1)per attempt), and post theCOMMITMENTSbroadcasts only after the envelopes are final, or atomically with them. - Close round 1 only through
closeRound1, passing the round-1 window after its cutoff and after it’s final on the board. PlaincloseRound()refuses round 1. The delivery keys are destroyed here. - Rounds 2 to 7 are plain broadcasts, as in example 1.
This program runs the same 2-of-3 key generation as example 1, with every message on one board. Posts are signed with each trustee’s Ed25519 roster key, and the board doubles as the verifier the API asks for. Its last step, letting an outsider admit the key, is in section 3.
import org.zeroj.circuit.lib.jubjub.AuthenticatedDkgMessage;import org.zeroj.circuit.lib.jubjub.DkgAdmissionVerifier;import org.zeroj.circuit.lib.jubjub.DkgConfig;import org.zeroj.circuit.lib.jubjub.DkgKeyDirectory;import org.zeroj.circuit.lib.jubjub.DkgMessage;import org.zeroj.circuit.lib.jubjub.DkgParticipant;import org.zeroj.circuit.lib.jubjub.DkgShareDelivery;import org.zeroj.circuit.lib.jubjub.DkgShareDeliveryKeys;import org.zeroj.circuit.lib.jubjub.DkgTranscript;import org.zeroj.circuit.lib.jubjub.ThresholdKeyContext;
import java.nio.charset.StandardCharsets;import java.security.GeneralSecurityException;import java.security.KeyFactory;import java.security.KeyPair;import java.security.KeyPairGenerator;import java.security.SecureRandom;import java.security.Signature;import java.security.spec.X509EncodedKeySpec;import java.util.ArrayList;import java.util.Arrays;import java.util.HashMap;import java.util.HexFormat;import java.util.List;import java.util.Map;
/** * The same 2-of-3 key generation as ThresholdTally, but with no private channels: every message, * including each trustee's secret SHAREs (HPKE-encrypted), goes over one public board. Each post * is signed with the trustee's Ed25519 roster key. Afterwards an outsider (a voter) admits the * joint key from the board alone. */public class EncryptedBoardDkg {
/** An in-memory public board: posts per round window, each signed by its sender. */ static final class Board implements DkgAdmissionVerifier { final List<List<AuthenticatedDkgMessage>> rounds = new ArrayList<>(); final List<KeyPair> signers;
Board(List<KeyPair> signers) { this.signers = signers; for (int r = 0; r <= 7; r++) rounds.add(new ArrayList<>()); }
void post(int round, int sender, byte[] message) throws GeneralSecurityException { Signature s = Signature.getInstance("Ed25519"); s.initSign(signers.get(sender - 1).getPrivate()); s.update(message); rounds.get(round).add(new AuthenticatedDkgMessage(message, s.sign())); }
@Override // authenticity: a valid Ed25519 signature under the sender's roster key public boolean authenticate(int sender, byte[] rosterKey, byte[] message, byte[] authenticator) { try { Signature s = Signature.getInstance("Ed25519"); s.initVerify(KeyFactory.getInstance("Ed25519").generatePublic(new X509EncodedKeySpec(rosterKey))); s.update(message); return s.verify(authenticator); } catch (GeneralSecurityException | RuntimeException e) { return false; // never throw on attacker-supplied input } }
@Override // closure: this board is the agreed, complete record of each round window public boolean roundClosed(DkgConfig config, int round, List<byte[]> messages, byte[] evidence) { List<byte[]> expected = DkgTranscript.deliveredRound(config, round, rounds.get(round), this); if (expected.size() != messages.size()) return false; for (int i = 0; i < expected.size(); i++) { if (!Arrays.equals(expected.get(i), messages.get(i))) return false; } return true; } }
public static void main(String[] args) throws GeneralSecurityException { SecureRandom random = new SecureRandom(); int n = 3;
// Roster: each trustee's long-term Ed25519 public key (X.509-encoded). List<KeyPair> signers = new ArrayList<>(); List<byte[]> roster = new ArrayList<>(); KeyPairGenerator ed = KeyPairGenerator.getInstance("Ed25519"); for (int j = 1; j <= n; j++) { KeyPair kp = ed.generateKeyPair(); signers.add(kp); roster.add(kp.getPublic().getEncoded()); } DkgConfig config = DkgConfig.create(1, n, roster, "demo-election-2026".getBytes(StandardCharsets.UTF_8), 1); Board board = new Board(signers);
List<DkgParticipant> trustees = new ArrayList<>(); List<DkgShareDeliveryKeys> hpkeKeys = new ArrayList<>(); for (int j = 1; j <= n; j++) { trustees.add(DkgParticipant.create(config, j, random)); hpkeKeys.add(DkgShareDeliveryKeys.generate(config, j, random)); // fresh per attempt }
// Round 0: each trustee announces its HPKE key. Once the window is final, everyone // builds the same directory from it. for (DkgShareDeliveryKeys k : hpkeKeys) board.post(0, k.id(), k.announcement()); DkgKeyDirectory directory = DkgKeyDirectory.fromRound0(config, board.rounds.get(0), board);
// Round 1: envelopes (encrypted SHAREs) first; COMMITMENTS only after the envelopes are final. List<DkgShareDelivery.SealedDealing> dealings = new ArrayList<>(); for (DkgParticipant p : trustees) { DkgShareDelivery.SealedDealing d = DkgShareDelivery.start(p, directory, hpkeKeys.get(p.id() - 1), random); dealings.add(d); for (byte[] envelope : d.envelopes()) board.post(1, p.id(), envelope); // one per other trustee } for (int j = 1; j <= n; j++) { for (DkgMessage m : dealings.get(j - 1).broadcasts()) board.post(1, j, m.encode()); } // Barrier: after the round-1 window is final, each trustee processes all of it at once. List<DkgMessage> outgoing = new ArrayList<>(); for (DkgParticipant p : trustees) { outgoing.addAll(DkgShareDelivery.closeRound1(p, directory, hpkeKeys.get(p.id() - 1), board.rounds.get(1), board)); } System.out.println("HPKE keys destroyed after round 1: " + hpkeKeys.stream().allMatch(DkgShareDeliveryKeys::isDestroyed));
// Rounds 2-7: plain broadcasts, as without encryption. for (int round = 2; round <= 7; round++) { for (DkgMessage m : outgoing) { board.post(round, m.sender(), m.encode()); for (DkgParticipant p : trustees) p.receiveBroadcast(m.sender(), m.encode()); } outgoing = new ArrayList<>(); for (DkgParticipant p : trustees) outgoing.addAll(p.closeRound()); } ThresholdKeyContext trusteeView = trustees.get(0).result().context();
// Section 3: an outsider admits the joint key from the board. }}Output of the full program (the joint key is random):
HPKE keys destroyed after round 1: trueBoard posts: 18Voter's admitted key equals the trustees' key: trueJoint key: 325c41c481f9e3fc49d9cc400cb51928820fa74e4dff86dd8501e8e631b1522eTwo rules for your own board verifier: authenticate and roundClosed must return false,
never throw, on bad input; and roundClosed must only say true for the agreed, complete
record of that round. A roundClosed that always returns true defeats the protection.
HPKE here has no forward secrecy and isn’t post-quantum: a delivery key that leaks before it is destroyed exposes that trustee’s shares.
3. Let outsiders admit the joint key
Section titled “3. Let outsiders admit the joint key”Voters, talliers and validators hold no secret, but they need to know that the joint key really
came out of an honest key generation. ThresholdKeyContext.admit replays the public record and
returns the same key context the trustees hold:
// A voter, who holds no secret, admits the key from the signed board (rounds 1-6 + confirmations).List<AuthenticatedDkgMessage> transcript = new ArrayList<>();for (int r = 1; r <= 6; r++) { for (byte[] m : DkgTranscript.deliveredRound(config, r, board.rounds.get(r), board)) { for (AuthenticatedDkgMessage post : board.rounds.get(r)) { if (Arrays.equals(post.message(), m)) { transcript.add(post); break; } } }}Map<Integer, byte[]> closureEvidence = new HashMap<>();for (int r = 1; r <= 7; r++) closureEvidence.put(r, new byte[0]); // our Board needs noneThresholdKeyContext voterView = ThresholdKeyContext.admit(config, transcript, closureEvidence, board.rounds.get(7), board);System.out.println("Board posts: " + board.rounds.stream().mapToInt(List::size).sum());System.out.println("Voter's admitted key equals the trustees' key: " + voterView.equals(trusteeView));System.out.println("Joint key: " + HexFormat.of().formatHex(voterView.jointKey().encode()));DkgTranscript.deliveredRound filters each round down to the threshold protocol’s own messages,
dropping the HPKE envelopes and announcements that share the board.
Operating rules
Section titled “Operating rules”The library enforces the protocol; it can’t enforce how you run it. A deployment must:
- Isolate trustees. Each one runs on its own machine, under its own control.
- Fix the configuration in advance.
t,n, the roster and the application context come from a trusted source, such as a published election manifest, never from the network mid-run. - Never reuse an
attemptnumber for the same context. - Deliver private shares on time. A missed share triggers a complaint, and answering a complaint publishes that share. Timely private delivery is a precondition for secrecy.
- Decrypt once. Decrypt only the final total, after the deadline. Decrypting running totals and subtracting them reveals individual votes.
- Verify every decryption share you receive with
VerifiedDecryptionShare.verifyand a DLEQ proof. In example 1 the shares are “verified by construction” because one process made them; a separate tallier gets them as bytes.
Sizes and timings
Section titled “Sizes and timings”| Item | Size |
|---|---|
| Delivery key announcement | 106 bytes per trustee |
| Encrypted share envelope | 223 bytes, n(n−1) per attempt (about 0.9 MB at n = 64) |
| Joint key, key shares, decryption shares | 32 bytes each |
| Key generation, whole run in one process (Apple M4 Max) | Time |
|---|---|
t = 1, n = 3 | 62 ms |
t = 2, n = 5 | 176 ms |
t = 10, n = 21 | 4.5 s |
Key generation times are the plain-channel runs in the ElGamal benchmark; sizes are from the share delivery benchmark, which also times the HPKE-delivered runs. Network rounds, not computation, dominate a real ceremony.
Next steps
Section titled “Next steps”- Private voting: an encrypted tally decrypted by trustees
- Split trust between several parties: the pattern, and when to use it
- ElGamal encryption: keys, admission and proofs