The afternoon of the first day contained several interesting talks, however I particularly enjoyed the two talks on non-interactive zero knowledge (NIZK), so will aim to summarize those in this post.
Jens Groth gave the first invited talk of the conference, an hour-long lecture on NIZK. In such a protocol, a prover who knows a particular statement wishes to provide a verifier with a proof of this statement. The non-interactive requirement means that this must be done with just a single message. As with standard zero knowledge, the completeness, soundness and zero knowledge requirements must be satisfied. Jens focussed on NIZK in the Common Reference String (CRS) model, where both the prover and verifier have access to a shared string to allow for non-interactivity.
To prove an arbitrary statement in NP, it suffices to give a proof for an NP-Complete problem such as the Circuit Satisfiability problem (SAT). The basic idea behind doing this is to use a homomorphic commitment scheme. The prover then commits to the satisfying inputs of the circuit, and also to the intermediate values on every wire of the circuit. For each gate, the prover must then provide proofs of correctness of the commitments.
Groth focussed on techniques that require standard assumptions; either trapdoor permutations or factoring and pairing-based assumptions for more efficient proofs. These all lead to proofs of linear or quasi-linear length in the circuit size.
Despite being a theoretically nice way of proving any statement in NP, this method would be highly inefficient for proving statements other than SAT due to high constants in the reduction from most NP problems to SAT. It would seem, then, that for any particular language one has to come up with a new NIZK proof to overcome the efficiency barrier. Groth described a compromise: the pairing product equations problem is to find x,y satisfying:
e(a,x)e(x,y) = 1
e(b,y) = 1
when given group elements a,b. This has a direct application to group signatures and many other pairing-based languages, yet is also NP-Complete so can be used to create a proof for any NP language.
A complementary talk was given later in the afternoon by Helger Lipmaa, detailing more efficient NIZK proofs under slightly stronger assumptions. He avoids having to use random oracles, but requires pairing-based assumptions and knowledge extractors. To prove the validity of the commitments, he describes Hadamard Product and Permutation zero-knowledge arguments, which are highly parallelizable and can be
used to prove circuit satisfiability. The CRS length and prover computation time are both reduced from quadratic to quasi-linear.
Further Reading:
Kilian & Petrank '98 (original proof for NP using hidden random bits)
Groth & Sahai '06 (proof for NP using pairing product equations)
No comments:
Post a Comment