Towards Practical Generic Zero-Knowledge Protocols
Exploring the evolution of zero-knowledge protocols, this presentation by Claudio Orlandi from Aarhus University delves into the concepts of Zero-Knowledge from Garbled Circuits, Privacy-Free Garbled Circuits, and more. The talk discusses efficient methods for proving statements and touches on related work in the field, highlighting the significance of Zero-Knowledge Protocols in authentication and complex protocols.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
TOWARDS PRACTICAL (GENERIC) ZERO-KNOWLEDGE Claudio Orlandi Aarhus University
In this talk: 3 simple ideas from Jawurek, Kerschbaum, Orlandi Zero-Knowledge from Garbled Circuits, CCS 2013 Frederiksen, Nielsen, Orlandi Privacy-Free Garbled Circuits, EUROCRYPT 2015 Chuo, Orlandi The Simplest OT Protocol, ePrint (next week?)
Zero-Knowledge from Garbled Circuits Jawurek, Ferschbaum, Orlandi CCS 2013
Zero-Knowledge Protocols IP/ZK GMR85 Revolutionary idea in cryptography and CS Soundness: even a corrupted P cannot prove false statements Zero-Knowledge: even a corrupted V only learns that the statement is true (and not why) Important in practice Authentication Essential component in complex protocols What about efficiency?
Zero-Knowledge Protocols Many examples of efficient ZK for algebraic languages Discret Logarithm RSA Lattice ... What about non-algebraic statements? How do I prove I know x s.t. y=SHA(x) ? This work tries to fill this gap!
Related Work IKOS 07 ZK from (honest majority) MPC First step towards the MPC in the head approach Efficient NIZK/SNARK (GOS06,GGPPR13, ) Non-interactive Require heavy public key operations per gate
Zero-Knowledge vs Secure 2PC f,x f,y x,w x B A V P f(x,y) R(x,w) = true
Garbled Circuits Values in a box are garbled d [F] z f De Gb [Z] Ev [X] e En x Correct if z=f(x)
2PC from GC (Yaos protocol) Alice Bob x e ([Fy],e,d) Gb( f( ,y) ) [X] OT Soundness: B could garble a If A is corrupted and malicious function [Fy] [Z*] A([F],[X]), g f then [Z] Ev([Fy],[X]) De([Z*],d) is either e.g. g(x)= lsb(x) [Z] f(x) or z De([Z],d)
2PC secure against active adversaries? How can Bob prove that he garbled f without revealing any extra information? Plenty of (costly) solutions are known for 2PC Zero-Knowledge Cut-and-choose Etc. Can we do better for ZK?
ZK based on GC The main idea: In ZK the verifier (Bob) has no secrets! After the protocol, Bob can reveal all his randomness. Alice can simply check that Bob behaved honestly by redoing his entire computation.
Prover Verifier w e ([F],e,d) Gb( f,r ) OT [W] Prover work ~ 2x passive Yao Passive Yao Communication ~ [F] Verifier work ~ Passive Yao [Z] Ev([F],[W]) Com([Z]) reveal r, e If [F]=Gb(f,r) (and check OTs) [Z] z De([Z],d) (else abort)
CCS Implementations Code not open-source, but easily reproducible FastGC garbled circuits implementation Smart-Tillich optimized circuits: AES, MD5, SHA GCParser to combine the two above SCAPI for implementing OT (using elliptic curves)
Runtime (rough estimates) Proof of c=AES(k,m) for secret k and public (c,m) AES: 35k gates (7k ANDs/28k XORs) Communication: 204kB (98% GC) Runtime: OT: 29.4ms (Using Chou-Orlandi OT) (|w|=128) Garbling: 721 s (Using JustGarble GaXR) Eval: 273 s Total (Garble+OT+Eval+Garble) ~ 31.2ms (+network)
Privacy-Free Garbled Circuits Frederiksen, Nielsen, Orlandi EUROCRYPT 2015
Garbled Circuits d [F] z f De Gb [Z] Ev [X] e En x Correct if z=f(x)
Main idea In 2PC GC ensure that evaluator does not learn internal values In Yao garbled circuits evaluation must be oblivious But in ZK the prover knows all the input bits! He also knows all internal wires values Can we optimize? Yes!
Garbling Schemes without Privacy Conceptual contribution: Natural separation between privacy and authenticity Concrete efficiency: Better constants in garbled circuit Can we construct garbling schemes tailored to specific applications, which are more efficient than Yao s original construction?
Garbling a Circuit ([F],e,d) Gb(f) K10,K11 Choose 2 random keys Ki0,Ki1for each input wire K20,K21 For each gate compute (Z0,Z1,gg) Gb(L0,L1,R0,R1) Ki0,Ki1 Output e=(Ki0,Ki1) for all input wires d=(Z0,Z1) [F]=(ggi) for all gates i Z0,Z1
Evaluating a GC [Z] Ev([F],[X]) K1a Parse [X] as (K1x1,K2x2, ) for all input wires K2b Parse [F] as (gg1,gg2, ) for all gates Kic For each gate compute Zg(a,b) Ev(La,Rb,gg) Output [Z]=Z Z
Garbling a Gate A (privacy-free) garbled gate is a gadget that given two inputs keys gives you the right output key (and nothing else) L0,L1 R0,R1 AND/XOR (Z0,Z1,gg) Gb(L0,L1,R0,R1) Zg(a,b) Ev(La,Rb,gg) //and not Z1-g(a,b) Z0,Z1
Garbling w/o free-XOR (GRR1) Gb_AND(L0,L1,R0,R1) Output keys: Z1= H(L1,R1) Z0= H(L0) Send: C = Z0 H(R0) Ev_AND(Lx, Ry, C) If(x = y = 1) output Z1= H(Lx, Ry) If(x = 0) output Z0= H(Lx) If(y = 0) output Z0= C H(Ry)
Garbling w/o free-XOR (GRR1) Gb_XOR(L0,L1,R0,R1) Output keys: Z0= L0 R0 Z1= L0 R1 Send: C = L0 R0 L1 R1 Ev_XOR(La, Rb, C) If(a = 0) output Z(a b)= La Rb If(a = 1) output Z(a b)= C La Rb
Conclusions & Open Problems Still a lot to be done with garbling schemes! Other specific purpose garbling schemes? Non-interactive ZK (w/o PKE/gate)?
The Simplest Oblivious Transfer Protocol Chou, Orlandi coming soon on ePrint
Diffie Hellman Key Exchange X = gx m Y = gy K = H(Yx) K = H(Xy) There is another key K = H( (X/Y)x) which Bob cannot compute! C = E(K,m) m = D(K,C)
The Simplest OT protocol b m0,m1 X = gx b=0 : Y = gy b=1 : Y = X/gy Y K0= H(Yx) K1= H((X/Y)x) Kb= H(Xy) C0= E(K0,m0) C1= E(K1,m1) E(( , ), m) = mb= D(Kb,Cb) ( + m, ( + m) )
The Simplest OT Protocol Complexity: Communication: 1ge/OT + 2 ctxt/OT + 1ge Computation: 3 exp/OT + 3 H/OT + 2 exp Security: UC vs. active adversary with programmable RO Performances: ~5000 OT/s Implementation based on Bernstein s Curve25519
