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) Signature Schemes One-way functions UOWHFs String Commitment Zero-Knowledge for all of NP Trapdoor permutations Pseudo-random generators Pseudo-random Permutations P NP Public-key Encryption (CPA) Pseudo-random Functions Shared-key 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 XL the distributions on transcripts that V* ’ induces and that S produces are computationally indistinguishable. 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* * V S – 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) Protocol: – 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 Zero-knowledge: • 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 knowledge The extractor: • Run P* for the first step • Given the commitments, following step 1 run the protocol twice – 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. www.wisdom.weizmann.ac.il/~naor/PAPERS/SUDOKU_DEMO/ • 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 value” 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 ℓ Parallel? – If adversary controls V* for ℓ identification sessions • Can act as it wishes Concurrent? Sequential? – 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 function • 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 N • 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 and – 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 b0,1 from V* If b’=b proceed as planned: send v Otherwise rewind V* and start from scratch Also proof of knowledge 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 Identical 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 assumption} 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 completeness. Relationship between The Complexity classes EXP PSPACE=IP #P If NP µ Co-AM then the polynomial-time hierarchy collapses PH S2 P 2P Δ2P Under current world view: AM Co-AM No Co-NP-Complete can have an AM protocol MA Co-MA NP coNP BPP P A mechanism for showing non-hardness of problems • 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 Isomorphism • 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 PCP – 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 protocol 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 P:c3 • 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 you? • 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 Setting: • 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 Works even against schemes concurrent executions. will see encryption satisfying the desired requirements Deniability: does V retain a receipt?? – It does not retain one for an honest V – Need to prove knowledge of r

Descargar
# Foundations of Cryptography Lecture 2