Challenges in Constant-Round Public-Coin Zero-Knowledge Proofs
On the Implausibility of
Constant-Round Public-Coin
Zero-Knowledge Proofs
Yi Deng
IIE,Chinese Academy of Sciences (Beijing)
Joint work with
Juan Garay, San Ling, Huaxiong Wang and Moti Yung
1
On the Implausibility of Constant-Round
Public-Coin ZK Proofs
The problem:
Do constant-round public-coin ZK proofs exist?
Public-coin constructions are broadly applicable and
versatile
Deep connection to other fundamental problems,
such as the Fiat-Shamir Heuristic
2
On the Implausibility of Constant-Round
Public-Coin ZK Proofs
Earlier public-coin protocols
：
3-round public-coin ZK proofs for NP
[Blum 86,GMW86]
What
we want:
C
onstant-round
public-coin ZK proofs with
negligible
soundness error
3
On the Implausibility of Constant-Round
Public-Coin ZK Proofs
Parallel repetition doesn’t help much
parallelizing
Reduces soundness error
exponentially
Preserves round complexity
Pass
et al.
[PTW 10]
：
Parallel repetion for public-coin
protocol does not preserve BB ZK in
general
4
On the Implausibility of Constant-Round
Public-Coin ZK Proofs
Soundness only holds against PPT prover
Impossibility result for
black-box
simulation [GK96]
w.r.t. both
proof
and
argument
Surprisingly,
Barak broke the above
black-box barrier
,
constructing constant-round public-coin ZK
argument
for NP
5
On the Implausibility of Constant-Round
Public-Coin ZK Proofs
6
Prove (WIUA): x
L
OR
there
exists
∏
s.t.
Z = Com(h(∏))
and ∏(z) outputs r in time n
logn
Z = Com(h(
∏),s
)
Barak’s argument
x
L
P
V
r
Barak’s non-
b
lack-box
ZK argument
In the simulation, S computes
Z=Com(h(V*),s)
(using the code of V*)
h
On the Implausibility of Constant-Round
Public-Coin ZK Proofs
7
Prove (WIUA): x
L
OR
there
exists
∏
s.t.
Z = Com(h(∏))
and ∏(z) outputs r in time n
logn
Z = Com(h(
V*
)
,
s
)
x
L
S(V*)
V*
r
Striking properties
of Barak’s simulator
h
Straight-line
（
i.e., no rewinding
）
Uses the code of V*
without
understanding
it!
On the Implausibility of Constant-Round
Public-Coin ZK Proofs
8
Prove (WIUA): x
L
OR
there
exists
∏
s.t.
Z = Com(∏) and
∏(z) outputs r in time n
logn
Z = Com(h(
0
n
)
)
Barak’s protocol
x
L
P*
V
r
h
Two facts
1. There are too many pre-images
for a single hash value
2. There infinitely many different
codes
∏
1
, ∏
2
,… that compute the
same function ∏(z) = r
Is it
a
proof
system?
P* may be able to find a code
∏ such that ∏(z) = r
and
Z = Com(h(
0
n
)
) = Com(h(∏))
On the Implausibility of Constant-Round
Public-Coin ZK Proofs
Probably not
Would known NBB techniques help?
Earlier negative evidence (for arbitrary reduction) [BLV03]:
We give new
negative evidence
for
universal simulation case.
entropy-preserving hash
functions
exist
No
constant-round
public-coin ZK proofs
But
such hash functions cannot be
based on standard assumptions via BB
reduction
[BDGJKLW13]
9
On the Implausibility of Constant-Round
Public-Coin ZK Proofs
ZK property requires the
mere existence
of a simulator:
For every V*, there exists a simulator S
But we often prove ZK property by
.
Constructing a single
universal simulator S
for every V*
Almost all simulators are universal:
BB simulator
Barak’s NBB simulator
10
On the Implausibility of Constant-Round
Public-Coin ZK Proofs
Universal simulators
Our main result
For a
common type
of constant-round public-coin
proof system,
if it has a
universal simulator S
Then S can be used to distinguish some
non-trivial
functionality
of the (possibly obfuscated) code of V*
Canonical
ZK proof: It is sufficient to feed S with
only partial code of V* in simulation
All known ZK protocols are canonical
We will deal with
honest
public-coin
verifier
(functionalities)
Given a random tape r = [r
1
, r
2
, …, r
m
], r
i
: randomness for step i,
The honest verifier V(r)= [V
1
(r
1
), V
2
(r
2
),…, V
m
(r
m
)]:
the step i function: V
i
(hist, r
i
) = r
i
But we consider
Arbitrary code
of the
honest verifier functionality
V* = [V*
1
, V*
2
, …, V*
m
]
each V*
i
is
functionally equivalent (FE)
to some V
i
(r
i
):
V*
i
(hist)
≡
V
i
: V*
i
(hist)=V
i
(hist, r
i
) = r
i
11
On the Implausibility of Constant-Round
Public-Coin ZK Proofs
FE
Our main result
(3)
For a
common type
constant-round
public-coin
proof system,
if it has a
universal simulator S
S(x,V’,
V*
k
)
r
1
r
k-1
p
1
p
k-1
V
′
V*
k
V
1
.
.
.
V
k-1
?
S must encode some functionality property of
V*
k
in the session prefix
before the verifier’s
k-th step!
This is in sharp contrast with all
known public-coin protocols!
Known straight-line S: it
generates the prefix (r
1
, p
1,
, …
r
k-1
, p
k-1
)
before
executing
V*
k.
Distinguish functionality of
V*
k.
without executing
V*
k
?
This shows that constructing
constant-round public-coin ZK
proof (if exists) requires paradigm
shifting simulation technique!
12
There exist
a code
V
′
≡
[V
1
, V
2
, …, V
k-1
]
a set of verifier step k
(V
1
k
,…,V
t
k
)
a code
V*
k
≡ random one of (V
1
k
,…,V
t
k
)
On the Implausibility of Constant-Round
Public-Coin ZK Proofs
Proof sketch (step 1):
Lemma 1
(an improvement of Babai-Moran
derandomization
[BM88])
：
There exist
p
random tapes
(r
1
,r
2
,…r
p
)
，
s.t.
P*(
r
1
,r
2
,…r
p
)
r
i
1
r
i
m
p
1
p
m
V
i
=V(
r
i
)
r
i
=[
r
i
1
, r
i
2
,…, r
i
m
]
any false x
accept <1-1/p
P* knows the set of random
tapes from which V will
choose
On the Implausibility of Constant-Round
Public-Coin ZK Proofs
Let
m
be the round number
and
q
the length of a prover msg
Babai-Moran [BM88]:
p=q
m
Improved
:
p=(q/log n)
m
13
Proof sketch (step 2):
Lemma 2
：
There exists a false statement x and
p
random tapes
(r
1
,r
2
,…r
p
)
of
the verifier such that
P*(
r
1
,r
2
,…r
p
)
r
i
1
r
i
m
p
1
p
m
V
i
=V(
r
i
)
r
i
=[
r
i
1
, r
i
2
,…, r
i
m
]
a false x
accept < 1-1/p
S(V*)
r
i
1
r
i
m
p
1
p
m
V*
≡
V
i
=V(r
i
)
a false x
accept
w/ prob. 1
&
14
On the Implausibility of Constant-Round
Public-Coin ZK Proofs
Now we group the
p
verifiers
V
1
,…V
p
(
V
i
=V(
r
i
)) as follows:
If two verifiers
V
i
and
V
j
share the same first
k-1
next-message-
steps [V
1
,…,V
k-1
] (i.e., they share the same randomness up to the
(k-1)-st step), we put them in the same group
Proof sketch (last step):
V
1
V
2
V
K-1
15
On the Implausibility of Constant-Round
Public-Coin ZK Proofs
Proof sketch (last step):
V
1
V
2
V
K-1
Each represents a next-msg-function
(determined by the randomness used for this
step)
Each path represents a verifier
A tree represents a group of verifiers
16
On the Implausibility of Constant-Round
Public-Coin ZK Proofs
Now we group the
p
verifiers
V
1
,…V
p
(
V
i
=V(
r
i
)) as follows:
If two verifiers
V
i
and
V
j
share the same first
k-1
next-message-
steps [V
1
,…,V
k-1
] (i.e., they share the same randomness up to the
(k-1)-st step), we put them in the same group
We now have (a polynomial number of) trees
Proof sketch (last step):
V
n
V
1
V
2
V
K-1
17
On the Implausibility of Constant-Round
Public-Coin ZK Proofs
Proof sketch (last step):
V
n
We then prove that
there is a tree sharing the same
[V
1
,…,V
k-1
], but have
t different k-th steps, V
1
k
,…,V
t
k
, and
a code
V′
≡
[V
1
,…,V
k-1
]
V
1
V
2
V
K-1
V′
V
1
K
V
2
K
V
t
K
18
On the Implausibility of Constant-Round
Public-Coin ZK Proofs
Proof sketch (last step):
S(
V
′,
V*
k
)
S(V
′,
V*
k
) will generate a prefix (r
1
,…,p
(k-1)
)
Based on this
prefix (r
1
,…,p
(k-1)
)
:
(By lemma 2 and canonical property)
If
V*
k
≡
V
i
k
,
an all-powerful prover will make a random verifier
in the subtree
T
i
(rooted at V
i
k
) accept with prob. 1
p
1
r
1
r
2
p
(k-2)
V′
r
k-1
p
k-1
V
m
V
1
k
V
i
k
V
i
k
V
t
k
T
i
(good)
T
j
(bad)
(By Babai-Moran)
There exists at least one
bad
subtree
T
j
(rooted at V
j
k
) such that an all-powerful
prover will make a random verifier in this tree
accept with prob. < 1-1/t
Thus, based on the prefix (r
1
,…,p
(k-1)
), we
can construct an algorithm U(r
1
,…,p
(k-1)
)
that finds the bad subtree
T
j
(i.e., find the
root V
i
k
≡
V*
k
) by exhaustive search
This completes the proof
□
19
We then prove that there is a tree sharing the same [V
1
,…,V
k-1
], but have
t different k-th steps, V
1
k
,…,V
t
k
, and a code V′
≡
[V
1
,…,V
k-1
]
such that for any code
V*
k
≡
V
i
k
On the Implausibility of Constant-Round
Public-Coin ZK Proofs
20
On the Implausibility of Constant-Round
Public-Coin ZK Proofs
Summary
Showed connection between existence of constant-
round public-coin ZK proofs and a seemingly
unrelated “program functionality distinguishing”
problem
•
Typical goal in reverse-engineering attempts with
static analysis
Thus, new evidence against existence of constant-
round public-coin ZK proofs, as it would imply
1.
A positive result in above distinguishing problem,
commonly believed to be notoriously hard, or
2.
A major paradigm shift in simulation strategies,
beyond the only known technique applicable to
argument systems
Thanks!
The paper discusses the implausibility of constant-round public-coin zero-knowledge proofs, exploring the limitations and complexities in achieving them. It delves into the fundamental problem of whether such proofs exist, the challenges in soundness error reduction, and the difficulties in parallel repetition. Additionally, it highlights the breakthrough by Barak in constructing a constant-round public-coin zero-knowledge argument. The content emphasizes the barriers, impossibility results, and non-black-box strategies in this area of cryptography research.
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
On the Implausibility of Constant-Round Public-Coin Zero-Knowledge Proofs Yi Deng IIE,Chinese Academy of Sciences (Beijing) Joint work with Juan Garay, San Ling, Huaxiong Wang and Moti Yung On the Implausibility of Constant-Round Public-Coin ZK Proofs 1
The problem: Do constant-round public-coin ZK proofs exist? Public-coin constructions are broadly applicable and versatile Deep connection to other fundamental problems, such as the Fiat-Shamir Heuristic On the Implausibility of Constant-Round Public-Coin ZK Proofs 2
Earlier public-coin protocols 3-round public-coin ZK proofs for NP [Blum 86,GMW86] Zero knowledge (By rewinding) Common input: x a P V e {0,1} Soundness Large soundness error: cheating prob. = 1/2 z What we want: Constant-round public-coin ZK proofs with negligible soundness error On the Implausibility of Constant-Round Public-Coin ZK Proofs 3
Parallel repetition doesnt help much x Reduces soundness error exponentially Preserves round complexity P V a e {0,1} z But: Not known to be zero knowledge parallelizing (BB simulator does not exist!) Pass et al. [PTW 10] Parallel repetion for public-coin protocol does not preserve BB ZK in general P V a1, a2, , an e1, e2, , en ei {0,1} z1,z2, ,zn On the Implausibility of Constant-Round Public-Coin ZK Proofs 4
Impossibility result for black-box simulation [GK96] w.r.t. both proof and argument Soundness only holds against PPT prover Surprisingly, Barak broke the above black-box barrier, constructing constant-round public-coin ZK argument for NP On the Implausibility of Constant-Round Public-Coin ZK Proofs 5
Baraks non-black-box ZK argument Barak s argument In the simulation, S computes Z=Com(h(V*),s) (using the code of V*) x L h V P Z = Com(h( ),s) r Prove (WIUA): x L OR there exists s.t. Z = Com(h( )) and (z) outputs r in time nlogn On the Implausibility of Constant-Round Public-Coin ZK Proofs 6
Striking properties of Baraks simulator x L h V* Straight-line i.e., no rewinding S(V*) Z = Com(h(V*),s) r Uses the code of V* without understanding it! Prove (WIUA): x L OR there exists s.t. Z = Com(h( )) and (z) outputs r in time nlogn On the Implausibility of Constant-Round Public-Coin ZK Proofs 7
Probably not Is it a proof system? Two facts Barak s protocol 1. There are too many pre-images for a single hash value x L 2. There infinitely many different codes 1, 2, that compute the same function (z) = r h V P* Z = Com(h(0n)) r Prove (WIUA): x L OR there exists s.t. Z = Com( ) and (z) outputs r in time nlogn P* may be able to find a code such that (z) = r and Z = Com(h(0n)) = Com(h( )) On the Implausibility of Constant-Round Public-Coin ZK Proofs 8
Would known NBB techniques help? Earlier negative evidence (for arbitrary reduction) [BLV03]: entropy-preserving hash functions exist No constant-round public-coin ZK proofs But such hash functions cannot be based on standard assumptions via BB reduction [BDGJKLW13] We give new negative evidence for universal simulation case. On the Implausibility of Constant-Round Public-Coin ZK Proofs 9
Universal simulators ZK property requires the mere existence of a simulator: For every V*, there exists a simulator S But we often prove ZK property by . Constructing a single universal simulator S for every V* Almost all simulators are universal: BB simulator Barak s NBB simulator On the Implausibility of Constant-Round Public-Coin ZK Proofs 10
Our main result We will deal with honest public-coin verifier (functionalities) Canonical ZK proof: It is sufficient to feed S with only partial code of V* in simulation Given a random tape r = [r1, r2, , rm], ri: randomness for step i, The honest verifier V(r)= [V1(r1), V2(r2), , Vm(rm)]: the step i function: Vi(hist, ri) = ri All known ZK protocols are canonical For a common type of constant-round public-coin proof system, if it has a universal simulator S But we consider Arbitrary code of the honest verifier functionality V* = [V*1, V*2, , V*m] each V*iis functionally equivalent (FE) to some Vi(ri): FE V*i(hist) Vi: V*i(hist)=Vi(hist, ri) = ri Then S can be used to distinguish some non-trivial functionality of the (possibly obfuscated) code of V* On the Implausibility of Constant-Round Public-Coin ZK Proofs 11
Our main result (3) For a common type constant-round public-coin proof system, if it has a universal simulator S This is in sharp contrast with all known public-coin protocols! Known straight-line S: it generates the prefix (r1, p1,, rk-1, pk-1) before executing V*k. There exist a code V [V1, V2, , Vk-1] a set of verifier step k (V1k, ,Vtk) a code V*k random one of (V1k, ,Vtk) Distinguish functionality of V*k. without executing V*k? r1 S(x,V , V*k) V1 ... This shows that constructing constant-round public-coin ZK proof (if exists) requires paradigm shifting simulation technique! p1 V rk-1 Vk-1 pk-1 ? V*k S must encode some functionality property of V*k in the session prefix before the verifier s k-th step! s.t. there is an alg U, U (r1, p1,, rk-1, pk-1)=j and V*k Vik On the Implausibility of Constant-Round Public-Coin ZK Proofs 12
Proof sketch (step 1): Lemma 1 (an improvement of Babai-Moran derandomization [BM88]) There exist p random tapes (r1,r2, rp) s.t. any false x ri1 Vi=V(ri) P*(r1,r2, rp) p1 P* knows the set of random tapes from which V will choose rim pm accept <1-1/p ri=[ri1, ri2, , rim] Let m be the round number and q the length of a prover msg Babai-Moran [BM88]: p=qm Improved: p=(q/log n)m On the Implausibility of Constant-Round Public-Coin ZK Proofs 13
Proof sketch (step 2): Lemma 2 There exists a false statement x and p random tapes (r1,r2, rp) of the verifier such that a false x a false x ri1 ri1 P*(r1,r2, rp) Vi=V(ri) S(V*) V* Vi=V(ri) p1 p1 & rim rim pm pm accept < 1-1/p accept w/ prob. 1 ri=[ri1, ri2, , rim] On the Implausibility of Constant-Round Public-Coin ZK Proofs 14
Proof sketch (last step): Now we group the p verifiers V1, Vp(Vi=V(ri)) as follows: If two verifiers Viand Vjshare the same first k-1 next-message- steps [V1, ,Vk-1] (i.e., they share the same randomness up to the (k-1)-st step), we put them in the same group V1 Each represents a next-msg-function (determined by the randomness used for this step) V2 VK-1 On the Implausibility of Constant-Round Public-Coin ZK Proofs 15
Proof sketch (last step): Now we group the p verifiers V1, Vp(Vi=V(ri)) as follows: If two verifiers Viand Vjshare the same first k-1 next-message- steps [V1, ,Vk-1] (i.e., they share the same randomness up to the (k-1)-st step), we put them in the same group V1 Each represents a next-msg-function (determined by the randomness used for this step) V2 VK-1 Each path represents a verifier A tree represents a group of verifiers Vm Vm+1 Vn On the Implausibility of Constant-Round Public-Coin ZK Proofs 16
Proof sketch (last step): We now have (a polynomial number of) trees V1 V2 VK-1 Vn Vp V1 V2 Vm-1Vm On the Implausibility of Constant-Round Public-Coin ZK Proofs 17
Proof sketch (last step): We then prove that there is a tree sharing the same [V1, ,Vk-1], but have t different k-th steps, V1k, ,Vtk, and a code V [V1, ,Vk-1] V1 V2 V VK-1 V1K V2K VtK Vn Vp V1 V2 Vi-1Vm On the Implausibility of Constant-Round Public-Coin ZK Proofs 18
Proof sketch (last step): We then prove that there is a tree sharing the same [V1, ,Vk-1], but have t different k-th steps, V1k, ,Vtk, and a code V [V1, ,Vk-1] such that for any code V*k Vik S(V ,V*k) will generate a prefix (r1, ,p (k-1)) Based on this prefix (r1, ,p (k-1)) : r1 p1 (By lemma 2 and canonical property) If V*k Vik, an all-powerful prover will make a random verifier in the subtree Ti(rooted at Vik) accept with prob. 1 r2 V S(V ,V*k) p(k-2) rk-1 pk-1 Vik (By Babai-Moran) There exists at least one bad subtree Tj (rooted at Vjk) such that an all-powerful prover will make a random verifier in this tree accept with prob. < 1-1/t V1k Vik Vtk Thus, based on the prefix (r1, ,p (k-1)), we can construct an algorithm U(r1, ,p (k-1)) that finds the bad subtree Tj(i.e., find the root Vik V*k) by exhaustive search Vm Vn This completes the proof Ti Tj (bad) On the Implausibility of Constant-Round Public-Coin ZK Proofs (good) 19
Summary Showed connection between existence of constant- round public-coin ZK proofs and a seemingly unrelated program functionality distinguishing problem Typical goal in reverse-engineering attempts with static analysis Thus, new evidence against existence of constant- round public-coin ZK proofs, as it would imply 1. A positive result in above distinguishing problem, commonly believed to be notoriously hard, or 2. A major paradigm shift in simulation strategies, beyond the only known technique applicable to argument systemsThanks! On the Implausibility of Constant-Round Public-Coin ZK Proofs 20
