Introduction to Advanced Cryptography Techniques

Fine-Tuning Groth-Sahai Proofs Alex Escala Scytl Secure Electronic Voting Jens Groth University College London

Non-interactive zero-knowledge proofs Common reference string Statement Completeness: Prover can prove true statements Soundness: Prover cannot prove false statements Zero-knowledge: Proofs does not reveal anything else 2

NIZK proofs Statement: Here is a ciphertext and a document. The ciphertext contains a digital signature on the document. Circuit SAT Pratical pairing- based statements 1 GB Inefficient Statistical sampling techniques Groth 2006 1 KB Efficient Groth-Ostrovsky- Sahai 2012 (2006) Groth-Sahai 2012 (2008) Further reduction of size More efficient computation 3

Prime order bilinear groups Gen(1?) generates (?, ?, ?,?,?, ?, ) ?, ?,? finite cyclic groups of prime order ? Pairing ?: ? ? ? ? ??, ??= ? ?, ? ?? ? = ? , ? = ,? = ? ?, Deciding group membership, group operations, and bilinear pairing efficiently computable 4

SXDH bilinear groups Three types of groups Type I: Symmetric, i.e., ? = ? Type II: Efficiently computable isomorphism ?: ? ? Type III: No efficiently computable isomorphisms in either direction between the source groups ? and ? SXDH assumption in Type III bilinear groups Decision Diffie-Hellman problem hard in both ? and ? 5

Groth and Sahai give NIZK proofs for simultaneous satisfiability a set of equations ??1,??2, over variables ?? ?, ?? ?,??,?? ??of the forms Pairing product equations ???= 1 ?( ??, ??) ?( ??, ??) ? ??, ?? ? ? ?,? Multi-exponentiation equations ?? ?????= ? ?? ?? ?? ?? ? ? ?,? Quadratic equations ????+ ????+ ???????= ? mod ? ? ? ?,? 6

Linear algebra notation Equations ??1,??2, over variables ?? ?, ?? ? Pairing product equations ???= 1 ?( ??, ??) ?( ??, ??) ? ??, ?? ? ? ?,? Use additive notation for groups, multiplicative notation for pairings to get Equations ??1,??2, over variables ?? ?, ?? ? Pairing product equations ? ? + ? ? + ? ? ? = 0 7

Groth-Sahai proofs Commitments ??? ?1,??? ?2, Proofs that committed values satisfy equations ???1,???2, 8

Commit-and-prove system [Kil90,CLOS02,Fuc11] ??? ?1 ??? ?1 ???1 ??? ?2 ???2 9

Type-based commit-and-prove system We commit to values ? = (?,?) with a public part (type) ? and a (potentially) private part ? Gen(1?) generates a commitment key ?? Com(??;?;?) generates commitment ? to ? = (?,?) Prove(??;?,?1,?1, ,??,??) generates proof ? for commitments ?1, ,?? containing witnesses ?1, ,?? certifying the veracity of the statement ? Verify(??;?, ?1,?1, , ??,??,?) verifies the proof and either accepts or rejects 10

Commitments to elements in ? Common reference string contains ? = ? , and ? = ? ? Commitment to ? ? ??? ?;?,? = ?(0,1) + ? ? + ? ? = ( ? + ?? ? , ? + ?? + ?) This is an ElGamal encryption of ? Zero-knowledge simulation uses CRS with ? = ? , and ? = ? ? ( 0, ) This makes the commitment perfectly hiding (?,? ??) (?,? ??) 11

ElGamal encryption of elements in ? Common reference string contains ? = ? , and ? = ? ? ElGamal encryption of ? ? ??? ?;?,0 = ?(0,1) + ? ? + 0 ? = (?? ,? + ?) Using ElGamal encryption can save computation and reduce proof sizes Zero-knowledge simulation uses CRS with ? = ? , and ? = ? ? ( 0, ) ElGamal encryption is not perfectly hiding, so be careful (?,? ??) (?,? ??) 12

Public constants in ? Common reference string contains ? = ? , and ? = ? ? Public ? ? can be trivially committed ??? ?;0,0 = ?(0,1) + 0 ? + 0 ? = (0, ?) This is easily verifiable as commitment to ? Simplifies pairing product equations to (?,? ??) (?,? ??) ? ? ? = 0 where some of the ?? s and ?? s may be public constants ??, ?? or ElGamal encrypted 13

Type-based commitments Generalize commitment scheme to allow many different types of commitments ??? ?, ? commit to public element ? ??? ? commit by ElGamal encrypting element ??? ? commit using Groth-Sahai commitment ???? ? commit to (public) element ? Similar types for elements in ? and also types for committing to elements in ?? Commitment format is ???(??; ?,? ;?) where we view ? as a public part and ? as a (potentially private) part of the committed message 14

The base type ???? ?, ;0,0 = (0,1) + 0 ? + 0 ? = (0, ) Why not just use (??? ?, )? Because in general we do not know discrete logarithm of ? in (??? ?, ?) but for we do, which helps in the zero-knowledge simulation In general Groth-Sahai proofs are not (directly) zero-knowledge if ? ? = 0involves pairings of public elements, but as it turns out they are zero- knowledge if the discrete logarithms are known ??? 15

Commitments All commitments to elements in ? are of the form 0 1 ? + ???+ ??? ??? ????, ? , ??,?? = where for some types ??= 0 or ??= 0 Let ? = ( ?1| | ??) be a matrix of the commitments, then we have 0 1 ? = ? + ???+ ??? Similarly, the matrix of commitments to elements in ? is ? = ? 0,1 + ?? ? + ?? ? 16

Proofs The equation to be proved is ? ? = 0 The proof is of the form ? ?, ? ?, ? ?, ? ? ? ? = ? ? ?,+ ? ? ?+ ? ? ? + ? ? ? Completeness 0 1 0 1 = 0 + something randomized ? ? = ? + ???+ ??? ? 0,1 + ?? ? + ?? ? ? ? 0,1 + something with ?, ?, ?, ? = 17

Soundness A standard CRS has vectors ?,? such that ? ? = 0 ? ? = 0 ?? = 0 ?? = 0 Define ? = ? ? and ? = ?? The verification equation gives us ? ? ?? = ? ? ? ?+ ? ? ?+ ? ? ? + ? ? ? ? = 0 so for each equation (? ?) ( ??) = ? ? = 0 ? 0,1 = 1 0 1? = 1 18

Zero-knowledge simulation for commitments In the simulation, the CRS contains ? = ? , and ? = ? ? ( 0, ) Since ?, ? are linearly independent, commitments using a simulated CRS are perfectly hiding The simulator knows types, but not values. Simulates commitments as follows Commits to 0 instead of making real commitments Can open base commitment ( 0, ) as 0,1 0+ ? ? ?, i.e., it can interpret it as a commitment to 0 Makes ElGamal type commitments as encryptions of 0 Makes (??? ?, ?) commitments as ( 0, ?) 19

Zero-knowledge simulation for proofs Given an equation ? ? = 0 the simulator needs to simulate proof ? ?, ? ?, ? ?, ? ?such that ? ? = ? ? ?,+ ? ? ?+ ? ? ? + ? ? ? Simulator can create proof if it knows openings ? = or more generally, if for each non-zero matrix entry ??? it knows openings to ??= 0 or ??= 0 (Restrictions on use of ElGamal encryptions though in order for the security proof to work) 0 1 0 + ???+ ??? or ? = 0 0,1 + ?? ? + ?? ? 20

Prover-chosen common reference string Common reference string I will use this CRS ??,??? Faster computation at the cost of sending a separate CRS and proving it is correct Good trade-off when many proofs to the same verifiers 21

Size: Reduced from 16 to 6 group elements ~63% Computation: Reduced ~40% Conclusion Commitment to ? may be reused many times, making a commit- and-prove scheme ideal Working in the SXDH setting we have fine-tuned Groth-Sahai proofs as follows Simplified notation Generalized to type-based commit-and-prove schemes Enabled the use of ElGamal encryption Allowed pairings of base elements ?, in equations Permitted the prover to choose her own CRS Weak Boneh-Boyen signatures ? + ? ? ? = ? Save a couple of group elements in each proof by using ElGamal encryption We can handle base elements directly Prover can reduce computation by using own key 22