Innovative Cryptography Techniques

One-out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin Jens Groth University College London Markulf Kohlweiss Microsoft Research

One-out-of-many statement One of them holds gold! But I will not tell you which one! Prover Verifier

One-out-of-many proof Zero-knowledge Remains secret which one of them holds gold Soundness Only accept if one of them holds gold Argument Prover Verifier

Ring signature Ring signature One of them signed, but secret who it was Construction Non-interactive one-of- many argument of knowledge of a secret key corresponding to one of their public keys

Zerocoin Coin spending Serial number 1001101 Anonymity Each coin has unique secret serial number known only to owner Use one-of-many proof to demonstrate one of the coins has this serial number

Membership proof 2 One-out-of-many proof that secret committed value belongs to a list ?

One-out-of-many proof for commitment to 0 Statement: ?0, ,?? 1 Claim that one of them is commitment to 0 Soundness Statement is true, there is a commitment to 0 Zero-knowledge Witness ,? ?.?. ? = commit(0;?) Remains secret which commitment contains 0 Prover Verifier

Pedersen commitments Setup with commitment key ?? that specifies group ? of prime order ? and two random generators ?, ? Commitment to ? ?? using randomness ? ?? computed as ??????;? = ?? ? Additively homomorphic = ? ? ? + ? Perfectly hiding Computationally binding Assuming hard to compute discrete logarithms

Sigma-protocols Statement ? ? Witness ? s.t. ?,? ?? ? ? ?? ? Prover Verifier ?-special soundness Compute witness from answers to ? different challenges Special honest verifier zero-knowledge Given challenge ? simulate transcript (?,?,?)

Main result: one-out-of-many proof Sigma-protocol for one out of many commitments ?0, ,?? 1 being a commitment to 0 Perfect completeness Computational (log? + 1)-soundness Perfect special honest verifier ZK Rounds 3 Prover 2? expo. Verifier 2?/log? expo. Communication 4log? group + 3log? field For 256-bit elliptic curve groups 224 log? bytes Can use Fiat-Shamir heuristic to make it non- interactive for ring signatures and zerocoin

Binary tree ? = 2? ?00= 1 0 ?10= 0 ?11= 1 1 ?01= 0 ?11= 1 ?01= 0 ?0 ?3 ?2 ?1 Want SHVZK Cannot reveal ? = com(0;?) ?? is commitment to 0 ? 1?? Want to show ?=0 Equivalently write ? = ?1 ?? and = 1 ? ? ?=1 ??? ? is commitment to 0 ? 1?? Want to show ?=0

Commit to path ? = 2? 0 1 ?0 ?3 ?2 ?1 ? = com(0;?) Prover commits to 1, , ? ? ?= com( ?;??) Standard Sigma-protocol for knowledge of opening of commitment to ? {0,1} Run ? arguments for ? 1, ,? ? in parallel

Build ? polynomials of degree ? in challenge ? ?= ? ? {0,1} and ?? Polynomials ?0? , ,?? 1? defined by ?1, ,?? Communication ? ? = ?(log?) ?? Check ????= ? ?? ? ? ?? ??= ? ?+ ?? We have ??= ?1 ?? + ?? and ? ??= ?0 ?? ?? Define ??,1= ?? and ??,0= ? ?? and ? ? (??? ?? ??) = ?? ??+ ??? = ??,??= ?=1 ?=1

Use committed path to construct ? polynomials ??? = ?? ??+ ??,? 1?? 1+ + ??,0 in a verifiable manner Both prover and verifier can compute ? 1 ???= ?? ? 1 ? 1 ? 1 ?? ?? ?? ??=? ?? ?? ? ? ? ? ?=0 ?=0 ?=0 ?=0 Prover sends ??0, ,??? 1 before challenge ? If ? = com(0;?) then ?=0 Otherwise negligible chance of commitment to 0 ??? ?=0 ?? is a commitment to 0 ? 1?? ? 1???

One-out-of-many proofs Sigma-protocol for one out of many commitments ?0, ,?? 1 being a commitment to 0 Rounds 3 Prover 2? expo. Verifier 2?/log? expo. Communication 4log? group + 3log? field Can save computation if prover knows openings of all commitments instead of just one of them Rounds 3 Prover 3? log ? mult. 2?/log? expo. Verifier Communication 4log? group + 3log? field

Membership proof Have commitment ? = com(? ;?) and want to give argument of knowledge of opening to value in the list ? = {?0, ,?? 1} Give one-out-of-many proof for statement ?0= ? com ?0;0 , ,?? 1= ? com( ?? 1;0) Save computation since both prover and verifier know a lot about commitments Rounds 3 Prover 2? log ? mult. Verifier 2? mult. Communication 4log? group + 3log? field

Fiat-Shamir heuristic Statement ? ? Witness ? s.t. ?,? ?? Non-interactive argument ? ? Hash(?,?,???) ? ? = (?,?) Sigma-protocol has quasi-unique challenges Hard to compute many different answers to a challenge ? Implies non-interactive argument is simulation-extractable in the random oracle model

?0= ?0 Ring signatures ?1= ?1 ?2= ?2 Ring ? = ?0, ,?? 1 contains public keys of the form ?? Interpret them as commitments to 0, i.e., ??= com 0;?? = ?0 ?? Use Fiat-Shamir heuristic with challenge ? = Hash(??,?,?,?) to prove knowledge of some ? = com(0;? ) Signature is the non-interactive argument ? = (?,?)

Zerocoin Bulletin board with coins Each coin commitment ??= com ??;?? to a serial number ?? Spend a coin from a set ? = {?0, ,?? 1} anonymously by posting serial number ? and proving one of the coins in ? has this serial number Prove that one of ?0 com ?;0 , ,?? 1 com( ?;0) is commitment to 0 using Fiat-Shamir challenge ? = Hash(??,?,?,?,?) Serial number prevents double spending Zero-knowledge guarantees anonymity

Summary Sigma-protocol for one out of many commitments ?0, ,?? 1 being a commitment to 0 Perfect completeness Computational (log? + 1)-soundness Perfect special honest verifier ZK Rounds 3 Prover 2? expo. Verifier 2?/log? expo. Communication 4log? group + 3log? field Membership proof Ring signature Zerocoin