Module mta_proofs 

Zero-knowledge proofs for the MtA protocol — GG18/GG20 Appendix A (Gennaro & Goldfeder, eprint 2019/114 A.1/A.2), the construction spec 70-cmp20 requires on every MtA ciphertext.

Two proofs, both sigma protocols made non-interactive via Fiat-Shamir (SHA-256 over the full transcript, challenge reduced mod q, the ECDSA group order):

• RangeProof (initiator): for Paillier ciphertext c = Γ^m·r^N mod N², proves knowledge of (m, r) with m ∈ [0, q³] — the “small ciphertext” guarantee that prevents the wrap-around attacks described in the paper.
• RespondentProof (responder, plain MtA): for c₂ = c₁^x·Γ^y·r^N mod N², proves knowledge of (x, y, r) with x ∈ [0, q³] and y ∈ [0, q⁷] — binding the response to the received ciphertext and bounding the mask.

The commitments use an auxiliary Strong-RSA modulus Ñ = P̃·Q̃ with P̃ = 2p̃+1, Q̃ = 2q̃+1 (safe primes) and h₁, h₂ ∈ Z*_Ñ with h₂ = h₁^w for discarded w — nobody (least of all the prover) knows the discrete log of h₂ in base h₁, which is what makes the h-commitments binding.

Trust model and limitations (audit ledger)

• A commitment key is generated by the VERIFIER and used by the OTHER party as prover. Never prove against a key you generated yourself — you would know the h₂/h₁ discrete log.
• The paper proves Ñ is of the correct form (safe-prime product) with an additional ZK proof ([Gennaro-Micciancio-Rabin]); this implementation generates such moduli honestly but does NOT yet prove their form to verifiers. A malicious verifier could mis-generate a key to break a prover’s privacy. Trusted-setup gap, tracked in the audit ledger.
• Soundness holds under Strong RSA over Ñ; size Ñ accordingly (the paper’s setting: 2048-bit Ñ alongside 2048-bit N).

Structs

CommitmentKey

Auxiliary commitment key (Ñ, h₁, h₂) — see the module docs.

RangeProof

Initiator’s range proof: knowledge of (m, r) with c = Γ^m·r^N mod N² and m ∈ [0, q³].

RespondentProof

Responder proof for plain MtA: knowledge of (x, y, r) with c₂ = c₁^x·Γ^y·r^N mod N², x ∈ [0, q³], y ∈ [0, q⁷].

Functions

generate_commitment_key

Generate a commitment key: Ñ = P̃Q̃ with P̃, Q̃ safe primes of prime_bits each, h₁ a random quadratic residue mod Ñ, and h₂ = h₁^w for uniformly random discarded w.

p256_order

The P-256 group order q, as the proofs’ range parameter.

prove_range

Prove that c = Γ^m·r^N mod N² opens to m ∈ [0, q³).

prove_respondent

Prove the responder statement for c₂ = c₁^x·Γ^y·r^N mod N², where r is the Paillier randomness used for the Γ^y term.

verify_range

Verify an initiator range proof for ciphertext c.

verify_respondent

Verify a responder proof binding c₂ to c₁ with bounded secrets.