Transcript Slide 1

Isolated PoK and Isolated ZK
Ivan Damgård, Jesper Buus Nielsen
and Daniel Wichs
Proofs of Knowledge (Review)
Language L in NP. Instance x. Witness w.
Prover
(x,w)
Verifier
x
Accept/Rejec
t
Completeness: Prover, Verifier honest ) Verifier outputs “Accept” W.O.P
Zero Knowledge (Review)
Language L in NP. Instance x. Witness w.
Verifier did
Simulator
not learn
anything x
new.
Prover
(x,w)
Verifier
x
¼
Simulator ensures that verifier could have
produced entire conversation on its own.
Knowledge Soundnes (Review)
Language L in NP. Instance x. Witness w.
Proverthe prover.
Extractor recovers w from
Verifier
x
If “Accept”,
prover
knows w.
Extractor
Isolation?
• Standard definitions assume isolation.
• Prover can run a man-in-the-middle attack between a “helper” and the verifier.
• No non-trivial protocol can guarantee that the prover knows w.
• Similar setting considered by Universal Composability.
Helper
Environment
(x,w)
Prover
(?)
(x,w)
Verifier
(x)
What can be done without full isolation?
• Setup assumptions (CRS, KRK,…) can be used to get UC security.
• Partial Isolation: Assume prover is l-isolated during the proof.
• Necessary condition: C>l.
Environment
(x,w)
Verifier
(x)
Prover
l bits
C bits
Why Study Partial Isolation?

Often reasonable to assume that Prover has more
bandwidth with Verifier than with other parties.




Prover and Verifier are in same room with no fast Internet
connection to the outside.
Prover is a tamper-proof hardware token and does not
have a large antenna sticking out (motivated by [Katz07]).
Prover is a smart-card and Verifier can monitor powersupply to limit communication.
Interesting theoretical question. Rewinding is
possible, but not easy.
What can be done without full isolation?
• An l-Isolated PoK (l-IPoK) is a protocol where no l-isolated cheating
prover can succeed without knowing a witness.
• Goal: Construct an IPoK compiler. For any l, compile an l-IPoK.
• Concentrate on witness indistinguishable (WI) l-IPoK protocols.
Environment
(x,w)
Verifier
(x)
Prover
l bits
C bits
Definition: Knowledge Soundness of l-IPoK
• Stage 1: Prover and Environment communicate without restraint.
• Stage 2: Prover is l-isolated. Prover and Verifier run protocol.
• Stage 3: If verifier accepts, the extractor is given:
• The code and coins of the prover
• The transcript of the proof
• The transcript of communication with the environment (inc. stage 1).
Negligible probability of prover succeeding and extractor failing.
Environment
(x,w)
Prover
(?)
l bits
Verifier
(x)
Extractor
Presentation Road-Map

Background, Motivation, Definition

A simple construction of an l-IPoK protocol with a large
communication/round complexity.

Lower bound on # of rounds in Black Box extractable l-IPoK.

A construction of an l-IPoK protocol with optimal
communication complexity.

A non-black-box construction in the RO model with optimal
communication/round complexity.

Zero Knowledge when the Verifier is only partially Isolated
Review: §-Protocols

Assume L 2 NP and § is a §-protocol for L.
Prover (x, w)
Verifier (x)
a
c
z

Special Knowledge Soundness


Can recover w from any two accepting conversations
(a,c,z) and (a,c’,z’) with c  c’.
Honest Verifier Zero Knowledge

Implies Witness Indistinguishability.
Compiling an l-IPoK from a
§-Protocol


Theorem: Repeating § with 1 bit challenges (l+·) times sequentially
results in an l-IPoK.
Intuition: The prover cannot communicate even 1 bit on at least · rounds
and hence must know the witness!
Prover (x, w)
a1
c1
z1
a2
c2
z2
…..
an
cn
zn
Verifier (x)
Extractor Description

The extractor rewinds to each round i and tries the challenge (1-ci).


Extractor ignores attempted communication with the environment.
If the prover answers incorrectly (or does not answer), go to next round.



Prover “expected help” from the environment.
Prover would have answered incorrectly in the original execution on this challenge.
Otherwise use (ai,ci,zi) and (ai, (1-ci), z’i) to compute w.
Prover
Ignore!
a1
c1-c
1 1
z’
z11
a2
1-c2
z’2
Extractor
(a1, 1-c1, z’1) is rejecting
Soundness (Proof)




We consider computationally unbounded provers and environments. Hence we can
consider deterministic provers and envrionments only.
An execution of the protocol is fully determined by the verifier challenges c1, c2,
c3,…,cn.
An execution is as a random path in a tree.
An execution path is winning if it is accepting AND the extractor fails to recover a
witness.
C1=0
C2=1
C3=0
Soundness (Proof)

On a winning path

All edges are correct.

All sibling edges are incorrect or
communicating

If two winning paths diverge at a node N.
Then both edges are correct and
communicating.

There can be at most l such nodes on any
path. Hence there are at most 2l winning
paths out of 2l+· total paths.

C1=0
C2=1
C3=0
• An edge is correct the prover
gives a correct response on that
challenge.
• An edge is communicating if
the environment communicates
) Probability of getting a winning execution is
with the prover on that challenge.
1/2·
Parameters
O(l + ·)
Round Complexity
O((l + ·)|§|)
Communication Complexity C
O(|§|)
Overhead = C/l. Assume l is large.
Presentation Road-Map

Background, Motivation, Definition

A simple construction of an l-IPoK protocol with a large
communication/round complexity.

Lower bound on # of rounds in Black Box extractable l-IPoK.

A construction of an l-IPoK protocol with optimal
communication complexity.

A non-black-box construction in the RO model with optimal
communication/round complexity.

Zero Knowledge when the Verifier is only partially Isolated
Round Complexity of BB
extractable l-IPoK




Prover and
environment share a
key k2 to a PRF.
The prover follows
the protocol honestly.
“Checks in” with the
Environment before
producing any
output.
Rewinding requires
finding a collission on
fk1 or guessing fk2 at a
new input!
Environment
(k2)
Prover
(x,w,k1,k2)
Verifier
(x)
¾ = fk1(view)
! = fk2(¾)
Update view
¾ = fk1(view)
! = fk2(¾)
! = fk2(¾)
! = fk2(¾)
Update view
¾ = fk1(view)
Update view
¾ = fk1(view)
If there are ½ rounds of communication then
l/½ = O(log(·))
) The number of rounds grows linearly with l.
Presentation Road-Map

Background, Motivation, Definition

A simple construction of an l-IPoK protocol with a large
communication/round complexity.

Number of rounds in BB extractable l-IPoK is linear in l.

A construction of an l-IPoK protocol with optimal
communication complexity.

A non-black-box construction in the RO model with optimal
communication/round complexity.

Zero Knowledge when the Verifier is only partially Isolated
Reducing the Communication

Task: Design an l-IPoK where the communication complexity
and round complexity are both O(l). In other words, we need
lots of short rounds.

If we start with a § protocol, then the flows (a,0,z0) and (a,1,z1)
determine w. The values z0 ,z1 can be thought of as a secret
sharing of w. Easy to verify that a share is indeed a share of
the witness.

Idea: Use a ramp secret sharing scheme to split z0, z1 into very
short shares. On each round give out ones short share.
Extractor collects enough shares to recover.
Efficient Protocol
Prover (x,w)
If Verifier asks for
a à enough
(random first
message of §)
blue/yellow
z0, z1 Ãshares
responses
to c=0,1
to break
0 0
0
0
(s [0],...,s
[N])Ã
SS(zquits.
;r )
secrecy,
Prover
1
Happens
w/ negligible
(s1[0],...,s
[N])Ã
SS(z1;r1)
0||r0when
probability
C0 Ã commit(z
)
1
1
verifier
is
honest.
C1 Ã commit(z ||r )
This is a single epoch
with N =O(l/·) rounds.
Protocol consists of
M=O(·) epochs.
Verifier
Choose(x)
? So that
expected number of
received blue/yellow
shares is less than
(secrecy_threshold)/2.
a, C0,C1
e 2{0,1,?}
Se/[i]/?
/?
}
b 2 {0,1}
/
decommit(C
b)
Repeat
i=1,…,N
Verify: (a,b,zb)
is accepting for §
Collected shares Sb[i]
match the
decommitment.
Proof Intuition
N =O(l/·) rounds.
Prover (x,w)
M=O(·) epochs.
Verifier (x)
a à (random first message of §)
z0, z1 Ã responses to c=0,1
0
(s0[0],...,s0[N])Ã SS(z ;r0)
1
(s1[0],...,s [N])Ã SS(z1;r1)
C0 Ã commit(z0,r0)
C1 Ã commit(z1, r1)
• Extractor rewinds to each
round in each epoch and tries
the other challenge.
a, C0,C1
e 2{0,1,?}
/ /?
}
Repeat
i=1,…,N
• If Prover communicates,
that share is lost.
• Share might also be
incorrect.
• Thrm: On at least one
epoch, extractor can recover
other correct response and
hence w.
b 2 {0,1}
/
Verify: (a,b,zb)
is accepting for §
Verify all shares Sb[i]
Received match the
decommitment
Parameters
Assume l = (·|§|)
O(l)
Round Complexity
O(l)
Communication Complexity C
O(1)
Overhead = C/l.
Presentation Road-Map

Background, Motivation, Definition

A simple construction of an l-IPoK protocol with a large
communication/round complexity.

Number of rounds in BB extractable l-IPoK is linear in l.

A construction of an l-IPoK protocol with optimal
communication complexity.

A non-black-box construction in the RO model with optimal
communication/round complexity.

Zero Knowledge when the Verifier is only partially Isolated
Random Oracle Protocol
Random Oracle
H: {0,1}* ! {0,1}·
Prover wins if he
queries oracle only on
the challenge chosen
by the verifier. The
probability of this is
1/2·a.
Protocol is WI (not ZK)
Prover (x,w)
Verifier (x)
rà random string of length l + ·
For i=1,…,·:
aià (first message of §)
zi0, zi1 responses
¾i0 = H(zi0, r, ri0)
¾i1 = H(zi1, r, ri1)
{ai, ¾i0, ¾i1 }i=1,…,·
c1, c2, …, c·
{ri(ci), zi(ci) }i=1,…,·
ci à {0,1}
Presentation Road-Map

Background, Motivation, Definition

A simple construction of an l-IPoK protocol with a large
communication/round complexity.

Number of rounds in BB extractable l-IPoK is linear in l.

A construction of an l-IPoK protocol with optimal
communication complexity.

A non-black-box construction in the RO model with optimal
communication/round complexity.

Zero Knowledge when the Verifier is only partially Isolated
l-Isolated Zero Knowledge (l-IZK)
• Stage
1: Environment and Verifier/Simulator communicate arbitrarily.
• Stage 2: Verifier is l-isolated. Prover and Verifier run proof.
• Stage 3: Environment and Verifier/Simulator communicate arbitrarily.
• Environment cannot distinguish left from right.
Prover
(x,w)
?
Verifier
(x)
Simulator
x
Environment
(x,w)
l bits
l bits
IZK + IPoK from WI IPoK


Use FLS paradigm to go from WI to IZK
Use your favorite WI IPoK, Perfectly Binding Commitments
Prover (x,w)
Verifier (x)
C0,C1
C0 Ã commit(m0;r0)
C1 Ã commit(m1;r1)
WI IPoK for one of
(m0||r0) or (m1||r1)
WI IPoK for one of
(m0||r0) or (m1||r1)
or w
Applications of IPoK and IZK

Can prevent man-in-the-middle attacks on
identification schemes when the prover is partially
isolated (use a WI IPoK).

UC secure MPC under a “cave” assumption. We can
implement ideal ZK PoK in such a cave and so can
do arbitrary UC-MPC using [CLOS02].

Would like to do UC-MPC when only one party is
partially isolated at a given time. This is needed for
tamper-proof hardware. can be accomplished using
a WI-IPoK (see ePrint 2007/332).
Open Questions

Open Questions:


A BB protocol with overhead 1 + o(1).
A non-standard, non-black-box assumption to
replace RO model in RO protocol
Thank You!
QUESTIONS?