### Slides

```Ran Canetti, Huijia (Rachel) Lin, Omer Paneth
Zero-Knowledge Proofs
• Completeness
• Soundness
∈ ℒ?

Zero-Knowledge Proofs
• Completeness
• Soundness
• Zero-knowledge
∈ℒ

∗
Zero-Knowledge
[Goldwasser-Micali-Rackoff 85]
•  ∗ learn nothing except " ∈ ℒ"
•  ∗ knows how to generate a proof
• There is a Simulator that
efficiently extracts a proof from  ∗
Two Types of
Zero-Knowledge proofs
Public-Coin Protocols
1 ←
1

2 ←
2

Concurrent Composition
1
2
1

2
3
3
4
4
∗
State of the Art
Constant-round public-coin
zero-knowledge
[Barak 01]
Concurrent zero-knowledge
[Richardson-Kilian 99]
[Kilian-Petrank 01]
[Prabhakaran-Rosen-Sahai 02]
Question
Is there a
public-coin concurrent
zero-knowledge protocol?
Yes! (well, almost)
Technical Motivation
Combine state of the art
simulation techniques
Applications to concurrent 2PC
[Goyal 13]
What are the existing
simulation techniques?
The Simulator
Simulator
proof transcript
∗
How does the simulator
∗
extract a proof from  ?
[Feige-Lapidot-Shamir 90]
Set a trapdoor statement such that
only  knows a trapdoor witness

Witness Indistinguishable
proof for  ∈ ℒ or
for a trapdoor statement

Simulator
∗
proof transcript
trapdoor
witness
How does the simulator
extract a trapdoor witness?
Rewinding
1

slot

4

Rewinding
1

′

′
+ ′ = Trapdoor witness
4

∗
Other Techniques
• Public-coin protocols
[Goldreich-Krawczyk 96]
• Concurrent composition
[Dwork-Naor-Sahai 98]
Public-Coin Protocols
0

′
Goldreich-Krawczyk
96:

′
∗

No black-box simulator
and ′ are independent
Public-Coin Protocols
The solution:
Non-black-box simulation
[Barak 01]
Concurrent Composition
1

1

4

4
∗
Concurrent Composition
1

′
1
1 ′

′

4
′
4 ′

′

∗
Concurrent Composition
1
′

1

1 ′

′
′′
′′′

′
′′
′′′
4
4 ′

′

∗
Concurrent Composition
The solution:
Rewinding with many slots
[Richardson-Kilian 99]
[Kilian-Petrank 01]
[Prabhakaran-Rosen-Sahai 02]
Current Techniques
rewinding
stand-alone
private-coin
zero-knowledge
rewinding with
many slots
concurrent
zero-knowledge
[RK,KP,PRS]
non-black-box
simulation
public-coin
zero-knowledge
[Barak 01]
This work
public-coin
concurrent
zero-knowledge
Barak’s Protocol (sketch)
= COM(Π)

Witness indistinguishable proof
for  ∈ ℒ or trapdoor statement
Trapdoor statement: the program Π predicts
the randomness  before it was sent
Barak’s Protocol
= COM(Π)

Witness indistinguishable proof
for  ∈ ℒ or Π c →
Trapdoor statement:
∃Π:  = COM Π ∧ Π  →

Barak’s Protocol
Soundness:
∗ can not commit to Π that predicts
Zero-knowledge:
Π = ∗

= COM(Π)
= COM( ∗ )

Witness indistinguishable proof
∗
Proof
that

() →
for  ∈ ℒ or Π c →
∗
Concurrent Barak
= COM( ∗ )

∗
Proof

Proof that  ∗ ()
→
Concurrent Barak
= COM( ∗ ⋅, , "Proof" )

Proof

∗ (, , "Proof") →
∗
Folklore Approach
[Deng-Goyal-Sahai 09]
[Pass-Rosen-Tseng 11]
[Goyal-Jain-Ostrovsky-Richelson-Visconti 13]
Folklore Approach
= COM( ∗ ⋅, , "Proof" )

Proof

∗
Folklore Approach
= COM(′)
′

Proof

Proof that ′() →
∗
Simulation Running Time
= COM(′)
= COM(′)
′

Proof that ′() →

Proof that ′() →
∗
′
Simulation Running Time

′

′
′
≥ 2  ′
′
Proof that  ′ () →
Proof that ′() →
′
Simulation Running Time
′ ≥ 2  ′
′ ≥ 2  ′ ≥ 4  ′
…
′
Proof that  ′ () →
Proof that ′() →
Proof that ′() →
′
′
Recursive Rewinding
1
2 ′
2
1

1 ′
2
2 ′
2 ′′
2 ′′′
3
3 ′
3 ′′
3 ′′′
4
4 ′
3
3 ′

∗
The Problem
Simulate
Prove a

≥2⋅
a proof
statement
stand-alone
private-coin
zero-knowledge
non-black-box
simulation
public-coin
zero-knowledge
[Barak 01]
concurrent
zero-knowledge
[RK,KP,PRS]
simulation
runtime is
exponential
concurrent
compassion
public-coin
concurrent
zero-knowledge
Concurrent Zero-Knowledge
1
1

Slot
1
2

2
6
Slot
Concurrent Zero-Knowledge
1

1
1 ′
1
1 ′
2
1 + 1 ′
2
6
∗
Concurrent Zero-Knowledge
1
1
1

2
2 ′
2
2 ′
2 + 2 ′
6
∗
Concurrent Zero-Knowledge

∗
Concurrent Zero-Knowledge

∗
Concurrent Zero-Knowledge

∗
The KP-PRS Strategy
The KP-PRS Strategy
The Protocol
1 = COM(Π)
1
…

Slot
Slot
= COM(Π)

WI proof for  ∈ ℒ or
∃i, Π:  = COM Π ∧ Π  →

Simulation
Black-box world - Rewinding
Non-black-box world – Proving
Simulation
= COM(′)

KP-PRS
Block

′
Round complexity
1+
log
for  > 0
Proof that  ′ ( ) →

∗
A Caveat
Simulation constructs many long proof
Solved by using memory delegation
Need all session to use one hash function
The Global Hash Model
ℎ ← ℋ
collision-resistant
hash function

The Global Hash Model
Breaking
soundness
Explicit uniform
reduction
Finding
collisions
The Global Hash Model
Uniform Hash Function

Protocol in the plain model

The Global Hash Model
SHA-256

Protocol in the plain model
from human ignorance [Rogaway 06]

GHM vs. CRS
Common reference
string model
Global hash
model
Simulated
with a trapdoor
Simulation for
every ℎ
Public-coin concurrent zero-knowledge
NIZK
Black-box impossibility
[Pass-Tseng-Wikström]
What is next?
• [Goyal 13]:
Public-coin concurrent zero-knowledge
with poly() rounds without a global hash
• Open question:
Public-coin concurrent zero-knowledge
with O(log ) rounds without a global hash
• Open question:
Concurrent zero-knowledge
with o(log ) rounds
[slide: Mira Blenekiy]
```