Practical examples Zero-knowledge proof
1 practical examples
1.1 discrete log of given value
1.2 hamiltonian cycle large graph
1.2.1 completeness
1.2.2 zero-knowledge
1.2.3 soundness
practical examples
discrete log of given value
we can extend these ideas more realistic cryptography application. peggy wants prove victor knows discrete log of given value in given group. example, given value
y
{\displaystyle y}
, large prime
p
{\displaystyle p}
, generator
g
{\displaystyle g}
, wants prove knows value
x
{\displaystyle x}
such
g
x
mod
p
=
y
{\displaystyle g^{x}{\bmod {p}}=y}
, without revealing
x
{\displaystyle x}
. indeed, revealing
x
{\displaystyle x}
used proof of identity, in peggy have such knowledge because chose random value
x
{\displaystyle x}
didn t reveal anyone, computed
y
=
g
x
mod
p
{\displaystyle y=g^{x}{\bmod {p}}}
, distributed value of
y
{\displaystyle y}
potential verifiers, such @ later time, proving knowledge of
x
{\displaystyle x}
equivalent proving identity peggy.
the protocol proceeds follows: in each round, peggy generates random number
r
{\displaystyle r}
, computes
c
=
g
r
mod
p
{\displaystyle c=g^{r}{\bmod {p}}}
, discloses victor. after receiving
c
{\displaystyle c}
, victor randomly issues 1 of following 2 requests: either requests peggy discloses value of
r
{\displaystyle r}
, or value of
(
x
+
r
)
mod
(
p
−
1
)
{\displaystyle (x+r){\bmod {(p-1)}}}
. either answer, peggy disclosing random value, no information disclosed correct execution of 1 round of protocol.
victor can verify either answer; if requested
r
{\displaystyle r}
, can compute
g
r
mod
p
{\displaystyle g^{r}{\bmod {p}}}
, verify matches
c
{\displaystyle c}
. if requested
(
x
+
r
)
mod
(
p
−
1
)
{\displaystyle (x+r){\bmod {(p-1)}}}
, can verify
c
{\displaystyle c}
consistent this, computing
g
(
x
+
r
)
mod
(
p
−
1
)
mod
p
{\displaystyle g^{(x+r){\bmod {(p-1)}}}{\bmod {p}}}
, verifying matches
c
⋅
y
mod
p
{\displaystyle c\cdot y{\bmod {p}}}
. if peggy indeed knows value of
x
{\displaystyle x}
, can respond either 1 of victor s possible challenges.
if peggy knew or guess challenge victor going issue, cheat , convince victor knows
x
{\displaystyle x}
when not: if knows victor going request
r
{\displaystyle r}
, proceeds normally: picks
r
{\displaystyle r}
, computes
c
=
g
r
mod
p
{\displaystyle c=g^{r}{\bmod {p}}}
, discloses
c
{\displaystyle c}
victor; able respond victor s challenge. on other hand, if knows victor request
(
x
+
r
)
mod
(
p
−
1
)
{\displaystyle (x+r){\bmod {(p-1)}}}
, picks random value
r
′
{\displaystyle r }
, computes
c
′
=
g
r
′
⋅
(
g
x
)
−
1
mod
p
{\displaystyle c =g^{r }\cdot \left(g^{x}\right)^{-1}{\bmod {p}}}
, , discloses
c
′
{\displaystyle c }
victor value of
c
{\displaystyle c}
expecting. when victor challenges reveal
(
x
+
r
)
mod
(
p
−
1
)
{\displaystyle (x+r){\bmod {(p-1)}}}
, reveals
r
′
{\displaystyle r }
, victor verify consistency, since in turn compute
g
r
′
mod
p
{\displaystyle g^{r }{\bmod {p}}}
, matches
c
′
⋅
y
{\displaystyle c \cdot y}
, since peggy multiplied inverse of
y
{\displaystyle y}
.
however, if in either 1 of above scenarios victor issues challenge other 1 expecting , manufactured result, unable respond challenge under assumption of infeasibility of solving discrete log group. if picked
r
{\displaystyle r}
, disclosed
c
=
g
r
mod
p
{\displaystyle c=g^{r}{\bmod {p}}}
, unable produce valid
(
x
+
r
)
mod
(
p
−
1
)
{\displaystyle (x+r){\bmod {(p-1)}}}
pass victor s verification, given not know
x
{\displaystyle x}
. , if picked value
r
′
{\displaystyle r }
poses
(
x
+
r
)
mod
(
p
−
1
)
{\displaystyle (x+r){\bmod {(p-1)}}}
, have respond discrete log of value disclosed – peggy not know discrete log, since value c disclosed obtained through arithmetic known values, , not computing power known exponent.
thus, cheating prover has 0.5 probability of cheating in 1 round. executing large enough number of rounds, probability of cheating prover succeeding can made arbitrarily low.
hamiltonian cycle large graph
the following scheme due manuel blum.
in scenario, peggy knows hamiltonian cycle large graph g. victor knows g not cycle (e.g., peggy has generated g , revealed him.) finding hamiltonian cycle given large graph believed computationally infeasible, since corresponding decision version known np-complete. peggy prove knows cycle without revealing (perhaps victor interested in buying wants verification first, or maybe peggy 1 knows information , proving identity victor).
to show peggy knows hamiltonian cycle, , victor play several rounds of game.
at beginning of each round, peggy creates h, graph isomorphic g (i.e. h g except vertices have different names). since trivial translate hamiltonian cycle between isomorphic graphs known isomorphism, if peggy knows hamiltonian cycle g must know 1 h.
peggy commits h. using cryptographic commitment scheme. alternatively, number vertices of h, each edge of h write small piece of paper containing 2 vertices of edge , put these pieces of paper upside down on table. purpose of commitment peggy not able change h while @ same time victor has no information h.
victor randomly chooses 1 of 2 questions ask peggy. can either ask show isomorphism between h , g (see graph isomorphism problem), or can ask show hamiltonian cycle in h.
if peggy asked show 2 graphs isomorphic, first uncovers of h (e.g. turning pieces of papers put on table) , provides vertex translations map g h. victor can verify indeed isomorphic.
if peggy asked prove knows hamiltonian cycle in h, translates hamiltonian cycle in g onto h , uncovers edges on hamiltonian cycle. enough victor check h indeed contain hamiltonian cycle.
completeness
if peggy know hamiltonian cycle in g, can satisfy victor s demand either graph isomorphism producing h g (which had committed in first step) or hamiltonian cycle in h (which can construct applying isomorphism cycle in g).
zero-knowledge
peggy s answers not reveal original hamiltonian cycle in g. each round, victor learn h s isomorphism g or hamiltonian cycle in h. need both answers single h discover cycle in g, information remains unknown long peggy can generate distinct h every round. if peggy not know of hamiltonian cycle in g, somehow knew in advance victor ask see each round cheat. example, if peggy knew ahead of time victor ask see hamiltonian cycle in h generate hamiltonian cycle unrelated graph. similarly, if peggy knew in advance victor ask see isomorphism generate isomorphic graph h (in not know hamiltonian cycle). victor simulate protocol himself (without peggy) because knows ask see. therefore, victor gains no information hamiltonian cycle in g information revealed in each round.
soundness
if peggy not know information, can guess question victor ask , generate either graph isomorphic g or hamiltonian cycle unrelated graph, since not know hamiltonian cycle g cannot both. guesswork, chance of fooling victor 2, n number of rounds. realistic purposes, infeasibly difficult defeat 0 knowledge proof reasonable number of rounds in way.
Comments
Post a Comment