piech.dev

Back to Projects github.com/Tenemo/threshold-elgamal

threshold-elgamal

npm version npm downloads

CI Tests coverage Documentation build

Node version License

threshold-elgamal is a TypeScript library for applications where a group of people need to submit encrypted scores, verify a shared public record, and reveal only the final result once enough participants cooperate.

In practice, that means browser-native finite-field ElGamal research prototypes for verifiable voting, encrypted group decisions, and other small-ceremony threshold workflows built on native bigint.

The published package has 0 runtime dependencies and ships as a fully self-contained library.

This library is a hardened research prototype. It has not been audited.

Start with these guides:

What the library includes

Encryption and validation

Threshold and protocol building blocks

Proofs, transport, and runtime

Installation

pnpm add threshold-elgamal

Runtime requirements

Quickstart

import {
    addEncryptedValues,
    decryptAdditive,
    encryptAdditive,
    generateParameters,
    getGroup,
} from "threshold-elgamal";

const group = "ffdhe3072" as const;
const { publicKey, privateKey } = generateParameters(group);
const suite = getGroup(group);
const messageBound = 10n;
const tallyBound = 20n;

const left = encryptAdditive(6n, publicKey, group, messageBound);
const right = encryptAdditive(7n, publicKey, group, messageBound);
const sum = addEncryptedValues(left, right, group);

console.log(decryptAdditive(sum, privateKey, group, tallyBound)); // 13n
console.log(suite.q > 0n); // true

All public APIs require explicit group selection. There is no implicit default suite.

Choosing an additive bound

For example, if each ballot is in 0..10 and you tally 50 ballots, encrypt each ballot with 10n and decrypt the final sum with 500n.

Documentation

Changes since v0.x.x

This library has been substantially rewritten around a smaller and stricter public surface. The current release keeps the validated group definitions, deterministic suite-derived h, secure randomness, additive ElGamal, key generation, threshold sharing, proofs, protocol helpers, transport primitives, and log-driven DKG reducers. Raw multiplicative mode has been removed.

The reason is privacy leakage at the individual ciphertext level, not any problem with the geometric mean itself. In multiplicative ElGamal, c2 = m * y^r mod p. The masking term y^r is always a quadratic residue because it stays inside the prime-order subgroup, so c2 inherits the Legendre symbol of m. Anyone observing the public ciphertext can compute that symbol and learn whether the plaintext score is in the quadratic-residue half of the score domain or the non-residue half. For a small domain such as {1, ..., 10}, that leaks about one bit per ballot and narrows each encrypted score from ten possibilities to roughly five before any decryption happens.

In additive ElGamal, c2 = g^m * y^r mod p. Both factors lie in the same prime-order subgroup, so c2 is always a quadratic residue. The Legendre symbol therefore leaks nothing about the individual plaintext. That makes additive mode strictly better on per-ballot privacy.

The remaining inference problem comes from publishing exact aggregates over small groups, and that problem exists in both designs. If a small board publishes an exact sum, participants can reason backward from the total and their own vote. If it publishes an exact product, they can do the same thing from the product. No homomorphic encryption scheme fixes that by itself. The only real mitigations are changing what gets published, suppressing small results, or adding noise, all of which change the voting system semantics.

This does create a real tradeoff: additive homomorphism gives sums and arithmetic means, while multiplicative homomorphism gives products and geometric means. If a scoring system truly requires geometric-mean behavior, additive mode does not reproduce that semantics directly. The library now chooses the mode that does not leak information from each posted ciphertext.

Development

pnpm install
pnpm run ci

DKG benchmark

For the DKG benchmark sweep, run:

pnpm run bench:dkg -- --group=ffdhe3072 --transport=X25519 3,11,21,31,41,51

Measurements were collected on this machine:

Results:

Participants (n)Threshold (k)Transcript messagesFull voting flowTranscript verificationTotal
322221.322 s729.839 ms22.052 s
1161662 min 6.564 s8.222 s2 min 14.786 s
21115268 min 2.140 s29.292 s8 min 31.432 s
3116108619 min 55.017 s1 min 5.193 s21 min 0.210 s
4121184639 min 54.015 s1 min 46.184 s41 min 40.199 s
512628061 h 9 min 19.986 s2 min 40.902 s1 h 12 min 0.888 s

The sweep scales superlinearly in both transcript volume and runtime, with the n=51, k=26 case producing 2806 transcript messages and taking just over 72 minutes for a full run plus verification on this hardware.

License

This project is licensed under MPL-2.0. See LICENSE.