CHAPTER 10: Protocols to do seemingly impossible A protocol is an algorithm two (or more) parties have to follow to perform a communication/cooperation. A cryptographic protocol is a protocol to achieve secure communication during some goal oriented cooperation. In this chapter we deal with a variety of cryptographic protocols that allow to solve seemingly unsolvable problems. We present several cryptographic protocols for such basic cryptographic primitives as bit commitment and oblivious transfer. Of special importance are zero-knowledge protocols we discuss in second half of this chapter. COIN-FLIPPING BY PHONE PROTOCOLS-EXAMPLE Coin-flipping by telephone: Alice and Bob got divorced and they do not trust each other any longer. They want to decide, communicating by phone only, who gets the car. COIN TOSSING • In any coin tossing protocol both parties should influence outcome and should accept the outcome. Both outcomes should have the same probability. • Requirements for a good coin tossing protocol are sometimes generalized as follows: – The outcome of the protocol is an element from the set {0, 1, reject} – If both parties behave correctly, the outcome should be from the set {0, 1} – If it is not the case that both parties behave correctly, the outcome should be reject Problem: In some coin tossing protocols one party can find out the outcome sooner than second party and in such a case can disrupt the protocol to produce reject. A way out is to require that in case of correct behavior no outcome should have probability > 1/2. COIN TOSSING USING ONE-WAY FUNCTION f Protocol: _ Alice chooses a one-way function f and informs Bob about the definition domain of f. – Bob chooses randomly r[1] , r[2] from dom(f) and sends them to Alice – Alice sends to Bob one of the values f(r[1]) or f(r[2]) – Bob announces Alice his guess which of the two values he received – Alice announces Bob whether his guess was correct (0) or not (1) – If one needs to verify correctness, Alice should send to Bob specification of f The protocol is computationally secure. Indeed, to cheat, Alice should be able to find, for randomly chosen r[1], r[2] such a one-way function f that f(r[1]) = f(r[2]). BIT COMMITMENT PROTOCOLS (BCP) Basic ideas and solutions I In a bit commitment protocol Alice chooses a bit b and gets committed to b, in the following sense: Bob has no way of knowing which commitment Alice has made, and Alice has no way of changing her commitment once she has made it; say after Bob announces his guess as to what Alice has chosen. An example of a “pre-computer era'' bit commitment protocol is that Alice writes her commitment on a paper, locks it in a box, sends the box to Bob and, later, in the opening phase, she sends also the key to Bob. BIT COMMITMENT SCHEMES I The basis of bit commitment protocols are bit commitment schemes: A bit commitment scheme is a mapping f: {0,1} x X ® Y, where X and Y are finite sets. A commitment to a b Î {0,1}, or an encryption of b, is any value (called a blow) f(b, x), x Î X. Each bit commitment protocol has two phases: Commitment phase: The sender sends a bit b he wants to commit to, in an encrypted form, to the receiver. Opening phase: If required, the sender sends to the receiver additional information that enables the receiver to get b. . BIT COMMITMENT SCHEMES II Each bit commitment scheme should have three properties: Hiding (privacy): For no b Î {0,1} and no x Î X, it is feasible for Bob to determine b from B = f(b, x). Binding: Alice can “open'' her commitment b, by revealing (opening) x and b such that B = f(b, x), but she should not be able to open a commitment (blow) B as both 0 and 1. Correctness: If both, the sender and the receiver, follow the protocol, then the receiver will always learn (recover) the committed value b. Bit Commitment with One-Way Function Commitment phase: – Alice and Bob choose a oneway function f – Bob sends a randomly chosen r[1] to Alice – Alice chooses random r[2] and her committed bit b and sends to Bob f (r[1] , r[2] , b). Opening phase: – Alice sends to Bob r[2] and b – Bob computes f (r[1] , r[2] , b) and compares with the value he has already received. TWO SPECIAL BIT COMMITMENT SCHEMES Bit commitment scheme I. Let p, q be large primes, n = pq, m Î QNR(n), X = Y = Z[n]*. Let n,m be public. Commitment: f(b, x) = m ^bx ^2^ mod n for a random x from X. Since computation of quadratic residues is in general infeasible, this bit commitment scheme is hiding. Since m Î QNR(n), there are no x[1], x[2] such that mx[1]^2^ = x[2]^2 mod n and therefore the scheme is binding. MAKING COIN TOSSING FROM BIT COMMITMENT Each bit commitment scheme can be used to solve coin tossing problem as follows: 1. Alice tosses a coin, and commits itself to its outcome b[A] (say heads = 0, tails = 1) and sends the commitment to Bob. BASIC TYPES of HIDING and BINDING A commitment scheme based on discret logarithm Alice wants to commit herself to an m Î {0,…,q - 1}. Scheme setting: Bob randomly chooses primes p and q such that q | (p - 1). Bob chooses random generators of the subgroup G of order q Î Z[n]*. Bob sends p, q, g and v to Alice. Commitment phase: To commit to an m Î {0,…,q - 1}, Alice chooses a random r Î {0,…,q - 1}, and sends c= g ^rv ^m to Bob. Opening phase: Alice sends r and m to Bob who then verifies whether c = g ^rv ^m. COMMENTS • If Alice, committed to an m, could open her commitment as , then and therefore Hence, Alice could compute lg [g][ ]v of a randomly chosen element v ÎG, what contradicts the assumption that computation of discrete logarithms in G is infeasible. BIT COMMITMENT using ENCRYPTIONS Commit phase: • Bob generates a random string r and sends it to Alice • Alice commit herself to a bit b using a key k through an encryption E[k](rb) and sends it to Bob. Opening phase: • Alice sends the key k to Bob. • Bob decrypts the message to learn b and to verify r. Comment: without Bob’s random string r Alice could find a different key l such that e[k](b)=e[l](¬b). COMMITMENTS and ELECTRONIC VOTING Let com(r, m) = g ^rv ^m denote commitment to m in the commitment scheme based on discrete logarithm. If r [1], r [2], m [1], m [2] Î {0,…,q - 1}, then com(r [1], m [1]) × com(r [2], m [2]) = com(r [1] + r [2], m [1] + m [2]). Commitment schemes with such a property are called homomorphic commitment schemes. Homomorphic schemes can be use to cast yes-no votes of n voters V [1],…, V [n], by the trusted authority TA for whom e [T] and d [T] are ElGamal encryption and decryption algorithms. Each voter V [i] chooses his vote m [i] Î {0,1}, a random r [I][ ]Î {0,…, q - 1} and computes his voting commitment c [I][ ]= com(r [i], m [i]). Then V [i] makes c [i] public and sends e [T](g ^r[i]) to TA and TA computes where and makes public g ^r. Now, anybody can compute the result s of voting from publicly known c [i] and g ^r since with s can now be derived from v ^s by computing v ^1, v ^2, v ^3,… and comparing with v ^s if the number of voters is not too large. Trust in cryptographic protocols In any interaction between people, there is a certain level of risk, trust, and expected behaviour, that is implicit in the interchanges. People may behave properly for a variety of reasons: fear from prosecution, desire to act in unethical manner due to social influences, and so on. However, in cryptographic protocols trust has to be kept to the lowest possible level. In any cryptographic protocol, if there is an absence of a mechanism for verifying, say autencity, one must assume, as default, that other participants can be dishonest (if for no other reason than for self- preservation). OBLIVIOUS TRANSFER (OT) PROBLEM Story: Alice knows a secret and wants to send secret to Bob in such a way that he gets secret with probability 1/2, and he knows whether he got secret, but Alice has no idea whether he received secret. (Or Alice has several secrets and Bob wants to buy one of them but he does not want that Alice knows which one he bought.) 1-OUT-OF-2 oblivious transfer problem The 1-out-of-2 oblivious transfer problem: Alice sends two messages to Bob in such a way that Bob can choose which of the messages he receives (but he cannot choose both), but Alice cannot learn Bob’s decision. A generalization of 1-out-of-2 oblivious transfer problem is two-party oblivious circuit evaluation problem: Alice has a secret i and Bob has a secret j and they both know some function f. At the end of protocol the following conditions should hold: • Bob knows the value f(i,j), but he does not learn anything about i. • Alice learns nothing about j and nothing about f(i,j). Note: The 1-out-of-2 oblivious transfer problem is the instance of the oblivious circuit evaluation problem for i=(b[0],b[1]), f(i,j)=b[j]. 1-out-2 oblivious transfer box 1-out-of-two oblivious transfer can be imagine as a box with three inputs and one output. INPUTS: Alice inputs: x[0][ ] and x[1]; ………….Bob inputs a bit c OUTPUT: Bob gets as the output: x[c] Implementation of oblivious transfer • Alice generates two key pairs for a PKC P and sends their public keys to Bob. • Bob chooses a to-be random secret key k for a SKC S, encrypts it by one of Alice’s public keys and sends it to Alice. • Alice uses her two secret keys to decrypt the message she received. One of outcome is garbage g, another one is k, but she does not know which one. • Alice encrypts her two secret messages, one with k, another with g and sends them to Bob. • Bob uses S with k to decrypt both messages he got and one of the attempts is successful. Alice has no idea which one. Power of Oblivious Transfers • C. Crépeau (1988) showed that both versions of oblivious transfer are equivalent a protocol for each version can be realized using any protocol for the other version, using a cryptographic reduction • Original definition of the oblivious transfer is due to J. Halpern and M. O. Rabin (1983); 1-out-of-2 olivious transfer suggested S. Even, O. Goldreich and A. Lempel in 1985. • J. Kilian (1988) showed that oblivious transfers are very powerful protocols that allow secure computation of the value f(x, y) of any binary function f , where x is a secret value known only by Alice, and y is a secret value known only by Bob, in such a way that it holds: – Both, Alice and Bob, learn f(x, y) – Alice learns about y only so much she can learn from x and f(x, y) – Bob learns about x only so much he can learn from y and f(x, y) BIT COMMITMENT from 1-out-2 oblivious transfer Using 1-out-of-2 oblivious transfer box (OT-box) one can design bit commitment: COMMITMENT PHASE: 1.Alice selects a random bit r and her commitment bit b; 2. Alice inputs x[0] = r and x[1] =r xor b into the OT-box. 3. Alice sends a message to Bob telling him it is his turn. 4. Bob selects a random bit c, inputs c into the OT-box and records the output x[c]. OPENING PHASE: • Alice sends r and b to Bob. • Bob checks to see if x[c] =r xor bc Mental poker playing by phone - two players Basic requirements: • All hands (sets of 5 cards) are equally likely. • The hands of Alice and Bob are disjoint. • Both players know their own hand but not that of the opponent. • Each player can detect eventual cheating of the other player. A commutative cryptosystem is used with all functions kept secret. Players agree on numbers w [1],…,w [52] as the names of 52 cards. Mental poker with three players • Alice encrypts 52 cards w [1],…,w [52] with e [A] and sends them in a random order to Bob. Zero-knowledge proof protocols To the most important primitives for cryptographic protocols, and at the same time very counterintuitive primitives, belong so-called zero-knowledge proof protocols (of knowledge). Very informally, a zero-knowledge proof protocol allows one party, usually called PROVER, to convince another party, called VERIFIER, that PROVER knows some fact (a secret, a proof of a theorem,...) without revealing to the VERIFIER ANY information about his knowledge (secret, proof,...). In the rest of this chapter we present and illustrate very basic ideas of zero-knowledge proof protocols and their importance for cryptography. Zero-knowledge proof protocols are a special type of so-called interactive proof systems. By a theorem we understand in the following a claim that a specific object has a specific property. For example, that a specific graph is 3-collorable. Illustrative example (A cave with a door opening on a secret word) Alice knows a secret word opening the door in cave. How can she convince Bob about it without revealing this secret word? ZERO-KNOWLEDGE PROOFS Informally speaking, an interactive proof systems has the property of being zero-knowledge if the Verifier, that interacts with the honest Prover of the system, learns nothing from the interaction beyond the validity of the statement being proved. There are several variants of zero-knowledge protocols that differ in the specific way the notion of learning nothing is formalized. In each variant it is viewed that a particular Verifier learns nothing if there exists a polynomial time simulator whose output is indistinguishable from the output of the Verifier after interacting with the Prover on any possible instant of the problem. The different variants of zero-knowledge proof systems concern the strength of this distinguishability. In particular, perfect or statistical zero-knowledge refer to the situation where the simulator’s output and the Verifier’s output are indistinguishable in an information theoretic sense. Computational zero-knowledge refer to the case there is no polynomial time distinguishability. INTERACTIVE PROOF PROTOCOLS In an interactive proof system there are two parties • An (all powerful) Prover, often called Peggy (a randomized algorithm that uses a private random number generator); • A (little (polynomially) powerful) Verifier, often called Vic (a polynomial time randomized algorithm that uses a private random number generator). Prover knows some secret, or a knowledge, or a fact about a specific object, and wishes to convince Vic, through a communication with him, that he has the above knowledge. Example - GRAPH NON-ISOMORPHISM A simple interactive proof protocol exists for a computationally very hard graph non-isomorphism problem. Input: Two graphs G [1] and G [2], with the set of nodes {1,…,n } Protocol: Repeat n times the following steps: • Vic chooses randomly an integer i Î {1,2} and a permutation p of {1,…,n }. Vic then computes the image H of G [i] under permutation p and sends H to Peggy. • Peggy determines the value j such that G [J] is isomorphic to H, and sends j to Vic. • Vic checks to see if i = j. Vic accepts Peggy's proof if i = j in each of n rounds. INTERACTIVE PROOF SYSTEMS An interactive proof protocol is said to be an interactive proof system for a secret/knowledge or a decision problem P if the following properties are satisfied. Assume that Prover and Verifier posses an input x (or Prover has secret knowledge) and Prover wants to convince Verifier that x has a certain properties and that Prover knows how to proof that (or that Prover knows the secret). (Knowledge) Completeness: If x is a yes-instance of P, or Peggy knows the secret, then Vic always accepts Peggy's “proof'' for sure. (Knowledge) Soundness: If x is a no-instance of P, or Peggy does not know the secret, then Vic accepts Peggy's “proof'' only with very small probability. Zero-knowledge proof protocols informally Very informally An interactive “proof protocol’’ at which a Prover tries to convince a Verifier about the truth of a statement, or about possession of a knowledge, is called “zero-knowledge” protocol if the Verifier does not learn from communication anything more except that the statement is true or that Prover has knowledge (secret) she claims to have. AGE DIFFERENCE FINDING PROTOCOLS Alice and Bob wants to find out who is older without disclosing any other information about their age. The following protocol is based on a public-key cryptosystem, in which it is assumed that neither Bob nor Alice are older than 100 years. Protocol Age of Bob: j, age of Alice: i. • Bob choose a random x, computes k = e [A](x) and sends Alice s = k - j. 3-COLORABILITY of GRAPHS With the following protocol Peggy can convince Vic that a particular graph G, known to both of them, is 3-colorable and that Peggy knows such a coloring, without revealing to Vic any information how such coloring looks. 1 red e [1][ ]e [1](red) = y [1][] 2 green e [2 ]e [2](green) = y [2] 3 blue e [3 ]e [3](blue) = y [3] 4 red e [4 ]e [4](red) = y [4] 5 blue e [5 ]e [5](blue) = y [5] 6 green e [6 ]e [6](green) = y [6] (a) (b) Protocol: Peggy colors the graph G = (V, E ) with colors (red, blue, green) and she performs with Vic |E| ^2- times the following interactions, where v [1],…,v [n] are nodes of V. 1. Peggy choose a random permutation of colors, recolors G, and encrypts, for i = 1,2,…,n, the color c [i] of node v [i] by an encryption procedure e [i] - for each i different. Peggy then removes colors from nodes, labels the i-th node of G with cryptotext y [i ]= e [i](c [i]), and designs Table (b). Peggy finally shows Vic the graph with nodes labeled by cryptotexts. Zero-knowledge proofs and cryptographic protocols The fact that for a big class of statements there are zero-knowledge proofs can be used to design secure cryptographic protocols. (All languages in NP have zero-knowledge proofs.) A cryptographic protocol can be seen as a set of interactive programs to be executed by non-trusting parties. Each party keeps secret a local input. The protocol specifies the actions parties should take, depending on their local secrets and previous messages exchanged. The main problem in this setting is how can a party verify that the other parties have really followed the protocol? The way out: a party A can convince a party B that the transmitted message was completed according to the protocol without revealing its secrets . Zero-knowledge proof for quadratic residua Input: An integer n = pq, where p, q are primes and x Î QR(n). Protocol: Repeat lg n times the following steps: 1. Peggy chooses a random v Î Z [n]* and sends to Vic y = v ^2 mod n. 2. Vic sends to Peggy a random i Î {0,1}. 3. Peggy computes a square root u of x and sends to Vic z = u ^iv mod n. 4. Vic checks whether z ^2^ º x ^i y mod n. Vic accepts Peggy's proof that x is QR if he succeeds in point 4 in each of lg n rounds. Zero-knowledge proof for graph isomorphism Input: Two graphs G [1] and G [2] with the set of nodes {1,…,n }. Repeat the following steps n times: • Peggy chooses a random permutation p of {1,…,n } and computes H to be the image of G [1] under the permutation p, and sends H to Vic. Why is the last “proof” a “zero-knowledge proof”? Because Vic gets convinced, by the overwhelming statistical evidence, that graphs G [1] and G [2] are isomorphic, but he does not get any information (“knowledge”) that would help him to create isomorphism between G [1] and G [2]. In each round of the proof Vic see isomorphism between H (a random isomorphic copy of G [1]) and G [1] or G [2], (but not between both of them)! However, Vic can create such random copies H of the graphs by himself and therefore it seems very unlikely that this can help Vic to find an isomorphism between G [1] and G [2]. Information that Vic can receive during the protocol, called transcript, contains: • The graphs G [1] and G [2]. • All messages i transmitted during communications by Peggy and Vic. • Random numbers r used by Peggy and Vic to generate their outputs. Transcript has therefore the form T = ((G [1], G [2]); (H [1], i [1], r [1]),…,(H [n], i [n], r [n])). The essential point, which is the basis for the formal definition of zero-knowledge proof, is that Vic can forge transcript, without participating in the interactive proof, that look like “real transcripts”, if graphs are isomorphic, by means of the following forging algorithm called simulator. SIMULATOR A simulator for the previous graph isomorphism protocol. • T = (G [1], G [2]), • for j = 1 to n do CONSEQUENCES and FORMAL DEFINITION The fact that a simulator can forge transcripts has several important consequences. • Anything Vic can compute using the information obtained from the transcript can be computed using only a forged transcript and therefore participation in such a communication does not increase Vic capability to perform any computation. • Participation in such a proof does not allow Vic to prove isomorphism of G [1] and G [2]. • Vic cannot convince someone else that G [1] and G [2] are isomorphic by showing the transcript because it is indistinguishable from a forged one. Proof for graph isomorphism protocol Theorem The interactive proof system for Graph isomorphism is a perfect zero-knowledge proof if Vic follows protocol. Proof Let G [1] and G [2] be isomorphic. A transcript (real or forged) contains triplets (H[J], i[J], r[J]). The set R of such triplets contains 2n! elements (because each pair i, r uniquely determines H and there are n! permutation r. In each round of the simulator each triplet occurs with the same probability, that is all triplets have probability Let us now try to determine probability that a triplet (H, i, r) occurs at a j-th round of the interactive proof. i is clearly chosen with the same probability. Concerning r this is either randomly chosen permutation p or a composition p with a fixed permutation. Hence all triplets (H, i, r) have the same probability The next question is whether the above graph isomorphism protocol is zero-knowledge also if Vic does not follow fully the protocol. The case Vic does not follow protocol It is usually much more difficult to show that an interactive proof system is zero-knowledge even if Vic does not follow the protocol. In the case of graph isomorphism protocol the only way Vic can deviate from the protocol is that i he does not choose in a completely random way. The way around this difficulty is to prove that, no matter how a “cheating” Vic deviates from the protocol, there exists a polynomial-time simulator that will produce forged transcripts that “look like” the transcript T of the communication produced by Peggy and (the cheating) Vic during the interactive proof. As before, the term “looks like'' is formalized by requiring that two probability distributions are the same. The case Vic does not follow protocol Denote by G(V*, x) the set of all possible transcripts that could be produced as a result of Peggy and V* carrying out the interactive proof with a yes-instance x of P. Suppose that for every such V* there exists an expected polynomial time probabilistic algorithm S* = S*(V*) (the simulator) which will produce a forged transcript. Denote by F(V*, x) the set of possible forged transcripts. For any transcript T Î G(V*, x), let p [G][,][V*](T) denote the probability that T is the transcript produced by V* taking part in the interactive proof. Similarly, for T Î F(x), let p [F,V* ](T) denote the probability that T is the (forged) transcript produced by S*. If G(V*, x) = F(V*, x) and for any T Î G(V*, x), p [F,V* ](T) = p [G][,][V*](T), then the interactive proof system is said to be a perfect zero-knowledge protocol. ADDITIONS • It can be proved that the graph isomorphism protocol is zero-knowledge even in the case Vic cheats.