Anonymous group authentication: prove you hold a valid RSA-2048 signature from someone in a group of public keys, without revealing which key is yours.
Built as a Plonky2 circuit. The proof is ~168 KiB and verifies in a fraction of a second against a 2.6 KB verifier key, independent of how the ring is populated.
A ring signature lets a member of a group sign on the group's behalf while hiding which member signed. Anyone can check that the signature came from someone in the ring; nobody can narrow it further. Unlike a group signature, there is no manager and no way to de-anonymize after the fact — the anonymity is unconditional, not revocable.
This implementation gets there with a SNARK rather than the classical Rivest–Shamir–Tauman construction. The prover produces a zero-knowledge proof of the statement:
I know a signature
σand a modulusnsuch thatσ^65537 mod nequals the PKCS#1 v1.5 padding ofH(message), andnappears in the public ring{n₁ … n₃₂}.
The signature σ and the signer's modulus n are private witnesses. The message hash and the full ring are public inputs. The verifier learns the statement is true and nothing else.
Provenance. Forked from
entrohpy/CS355-project-ring-signature, the assignment scaffold for Stanford CS 355 (Advanced Topics in Cryptography). The scaffold supplied the BigUint gadgets, RSA host-side utilities, serialization, and the four example binaries. My contribution is the circuit itself — all ofsrc/gadgets/rsa.rs, which the scaffold left as fourunimplemented!()stubs.
Everything below is in src/gadgets/rsa.rs. Plonky2 config is PoseidonGoldilocksConfig with D = 2, built on CircuitConfig::standard_recursion_zk_config() — the zero-knowledge variant, which is what actually makes the proof hiding rather than merely succinct.
RSA verification needs σ^e mod n with e = 65537 = 2¹⁶ + 1. Naively that's 65,537 modular multiplications. Exploiting the binary structure of the exponent reduces it to 16 squarings plus 1 multiply, each followed by a rem_biguint reduction over 64 u32 limbs. In a circuit, where every operation is paid for in constraints rather than cycles, that 4,000× reduction is the difference between a circuit that compiles and one that doesn't.
Membership is enforced as an OR chain of 2048-bit equality checks: the signer's modulus is compared against every ring entry, and the disjunction of those comparisons is constrained to true.
let mut or_target = eq_biguint(&mut builder, &sig_pk_target, &pk_targets[0]);
for pk_target in pk_targets.iter().skip(1) {
let eq = eq_biguint(&mut builder, &sig_pk_target, pk_target);
or_target = builder.or(or_target, eq);
}
builder.connect(or_target.target, one);This is O(ring size) in constraints — a linear scan. A Merkle inclusion proof would make it O(log n) and is the natural next step for large rings, at the cost of committing to a fixed ring root. For a 32-member ring the linear scan is simpler and the constraint budget is not the binding limit.
Rings smaller than the circuit's fixed capacity get zero-padded to 32 entries. That creates an attack: if n = 0 were an acceptable witness, a non-member could "prove" membership by matching a padding slot. The circuit closes it by constraining the signer's modulus to be non-zero:
let zero_check = eq_biguint(&mut builder, &sig_pk_target, &zero_target);
let not_zero = builder.not(zero_check);
builder.connect(not_zero.target, one);A fixed-size circuit with variable-size input needs the padding value to be provably unusable. This is the constraint that makes the padding safe.
The message is hashed with Poseidon over the Goldilocks field (hash_or_noop::<PoseidonHash>), and the four resulting field elements are folded into a BigUint base GoldilocksField::ORDER. That digest is then wrapped in PKCS#1 v1.5 padding — 0x00 || 0x01 || 0xff…ff || 0x00 || H(m) — to 256 bytes, matching what a real RSA signer would have signed.
From a real run of the 32-key circuit:
| Artifact | Size |
|---|---|
| Proof (bincode, excluding public inputs) | 172,312 B (~168 KiB) |
| Public inputs | 16,904 B (2,112 field elements) |
| Verifier circuit data | 2,698 B |
| Prover circuit data | ~1.59 GB |
The 2,112 public inputs are 64 limbs of padded hash plus 32 × 64 limbs of ring moduli. The prover data is large because Plonky2 materializes the full prover key; the verifier side stays tiny, which is the asymmetry that makes this deployable — verification is cheap and portable even though proving is not.
Proving and verification times are not instrumented in the current code, so no timing numbers are quoted here.
git clone https://github.com/a-argy/RingSignature.git
cd RingSignature
cargo build --releaseRequires Rust nightly (edition 2024).
1. Generate a keypair — writes key.json (private) and key.pub.json (public modulus).
cargo run --example keygen --release2. Compile the circuit — emits circuit_prover.json (~1.59 GB) and circuit_verifier.json.
cargo run --example compile --release3. Prove. Provide the ring and message in public_input.json:
{
"public_keys": ["<base64-pubkey-1>", "<base64-pubkey-2>", "..."],
"message": "Class is canceled for the remainder of the quarter!"
}cargo run --example prove --release -- \
public_input.json circuit_prover.json key.pub.json key.jsonYour own key must appear in public_keys. Rings under 32 keys are zero-padded automatically; over 32 is rejected.
4. Verify — prints success.
cargo run --example verify --release -- \
circuit_verifier.json proof.json public_input.jsonVerification checks two things: that the proof's public inputs match the ring and message you expect, and that the proof itself is valid. Both matter — a valid proof over a different ring proves nothing about yours.
cargo test --releaseFour tests cover the padded-hash construction against a known vector, an all-zero ring that must fail to prove (exercising the non-zero-modulus guard), and a real end-to-end prove/verify with public-input checking.
Coverage gaps worth naming: there is no negative test for a signer whose key is genuinely absent from a well-formed ring, no test at the full 32-key ring size, and no statistical test of anonymity. The first is the one that matters most for soundness and is the next test I'd write.
| Proof system | Plonky2, PoseidonGoldilocksConfig, D = 2 |
| Circuit config | standard_recursion_zk_config() |
| RSA modulus | 2048-bit (two 1024-bit primes), e = 65537 |
| BigUint representation | 64 × u32 limbs |
| Message hash | Poseidon over Goldilocks |
| Signature padding | PKCS#1 v1.5 |
| Ring capacity | 32 keys (circuit is parametric; 32 is the example binaries' constant) |
| Membership check | OR chain of 2048-bit equalities, O(n) |
| Private witnesses | signature σ, signer modulus n |
| Public inputs | padded message hash, all 32 ring moduli |
A course project, not a production library. It has not been audited, the ring size is fixed at compile time, and the linear-scan membership check will not scale to large rings without moving to a Merkle commitment. The cryptographic construction and its soundness constraints are the point.
Licensed under either Apache License 2.0 or MIT, at your option.