Foundations of Cryptography
Lecture 13: Zero-Knowledge Variants and Applications
Lecturer: Moni Naor
Recap of last week’s lecture
• String Commitment
– Definition
– Construction from pseudo-random generators
• Coin Flipping
• Zero-knowledge Interactive Proofs
– Interactive Proofs and the cryptographic setting
– Definition of zero-knowledge proofs
– Construction of a zk proof system for Hamiltonicity
Question: zero-knowledge protocol for
subset sum
• Give a direct protocol (i.e. not through a reduction to
hamiltoncity) for the subset sum problem
• Subset sum problem: given
– n numbers 0 ≤ a1, a2 ,…, an < 2m
– Target sum T
– Is there a subset S⊆ {1,...,n} such that
∑ i S ai,=T mod 2m
The world so far
Factoring is hard
(BG Permutations)
for all of NP
P  NP
Encryption (CPA)
Encryption (CPA)
and Authentication
What’s next
More of zero-knowledge:
– Black-box simulation
– Proofs of knowledge
• Public-key Identification
– Perfect and Statistical Zero-knowledge
– Authentication via encryption
• Malleability
Zero Knowledge
• Each (cheating) verifier V* induces a distribution on
transcripts on interaction with P
• Zero-Knowledge Requirement: for all verifiers V*
there exists a simulator S such that:
– simulator S is a pptm (does not get witness W)
– for all XL the distributions on transcripts that V* ’
induces and that S produces are computationally
Role of simulator similar to alternative adversary A’ in
semantic security
Black-box Zero-Knowledge
• Order of quantifier: for for all verifiers V* there exists
a simulator S
• Black-box simulation: there exists a simulator S that
is good for all verifiers V*
– S interacts with V* as an oracle:
– Can see V*’s reaction to various messages but not its
internal state
Almost all known zero-knowledge protocols are black-box
Protocol Hamiltonicity
Common input graph G=(V,E)
L is the language of graphs with Hamiltonian cycles
Witness W – a Hamiltonian Cycle C=(i1,i2,  in)
– Prover P selects a random permutation  of the nodes
Commits to the adjacency matrix of (G)=((V), (E))
for each entry separately
Verifier V selects and sends a bit r R 0,1
Prover P
Verifier V accepts if: r=0 and committed graph isomorphic to G
r=1 and all opened slots are ’1’
If r=0 then P opens all the commitments and sends 
If r=1 then P opens only the commitments corresponding to C
• entries ( (ij),  (ij+1 ))
Reducing probability of cheating
To reduce the probability of cheating
• Run the protocol k times sequentially
• Verifier accepts if prover succeeds in all k runs
Probability of cheating: 2-k
• The simulator builds the transcript one iteration at a time
• The rewinding is to the end of the previous iteration
Knowledge of a Hamiltonian Cycle
Can a verifier succeed in the protocol without knowing a
witness W (a Hamiltonian cycle)?
– What does ‘know’ mean?
• In the NP context: you give the cycle, so the question does
not arise.
New notion: proof of knowledge
• There exists an extractor so that for any Prover P* that
succeeds in the protocol produces a cycle
– Extractor should be a ppt.
– Gets to interact with P* as a black-box and may rewind it
– Success of extraction should be similar to success of P*
Hamiltonicity protocol is a proof of
The extractor:
• Run P* for the first step
• Given the commitments, following step 1 run the protocol
– with r =0 and r =1
– If succeeds in both: can extract a cycle
– If at least one case fails – in a real execution prover fails with
probability at least ½
– If probability of extraction failing is , probability of success in
protocol is at most 1-/2
– If protocol is repeated k times: non-negligible probability of
success implies probability (1 – negligible) of extraction
Applications of proofs of knowledge
• A goal in itself: Sudoku example.
• Identification:
– I know a secret that only the claimed entity should know
– Allows for public-key identification
• Important as an internal component of protocols
– To be able to make sense out of intuitions “Player has a
Public-key identification
• Generation: G:{0,1}*  {0,1}* x {0,1}* mapping random
bits to public key Kp and secret key Ks
• Identification: prover and verifier both know Kp and prover
knows Ks
• Interactive protocol at the end verifier accept/rejects
• Completeness: a prover who knows Ks always makes the
verifier accepts
• Unforgeability: for any polynomial ℓ
– If adversary controls V* for ℓ identification sessions
• Can act as it wishes
– Tries to act as prover P* and make real verifier accept
Has negligible probability of succeeding
– Insecure against online transfers: mafia scam or man-in-the-middle
Public-key identification
• Public-key: Y=f(X) secret X 2 {0,1}k where f is a one-way
• To identify: run zero-knowledge proof of knowledge for inverse
of Y
– Prover knows X
• Since f is in P can reduce to Hamiltonicty
• Unforgeability: without any sessions as verifier:
– A forger will be caught whp
• Else can extract from it X, violating the hardness of f.
– If forger succeeds after ℓ sessions as verifier
• Run the simulator S for ℓ sessions and the run the extraction
– Receiver cannot prove that interaction took place
• Bug or feature?
Public-key identification
Can use witness indistinguishability instead of zero-knowledge
• Public-key: Y0=f(X0) and Y1=f(X1) where f is a one-way
function. Secret key: X0 or X1
• To identify: run a witness-indistinguishable proof of knowledge
for inverse of Y0 or Y1
– Prover knows X0 or X1
• Since f is in P can reduce to Hamiltonicty
• Unforgeability: given a forger A, can use it to invert f
– run it knowing one of the inverses.
– Then run the extractor on the forging session and extract an inverse to
Y0 or Y1.
– If known inverse more likely to be extracted: violated WI
– Ow successful inversion with probability 1/2
Protocol for quadratic residuosity
• Given y, N where N=P¢Q want to prove that y is a
quadratic residue:
there exist x such that x2 = y mod N
Zero-knowledge protocol for Prover who knows x
• Prover: choose random r 2R ZN* and send z=r2 mod
• Verifier: send b2R {0,1}
• Prover: send v = xbr mod N
• Verifier: check that v2 = yb z mod N
Analysis of Protocol
• Completeness: perfect √
• Soundness: if there exist v0 and v1 such that
– v02 = y0 z mod N
– v12 = y z mod N
then v1/v0 is square root of y.
– Probability of cheating is at most ½
• Zero-knowledge – simulator for V*:
guess b’ R 0,1 and select v 2R ZN*
Send z = v2/yb’
Obtain b0,1 from V*
If b’=b proceed as planned: send v
Otherwise rewind V* and start from scratch
Also proof of
Claim: for every V* (not necessarily ppt) Simulator stops in
expected constant number of trials
Proof: given z, distribution on b’ is unbiased
Half the cases b’ = b
Claim: Distributions of (S, V*) and (P, V*) are indistinguishable
Protocol is perfect zero-knowledge proof system
Statistical (prefect) zk: the distribution of the simulator is close to the actual distribution
 is negligible in the security parameter. In Perfect zk =0
Statistical Zero-Knowledge
So if statistical zero-knowledge is so good, why not use it
all the time?
Definition: L is a promise problem
SZK={L|L has a statistical zero-knowledge protocol}
HVSZK={L|L has an honest verifier statistical zeroknowledge protocol}
Clearly: SZK µ HVSZK
since any protocol good against all verifiers is good against honest
ones as well
Promise Problems
A promise problem L is similar to a language recognition problem except
that there is a set A
• if x 2 A then should report correctly whether x 2 L or not
• if x 2 A then do not care how algorithm responds
Example: unique sat
A={|either  is not statisfiable or  has a unique satisfying
O satisfying assignments
1 satisfying assignment
If A={0,1}n, then this is the usual language recognition problem
Public Coins: Arthur-Merlin Games
• Definition of IP permits the verifier to keep its coin-flips private
– necessary feature?
– The quadratic residue protocol we saw breaks without it
• New characters: Arthur as the verifier and Merlin as the prover
Public Coins
Arthur-Merlin Games
• Arthur-Merlin game: interactive protocol in which coin-flips are public
– Arthur (verifier) may as well just send the results of coin-flips. No point in doing
any computation until the final step
• If more complicated computation are need, Merlin (prover) can perform by himslef
any computation Arthur would have done
– Merlin does not know in advance the coin flips
• Complexity Class defined by limiting the # of rounds:
– AM[k] = Arthur-Merlin game with k rounds, Arthur goes first
– MA[k] = Arthur-Merlin game with k rounds, Merlin goes first
Theorem: AM[k] (MA[k]) equals AM[2] (MA[2]) with perfect
Relationship between
The Complexity classes
If NP µ Co-AM then the
polynomial-time hierarchy
S2 P
 2P
Under current world view:
No Co-NP-Complete can
have an AM protocol
A mechanism for showing non-hardness of
• By placing a problem in AM Å Co-AM one
demonstrates that the problem is not NP-Complete
according to the current world view
Example: Graph
• Alternatively, one can view it as a method for
showing impossibility of certain types of protocols
Statistical Zero-Knowledge
Theorem: if a language L has a statistical zero-knowledge
proof system, then L 2 AM Å Co-AM
Conclusion: if interested in zero-knowledge proofs for all
languages in NP need to either
– Relax notion of proof: argument
• Prover is assumed to be a polynomial time machine
This led to
– Having access to some secret information
• Such protocols exists assuming a certain kind of commitment exists
– Based on one-way permutations. Now functions!
• Another possible relaxation of proof: assume that there are two
provers who do not exchange information during the execution of the
Exercise: Commitment with two provers
• Suggest a commitment protocol for two provers
– They agree on a random string before the beginning of
the protocol
– Verifier/receiver talks to both of them
– They are assumed not to talk to each other during the
execution of the protocol
• How to enforce?
– Only one of them needs to know the string x to which
they are committing
– Define the properties of the protocol
Everlasting Security
Advantage of statistical/perfect proofs and arguments:
• The computational assumptions and limitation on
the adversary are made only for a fixed time period.
Bounded storage model
Significance of public coins protocol
• If there is a trusted source of randomness that broadcasts
after the initial commitments are made
– Beacon
– For instance: sub spots
Can have a “non-interactive” protocol
P: c1
V: c2 -random
• If there is a publicly available random function h
– Only access is via Standard Interface
Can turn identification protocol into a signature protocol
– Coins for challenge derived from message m to be signed and
first round message. Signature: (c1, c3) . c2 = h(c1,m)
– Fiat-Shamir signatures
Common heuristic
• Replace publicly available random function h with
some concrete and fixed function
• Proof of security goes away
• There are examples of schemes that are secure but
any instantiation of h makes them insecure
Interactive Authentication
P wants to convince V that he is approving message m
P has a public key KP of an encryption scheme E.
To authenticate a message m:
• V  P: Choose r 2R {0,1}n.
Send c=E(m ° r, KP)
• P  V : Receiving c
Decrypt c using KS
Verify that prefix of plaintext is m.
If yes - send r.
V is satisfied if he receives the same r he choose
Is it Safe?
• Definition of security: Existential unforgeability against adaptive chosen
message attack
– Adversary can ask to authenticate any sequence of messages m1, m2, …
– Has to succeed in making V accept a message m not authenticated
– Has complete control over the channels
• Intuition of security: if E does not leak information about plaintext
– Nothing is leaked about r
• Several problems: if E is “just” semantically secure against chosen
plaintext attacks:
– Adversary might change c=E(m ° r, KP) into c’=E(m’ ° r, KP)
• Malleability
– not sufficient to verify correct form of ciphertext in simulation
• Closer to a chosen ciphertext attack
No receipts
• Can the verifier convince third party that the prover
approved a certain message?
Authentication and Non-Repudiation
Key idea of modern cryptography [Diffie-Hellman]:
can make authentication (signatures) transferable to third
party - Non-repudiation.
– Essential to contract signing, e-commerce…
Digital Signatures: last 25 years major effort in
– Research
• Notions of security
• Computationally efficient constructions
– Technology, Infrastructure (PKI), Commerce, Legal
Is non-repudiation always desirable?
Not necessarily so:
• Privacy of conversation, no (verifiable) record.
– Do you want everything you ever said to be held against
• If Bob pays for the authentication, shouldn't be able to
transfer it for free
• Perhaps can gain efficiency
Alternative: (Plausible) Deniability
If the recipient (or any recipient) could have generated the
conversation himself
or an indistinguishable one
Deniable Authentication
• Sender has a public key known to receiver
• Want to an authentication scheme such that the receiver
keeps no receipt of conversation.
This means:
• Any receiver could have generated the conversation itself.
– There is a simulator that for any message m and verifier V*
generates an indistinguishable conversation.
– Exactly as in Zero-Knowledge!
– An example where zero-knowledge is the ends, not the means!
Proof of security consists of Unforgeability and Deniability
A Public Key Authentication Protocol
P has a public key PK of an encryption scheme E.
To authenticate a message m:
• V  P : Choose r R {0,1}n and random bits 2{0,1}*
Send Y=E(PK, m°r, )
• P  V : Verify that prefix of plaintext is indeed m.
If yes - send r.
V accepts iff the received r’=r
Is it Unforgeable?
Is it Deniable
Security of the scheme
Unforgeability: depends on the strength of E
• Sensitive to malleability:
– if given E(PK, m°r, ) can generate E(PK, m’°r’, ’) where m’ is
related to m and r’ is related to x then can forge.
• The protocol allows a chosen ciphertext attack on E.
– Even of the post-processing kind!
• Can prove that any strategy for existential forgery can be
translated into a CCA strategy on E
• We
against schemes
will see
the desired requirements
Deniability: does V retain a receipt??
– It does not retain one for an honest V
– Need to prove knowledge of r

Foundations of Cryptography Lecture 2