htlp

A linearly homomorphic time-lock puzzle (LHTLP) in Rust, faithful to Malavolta and Thyagarajan, "Homomorphic Time-Lock Puzzles and Applications", CRYPTO 2019, Section 4.1.

This is a research proof-of-concept. It is not secure for production use, and it has not been independently audited. The modulus is generated locally, so the generator knows the trapdoor and can open any puzzle instantly; a real deployment requires a trusted-setup ceremony or a class-group instantiation with no trusted setup. The opening time is hardware-relative and is not a real-time guarantee; a faster solver opens puzzles sooner, as the LCS35 puzzle showed when it was solved roughly fifteen years ahead of its design schedule. The code has had no external security review: treat it as a reference implementation for study, not a vetted library.

What it does

It locks a value in Z_N inside a puzzle whose opening requires a fixed number of sequential squarings, and it lets you homomorphically add puzzles so that a single solve reveals only the sum of the locked values, never the individual inputs. Two demos ship with it:

• auction: a sealed-bid auction where several bids are locked, summed without being opened, and revealed only in aggregate (the total) after one solve.
• vote: a yes/no vote where 0/1 ballots are locked, tallied homomorphically, and only the yes-count is revealed, never any single ballot.

Both show a live squaring countdown (progress bar plus ETA) during the solve.

Build and run

This crate uses rug, which needs GMP and a C toolchain on the system.

# macOS
brew install gmp m4
# Debian/Ubuntu
sudo apt-get install -y build-essential m4 libgmp-dev

cargo build --release
cargo test --release

cargo run --release --bin htlp-demo -- auction
cargo run --release --bin htlp-demo -- vote
cargo run --release --bin htlp-demo -- bench       # squarings/sec + T-to-wall-clock
cargo run --release --bin htlp-demo -- classgroup  # transparent setup, NO trapdoor
cargo run --release --bin htlp-demo -- clhtlp      # transparent AND homomorphic
cargo run --release --bin htlp-demo -- clvote      # transparent vote, with ballot proofs

Transparent setup (no trapdoor)

The RSA path above has a trapdoor: whoever generates the modulus knows its factorization and can open any puzzle instantly, so it needs a trusted-setup ceremony for real security. The class-group paths remove this. They work in the class group of an imaginary quadratic order, whose class number (the group order) is unknown to everyone, so there is no trapdoor. Setup computes h = g^(2^T) by T public sequential squarings once (no secret, and doing so reveals nothing that helps solve faster). The module (htlp::classgroup) provides binary quadratic form arithmetic (reduce, compose, square, pow, all reduced after every operation).

• classgroup (cg_setup / cg_lock / cg_solve): a transparent time-lock encryption with a discriminant Delta = -p (a random negative prime). No trapdoor, but not homomorphic.
• clhtlp (cl_setup / cl_lock / cl_solve / cl_eval_sum): transparent and additively homomorphic, via the Castagnos-Laguillaumie framework. Messages live in Z_q, encoded in the order-q subgroup F (with Delta_q = q^2 * Delta_K, Delta_K = -p~ q, so q ramifies and |F| = q). Values are locked, homomorphically summed without opening, and one solve reveals only the aggregate mod q. This unifies the two properties the other two paths each have only one of.

The discrete log in F uses the Castagnos-Laguillaumie poly-time easy-DL (cl_easy_dl): lift to the maximal order, reduce to the principal form while tracking the transform, and read the generator from it (no square-root cost, so q is not bounded by baby-step-giant-step; tested against BSGS at small q and by direct round trip up to q about 2^48). Security rests on the unknown order of the hard subgroup, so Delta_K must be large; the demo uses a small one and is illustrative. Input validity: for 0/1 votes the CL path now has a per-ballot validity proof (cl_gen_ballot / cl_verify_bit, the class-group analog of the RSA ballot proof), so an aggregator rejects a ballot that does not lock a bit (the clvote demo rejects a forged "encode 7" ballot). Its soundness needs class-group-specific assumptions (strong-root and low-order), which is why the generator is taken in the odd-order squares subgroup. General-range bids (not just 0/1) still need a class-group range proof and are future work; and if proof verification is skipped, a malformed puzzle is detected at solve time (cl_solve returns Err) rather than corrupting the tally silently. See MATH.md Section 10 and SECURITY.md.

The public setup value h = g^(2^T) comes with a Wesolowski proof of exponentiation (poe_prove / poe_verify): a third party verifies h in a constant number of group operations rather than redoing the T squarings (the classgroup demo shows about a 50x speedup at T = 2^14, growing with T). The same proof certifies a solver's w = u^(2^T), which is the verifiable-delay-function use. See MATH.md, Section 9.

Benchmarks

Numbers below were measured on the machine this repository was developed on (an x86-64 Intel Broadwell-class CPU, 6 cores, about 5.8 GiB RAM, Linux), via cargo run --release --bin htlp-demo -- bench. Time-lock wall-clock is hardware-relative, so these are illustrative and will differ on your host; re-run bench to calibrate t for your own machine.

• Modular squarings per second (the sequential cost that sets the solve time): about 1.28 M/sec at a 1024-bit modulus, about 0.38 M/sec at 2048-bit.
• T-to-wall-clock at 2048-bit: T = 2^22 is about 11 s, 2^24 about 44 s, 2^26 about 175 s.
• Sequential-integrity check: a real T = 2^20 solve landed within about 6 to 14 percent of the predicted T / rate (ratios 1.06 at 1024-bit, 0.86 at 2048-bit), confirming the solve is genuinely T sequential squarings and not a shortcut.
• Homomorphic aggregation (PEval) is negligible next to the solve: about 3.9 microseconds per puzzle (38 ms to combine 10,000 ballots at 1024-bit).

API

The library exposes the four-function shape from the paper, the demo trapdoor oracle, and an overflow-safe wrapper:

• setup(modulus_bits, t) -> (PublicParams, Trapdoor)
• gen(&pp, &s) -> Puzzle
• solve(&pp, &z) -> Integer (the slow, sequential path)
• solve_with_progress(&pp, &z, |done, total| ...) -> Integer (same loop, with a progress callback)
• solve_with_trapdoor(&pp, &td, &z) -> Integer (instant, demo oracle, proves why the modulus is insecure)
• eval_sum(&pp, &[Puzzle]) -> Puzzle (homomorphic aggregation)
• gen_in_range(&pp, &s, &bound) -> Result<Puzzle, HtlpError> and eval_sum_in_range(&pp, &[Puzzle], &bound) -> Result<Puzzle, HtlpError> (the recommended overflow-safe path)
• max_aggregable_inputs(&pp, &bound) -> Integer (how many inputs are safe at a given per-input bound)
• gen_ballot(&pp, s_bit) -> (Puzzle, BitProof), prove_bit(&pp, &z, &r, s_bit) -> BitProof, and verify_bit(&pp, &z, &proof) -> bool (zero-knowledge proof that a puzzle locks a 0/1 ballot, so a malicious voter cannot corrupt the tally)
• gen_in_range_proved / verify_range (a bit-decomposition range proof that a bid is in [0, 2^L)) and gen_in_range_tight / verify_range_tight (a tight [0, B) for arbitrary B, via the two-sided Boudot decomposition), so a malicious bidder cannot exceed the cap; both have CL analogs (cl_*)
• classgroup::cg_setup / cg_lock / cg_solve (transparent, no-trapdoor time-lock encryption) and classgroup::cl_setup / cl_lock / cl_solve / cl_eval_sum (transparent AND additively homomorphic, Castagnos-Laguillaumie)
• classgroup::poe_prove / poe_verify (Wesolowski proof that h = g^(2^T), verified in O(lambda) instead of redoing the T squarings)
• classgroup::cl_gen_ballot / cl_prove_bit / cl_verify_bit (the CL analog of the ballot proof: zero-knowledge that a transparent homomorphic puzzle locks a 0/1 vote, so a malicious voter cannot corrupt the tally), and cl_gen_in_range_proved / cl_verify_range (the CL bid range proof, [0, 2^L) with 2^L <= q)

Ballot-validity proof

gen_ballot locks a 0/1 ballot and attaches a non-interactive zero-knowledge proof that it really is a bit, without revealing which. It is a Chaum-Pedersen equality-of-exponent statement (the same randomness ties u and v together) ORed over s=0/s=1 (Cramer-Damgaard-Schoenmakers), Fiat-Shamir compiled with SHA-256 over the full transcript. The vote demo verifies every ballot and shows a forged ballot (encoding 7) being rejected. Soundness that s is a bit holds in the random-oracle model; knowledge-soundness in the unknown-order RSA group rests on a strong-RSA-style assumption (this is a sigma-protocol argument, not a SNARK). For auction bids the same proof extends to a range proof by bit-decomposition: [0, 2^L) (gen_in_range_proved) and a tight [0, B) for arbitrary B (gen_in_range_tight, proving s and B-1-s both in [0, 2^L) and tying them to the public B-1). The auction demo uses a tight bound B = 1000 and rejects an over-cap bidder. See MATH.md for the full accounting.

Caveats

• Generated modulus retains a known trapdoor: insecure by construction, for demonstration only.
• Timing is hardware-relative; t squarings is not a wall-clock guarantee.
• The base g is sampled as a quadratic residue (the square of a uniform unit of Z_N*), so <g> stays inside QR_N, away from the Jacobi-symbol coset and the order-2 element -1, matching the construction in the paper. (See MATH.md, Section 6.)
• Not constant-time. Secret-exponent operations are hardened (GMP secure_pow_mod on the RSA path, a fixed-width Montgomery ladder pow_ct on the class-group path), but the underlying GMP arithmetic and key generation are not constant-time, so this is leakage reduction, not a guarantee. See SECURITY.md.
• Input validity: 0/1 ballots have a zero-knowledge proof (gen_ballot / verify_bit) and bounded bids have a bit-decomposition range proof, both power-of-two [0, 2^L) and tight [0, B) for arbitrary B (gen_in_range_tight / verify_range_tight), on both the RSA and CL paths, so a malicious voter or bidder cannot corrupt the aggregate (the vote, auction, and clvote demos all reject a cheater).
• The homomorphic sum is mod N; the true sum must stay below N to be read as an integer. This is now enforced: gen_in_range and eval_sum_in_range reject out-of-range messages and over-capacity batches rather than wrapping silently.

When not to use this

If you need precise release timing, use threshold timelock encryption (drand/tlock). If you need an encrypted mempool at scale, the deployed answer is threshold encryption (Shutter). HTLP's niche is committee-free aggregation of locked inputs where decentralization matters more than timing precision.

License

MIT OR Apache-2.0.