Slides

Report
Nir Bitansky and Omer Paneth
The Result
Assuming OT there exist a
resettably-sound ZK protocol
(Previous constructions of
resettably-sound ZK relied on CRHF)
Zero-Knowledge Proofs
Zero
Knowledge
Soundness
 ∈ ℒ?


Zero-Knowledge Proofs
Soundness
∉ℒ
∗

Zero-Knowledge Proofs
Zero
Knowledge
∈ℒ

∗
Intuition:
 ∗ “knows” how to generate a proof itself!

∗
We can efficiently extract a proof from  ∗
The Simulator
Accepting transcript:
∗
Simulator
The Simulator
∗

≈
∗
Simulator
Black-Box Simulator
∗
Black Box
Simulator
Non-Black-Box Simulator

∗
Non Black Box
Simulator
Black-Box vs. Non-Black-Box
Can Non-Black-Box Simulation
really achieve more than
Black-Box Simulation?
Black-Box vs. Non-Black-Box
Constant-round public-coin ZK
(for NP, with negligible soundness error)
Not considering 3-round ZK from KEA
[Hada-Tanaka 98, Bellare-Palacio
04]
CRHF + PCP
Argument
Black Box
Simulator
[Goldreich-Krawczyk 90]
Non Black Box
Simulator
[Barak 01]
Black-Box vs. Non-Black-Box
Black Box
Simulator
Non Black Box
Simulator
Constant-round public-coin ZK
GK90,B01
Resettably-sound ZK
BGGL01
Constant-round bounded-concurrent ZK and MPC
B01,PR03
Constant-round ZK with strict polynomial-time
simulation\knowledge extraction
BL02
Simultaneously resettable ZK and MPC
DGS09,GM11
Constant-round covert MPC
GJ10
Constant-round public-coin parallel ZK
PRT11
Simultaneously resettable WI proof of knowledge
COSV12
Non-Black-Box Simulation
BGGL01,B01,PR03,BL02,DGS9,GS09,
GM11,GJ10,PRT11,COSV12…
Barak
Barak 01
01
Non-Black-Box Simulation
BGGL01,B01,PR03,BL02,DGS9,GS09,
GM11,GJ10,PRT11,COSV12…
Barak 01
CRHF + PCP
Barak’s ZK Protocol
The FLS paradigm: [Feige-Lapidot-Shamir 99]
Generation protocol for
trapdoor 

Witness indistinguishable
proof that  ∈ ℒ or
 “knows” 

Barak’s ZK Protocol
The FLS paradigm: [Feige-Lapidot-Shamir 99]
A proof generated using a witness for  ∈ ℒ
and a proof generated using the trapdoor 
are protocol
indistinguishable
Generation
for
trapdoor 

Witness indistinguishable
proof that  ∈ ℒ or
 “knows” 

Barak’s ZK Protocol
Q: Can we have a trapdoor generation
protocol where  is public-coin?
A: Not using black-box simulation.
Barak’s ZK Protocol
Q: Can we have a trapdoor generation
protocol where  is public-coin?
A: (Barak 01) Yes!
Trapdoor is the entire code of 
∗
Problem of “Long” Trapdoor
(Or: problem of “short” messages)

Witness indistinguishable
proof that  ∈ ℒ or
 “knows”  =  ∗
 ∗ is an arbitrary
polynomial

Barak’s ZK Protocol
Fixing the problem:
1. Use a Universal Argument – a succinct
witness indistinguishable proof
based on PCPs [kilian 92, Barak-Goldreich 08]
2. Use a collision-resistant hash function to give a
shrinking commitment to trapdoor.
Non-Black-Box Simulation
BGGL01,B01,PR03,BL02,DGS9,GS09,
GM11,GJ10,PRT11,COSV12…
Barak 01
CRHF + UA\PCP
Are Barak’s techniques inherent in
non-black-box simulation?
No!
Can its applications be achieved
without collision-resistant hashing
and universal arguments?
Yes!
Resettable Protocols


Resettable Protocols


Resettable Protocols


Resettable ZK
[Canetti-Goldreich-Goldwasser-Micali 00]
∈ℒ

∗
Resettably-Sound ZK
[Micali-Reyzin 01,
Barak-Goldreich-Goldwasser-Lindell 01]
∉ℒ
∗

Resettably-Sound ZK
[Barak-Goldreich-Goldwasser-Lindell01,
Goldreich-Krawczyk 90]


Black Box
Simulator
Resettably-Sound ZK
Black Box
Simulator

∗

∗
Black Box
Simulator
Resettably-Sound ZK
[Barak-Goldreich-Goldwasser-Lindell 01]


Non Black Box
Simulator
Using CRHF and UA
The Result
Assuming only OT there exist a
constant-round resettably-sound ZK
protocol that does not make use of UA.
The Technique
A new non-black-box simulation technique
from the Impossibility of Obfuscation
Program Obfuscation
 is an obfuscation of a function family  :





Πk
 ()
≈
Πk

Obfuscation and ZK
If we can obfuscate  ∗ :
∗
∗
( )
Non Black Box
Simulator
Black Box
Simulator
Resettably-Sound ZK
Obfuscation and ZK
Assuming OWFs, there exist a family of
functions  that can not be obfuscated.
[Barak-Goldreich-Impagliazzo-Rudich-Sahai-Vadhan-Yang 01]
Resettably-Sound ZK
“Easy”
Impossibility of obfuscation
Obfuscation and ZK
Assuming OWFs, there exist a family of
functions  that can not be obfuscated.
[Barak-Goldreich-Impagliazzo-Rudich-Sahai-Vadhan-Yang 01]
Resettably-Sound ZK
“Hard”
Impossibility of obfuscation + OT
Unobfuscatable functions

1. ∀,  ← :
2. ∃, ∀ ≡  :





The Protocol
 = ()
=0


 ← 

Secure function
evaluation of  ()
 () where  = ()
Witness Indistinguishable
proof that  ∈ ℒ or
 “knows” 


Proof Idea - Resettable Soundness
 = ()

∗

 () SFE of  ()
 ← 


∗

Proof Idea – Zero Knowledge
Non Black Box Simulator
∗
 ≡ 


Proof Idea – Zero Knowledge
 ≡ 
 = ()

 ()

SFE of  ()
∗
Non Black Box Simulator
∗
 ≡ 


Proof Idea – Zero Knowledge
 ≡ 
 = ()

⊥
⊥
SFE of  ()



  =
⊥
∗

w.p.
w.p. 1 − 
Proof Idea – Zero Knowledge
 ≡ 
′ ≡  \ ⊥

′ ≡  \ ⊥

∗
⊥
 ()
…
1

∗
′ ≡  \ ⊥
∗
⊥
 ()
Proof Idea – Zero Knowledge
Non Black Box Simulator
 = ()
=0

 ()
∗

 ← 
SFE of  ()
 ≡ 
 
Witness Indistinguishable
proof that  ∈ ℒ or
 “knows” 
∗
The SFE Protocol

 = ()

∗

 ()
SFE of
 ()


∗
How
Howto
to instantiate
instantiate
this box?
box?
this
 = ()

 ()
SFE of
 ()

∗
 ≡ 
The SFE Protocol

Semi-honest SFE of  ()

ZK proof of knowledge

ZK proof of knowledge
 ()

The SFE Protocol

Semi-honest SFE of  ()

ZK proof of knowledge

ZK proof of knowledge
 ()

The SFE Protocol

Semi-honest SFE of  ()

Resettably-sound ZK POK
Based on resettably-sound ZK
[BGGL01,GS09]

Resettable ZK POK
 ()

The SFE Protocol

 = ()

∗

 ()
SFE of
 ()


∗
∉ℒ
∈ℒ
 = ()

 ()
SFE of
 ()

∗
 ≡ 
Instance-dependent SFE
∈ℒ
∉ℒ
SFE  of  ()
ZK
POK
Resettable POK
Resettable ZK
+ Strongly unobfuscatable functions
Instance-dependent SFE
 
1

 
3
∈ℒ
POK
∉ℒ
Resettable ZK WI
Instance-dependent SFE
Com()
 
1

 
3
∈ℒ
POK
∉ℒ
Resettable ZK
Instance-dependent SFE
Com ()
 
1

 
3
∈ℒ
POK
∉ℒ
Resettable ZK
Simulation Running Time
Non Black Box Simulator
∗
 ≡ 


Simulation Running Time
 ≡ 
′ ≡  \ ⊥

′ ≡  \ ⊥

∗
⊥
′ ≡  \ ⊥
∗
 ()
 ()
poly()
 =

…
1

∗
⊥
Proof Idea – Zero Knowledge
Non Black Box Simulator
 = ()
=0

 ()
∗

 ← 
SFE of  ()
 ≡ 
 
Witness Indistinguishable
proof that  ∈ ℒ or
 “knows” 
∗
Simulation Running Time
Non Black Box Simulator
∗
 ≡ 



w.p.
||
 =
poly() w.p. 1 − 
 
poly 
=⋅
+ 1 −  ⋅ poly  = poly 

Simulation Running Time
Non Black Box Simulator
∗

 ≡ 

() = (  2 )
 
poly 
=⋅

2
1
+ 1 −  ⋅ poly  >

Simulation Running Time
 = ()
=0

 ← 

 ()
SFE of  ()
Witness Indistinguishable
proof that  ∈ ℒ or
 “knows” 

Simulation Running Time
 = ()
=0

 ()

 ← 
SFE of  ()
=0

 ()
SFE of  ()
Witness Indistinguishable
proof that  ∈ ℒ or
 “knows” 

Simulation Running Time
Non Black Box Simulator
∗

 ≡ 

poly 
 =

 
poly 
=⋅

2
+ 1 −  ⋅ poly  = poly 
Comparison to [Barak 01]
# rounds
Assumptions
Uses
Trapdoor
PCP\UA Length
PublicCoin
Barak 01
O(1)
CRHF
Yes
Long
Yes
This work
O(1)
OT
No
Short
No
One More Application
Simultaneously resettable ZK
∉ℒ
∗
∈ℒ


∗
[BGGL 01]: Can a protocol be resettable ZK
and resettably-sound simultaneously?
Simultaneously resettable ZK
∉ℒ
∗
∈ℒ

[Deng-Goyal-Sahai 09]: Yes!

∗
Simultaneously resettable ZK
Resettably-sound ZK
Non-black-box simulation
Long trapdoor
Short trapdoor
Black-box simulation
Bounded concurrent ZK
Concurrent ZK
Resettable ZK
Simultaneously resettable ZK
Resettably-sound ZK
Non-black-box simulation
Short trapdoor
Black-box simulation
Concurrent ZK
Resettable ZK
Simultaneously resettable ZK
 = ()
=0
×

 ()
 ← 

SFE of  ()
 12]
[Cho-Ostrovsky-Scafuro-Visconti
Simultaneously Resettable
Witness Indistinguishable
proof that  ∈ ℒ or
 “knows” 
?


similar documents