密碼算法與協(xié)議3_密鑰的確認(rèn)

1、2022-2-31Chapter 3.Commitment Schemes2022-2-32IntroductionThe functionality of a commitment scheme is commonly introduced by means of the following analogy. Suppose you need to commit to a certain value, but you dont want to reveal it right away. For example, the committed value is a sealed bid in s

2、ome auction scheme. One way to do this is nto write the value on a piece of paper, nput it in a box, and lock the box with a padlock. nThe locked box is then given to the other party, but you keep the key. nAt a later time, you present the key to the other party who may then open the box, and check

3、its contents.2022-2-33Coin Flipping over the TelephoneAn immediate application of commitment schemes is known as “coin flipping over the telephone” or as “coin flipping into a well”. Two parties, say A and B, determine a mutually random bit as follows. nParty A commits to a random bit value bA R 0,

4、1 by sending a commitment on bA to party B. nParty B then replies by sending a bit value bB R 0, 1 to A. nFinally, party A opens the commitment and sends bA to B. nBoth parties take b = bAbB as the common random bit. If at least one of the parties is honest, the resulting bit b is distributed unifor

5、mly at random, assuming that A and B cannot cheat when revealing their bits.2022-2-34Application of CommitmentNote that party B sees the commitment of A before choosing its bit bB, so no information on bit bA should leak from the commitment on bA. Similarly, party A could try to influence the value

6、of the resulting bit b (after seeing the bit bB) by opening the commitment on bA as a commitment on 1-bA. Clearly, party A should not be able to “change its mind” in such a way! . , such as zero-knowledge proofs and secure multi-party computation.2022-2-35Commitment SchemeA commitment scheme consist

7、s of two protocols, called ncommit nand reveal , between two parties, usually called the and the . In many cases, the protocols commit and reveal can be defined in terms of a single algorithm, requiring no interaction between the sender and receiver at all. Such commitment schemes are non-interactiv

8、e.2022-2-36 ReceiverCommit PhaseReveal PhaseSenderReceiverXCommitment Protocol Receiver can verify X was the value in the boxSender is bound to XXSender2022-2-37Bit Commitment: Locking a Bit in a Secure Boxf: 0,1 X Y is bit commitment scheme if for a randomly chosen x from XnConcealing: for a bit b

9、0,1, Verifier() cannot determine the value b from f (b,x), the blobnBinding: Prover() can later open the blob by revealing the value of x. The Prover should not be able to open the blob as both 0 or 12022-2-38Following Commit PhaseReceiver should not have gained any information about XnInformation t

10、heoretic?nComputationally?Sender should be bound to XnNo two different and valid openings existnIt is computationally infeasible to find two different valid openings2022-2-39Bit Commitment by Encryption(Example 1)Let K = (n = pq, e, d) be an RSA keyTo commit a bit b, we could do the followingnChoose

11、 a random x such that wx is even if b = 0 wx is odd if b = 1wLet blob(b) = xe mod nTo open blob(b), njust review x, use the encryption to check!Concealing:b不參與其中運(yùn)算Binding: 不存在x1(odd),x2(even), x1e = x2emod n2022-2-310Bit Commitment by Encryption(Example 2)Let K = (n = pq, p, q primes, ) , (n,m) publ

12、ishedTo commit a bit b, we could do the followingnChoose a random x such that wY=f(b,x)=mbx2 mod nTo open blob(b), njust review b and x, use the encryption to verify: y=f(b,x)=mbx2 mod nnConcealing : 如果平方剩余問(wèn)題不可解，no information on b will be revealednBinding: if not, then exist x1,x2, commit(x1,1) = c

13、ommit(x2,0), mx12=x22 mod n, then m= (x2x1-1)2 (mod n), it is contradiction to the condition.)(nQRm2022-2-311DefinitionLet : 0, 1k 0, 1* 0, 1* be a , where k is a security parameter. A (noninteractive) consists of two protocols between a sender and a receiver: To commit to a value x 0, 1*, the sende

14、r computes C = commit(r, x), where r R 0, 1k, and sends C to the receiver.: To open commitment C = commit(r, x), the sender sends r and x to the receiver. The receiver computes commit(r, x) and verifies that it is equal to the previously received commitment.In the special case that the committed val

15、ue is a bit, that is, x 0, 1, one speaks of a bit commitment scheme. 2022-2-312Security RequirementsThe security requirements for a bit commitment scheme are the following.The commitment must be , i.e., nfor any adversary A, the probability of generating r, r 0, 1k satisfying commit(r, 0) = commit(r

16、, 1) should be negligible (as a function of k). Furthermore, the commitment must be , i.e., nthe distributions induced by commit(r, 0) and commit(r, 1) (with r R 0, 1k) are indistinguishable.2022-2-313Some distinctionsA commitment scheme is called nif the adversary A is restricted to be a p.p.t. alg

17、orithm. the scheme is called nif no such restriction is made (in other words, the adversary may be unlimited powerful). Similarly, the scheme is called nif the distributions induced by commit(r, 0) and commit(r, 1) are polynomially indistinguishable and the scheme is called nif these distributions a

18、re statistically indistinguishable.2022-2-314Security PropertiesThe security properties are easily extended to the case that x is an arbitrary string.Note that the above security requirements only cover attacks by either the sender or the receiver. For example, nsuppose party A acts as the sender an

19、d party B acts as the receiver, nand A sends a commitment C to B. nThen there is no guarantee that wB will notice if an attacker replaces C by a commitment C = commit(r, x) during the commit protocol, wand replaces r, x by r, x during the reveal protocol. nSuch attacks may be stopped by using an aut

20、henticated channel between A and B.2022-2-315Commitment Using a Hash FunctionGiven a cryptographic hash function H one obtains a bit commitment scheme simply by setting ncommit0(r, b) = H(r, b), where b 0, 1 and r R 0, 1k.The preimage resistance of H guarantees that the value of b remains hidden (as

21、 well as the value of r). The scheme is therefore hiding.Collision-resistance of H guarantees that the committer cannot prepare r, b and r, 1-b with H(r, b) = H(r, 1-b). Hence, the scheme is binding as well.More precisely, we conclude that the scheme is computationally binding and computationally hi

22、ding. nCan we do better?2022-2-316Bit Commitment - Suggestion1101001Commitment1Unveiling2022-2-317Bit Commitment - Suggestion21 10111010001001Commitment1 101110100Unveiling2022-2-318Bit Commitment - AssumptionsHash is one way and collision-freeAlice is computationally boundedHash doesnt “l(fā)eak” infor

23、mationnExample of a “l(fā)eaky” hash: 1 101110100100112022-2-319Commitment Using a Discrete Log SettingLet G = be a group of order n, where n is a large prime. Let h R G1 denote a random group element n(such that logg h is not known to any party).We define the following bit commitment scheme (known as “

24、Pedersens commitment scheme”):ncommit1(r, b) = grhb, where r R Zn. This scheme is computationally binding (under the DL assumption), which can be seen as follows. nSuppose it is computationally feasible to compute r, r Zn such that commit1(r, b) = commit1(r, 1 - b).nThat means that grhb = grh1-b, he

25、nce that logg h = (r-r)/(1-2b). Since r, r, and b are all known, this means that the discrete log of h with respect to g would be computed.2022-2-320Commitment Using a Discrete Log (cont.)On the other hand, the scheme is information-theoretically hiding, since the distribution of grhb is statistical

26、ly independent of the value of b.（相當(dāng)于gr和gr的分布是統(tǒng)計(jì)不可區(qū)分的） r=r概率為0，因?yàn)閔不為1，所以x不為0As a complementary bit commitment scheme, one may use the following ElGamal-like scheme:ncommit2(r, b) = (gr, hr+b), where r R Zn. This scheme is information-theoretically binding, since it is easily seen there cannot even e

27、xist r, r Zn such that commit2(r, b) = commit2(r, 1 - b), for b 0, 1.即不能既作為0又作為1來(lái)打開(kāi)承諾nnnngYgXgYgXgYgXYXrrrnrrrrrrnrrrrxrnrrr1)11101(21)Pr()Pr()Pr()Pr(21)Pr()Pr(21),(,2022-2-321Commitment Using a Discrete Log (cont.)On the other hand, this scheme is computationally hiding, since b can be computed as

28、follows. Assuming that the DL problem is feasible, one may compute b from a given commitment commit2(r, b) = (x, y), using the formula b = logh y - logg x. Note, however, that the DL assumption is not sufficient to guarantee that the scheme is hiding. We need to use the DDH assumption to ensure the

29、hiding property, as solving for b given commit2(r, b) is equivalent to solving the DDH problem.Both commitment schemes remain secure when used for b Zn instead of b 0, 1 Zn.2022-2-322ExampleExample: Analyze the security properties of commit1 and commit2 for the case that b Zn.Solution: The same reas

30、oning applies as before, except that for showing that commit1 is computationally binding we need a more general argument.nSuppose that it is feasible to find r, r, b, b with b b such that commit1(r, b) = commit1(r, b). nThis means that grhb = grhb , hence that logg h = (r r)/(b - b). nSince r, r, b,

31、 b are all known, this means that the discrete log of h with respect to g can be computed, contradicting the DL assumption.2022-2-323Example: What happens if the receiver knows logg h in scheme commit1? Same question for scheme commit2.: Since scheme commit1 is information-theoretically hiding, the

32、value of the committed value b is hidden even if the receiver knows logg h. For scheme commit2, the receiver is able to compute the value of hb = y/xloggh, where (x=gr,y=hr+b) = commit2(r, b). nIf b 0, 1, then hb 1, h and the value of b is easily determined. nIf b Zn and no additional information on

33、 b is known, then computing b from hb will be infeasible (under the DL assumption).2022-2-324Example: Discuss the security of the following commitment scheme for values m :ncommit(r,m) = grm, where r R Zn. nIs it binding? nIs it hiding?: The scheme is not useful as it is not binding. nLet m = mgr, t

34、hen commit(r,m) = grm = gr-rm = commit(r r,m). nSo, commitment commit(r,m) can be opened as a commitment to any message m with m = mgr. The scheme is information-theoretically hiding.nAgain: 相當(dāng)于gr和gr的分布是統(tǒng)計(jì)不可區(qū)分的2022-2-325Impossibility ResultA natural question is whether there exists a commitment sche

35、me which is both information-theoretically binding and information-theoretically hiding.The following informal argument shows that such a scheme cannot exist. Consider any bit commitment scheme which is information-theoretically binding. nFor such a scheme there cannot exist any r, r such that commi

36、t(r, 0) = commit(r, 1), because then the (unlimited powerful) sender would be able to compute both r and r, and open the commitment at its liking. nHowever, if the sender commits to 0, say, using C = commit(r, 0) for some r, the (unlimited powerful) receiver will notice that there does not exist any

37、 r with C = commit(r, 1), hence the receiver knows that the committed value must be 0.2022-2-326Homomorphic CommitmentsThe basic security requirement for a commitment scheme are that is must be binding and hiding. Another useful property of a commitment scheme is that it may be homomorphic. We will

38、introduce the homomorphic property by means of an example. Consider Pedersens commitment scheme, given by commit1(r, x) = grhx, where r R Zn and x Zn .This scheme is homomorphic in the sense that: ncommit1(r, x) commit1(r, x) = commit1(r + r, x + x), where the multiplication on the left-hand side is

39、 in the group G and the additions on the right-hand side are in Zn. nSo, the product of two commitments is a commitment to the sum of the committed values.Homomorphic properties turn out to be very useful for achieving secure multiparty computation.2022-2-327Homomorphic PropertyAs a concrete example

40、, homomorphic commitments can be used as a building block for secure election schemes: nvery roughly, during the voting stage, voters put their votes into homomorphic commitments, nand during the tallying stage, the votes are counted by taking the product of all commitments).2022-2-328ExampleLet m =

41、 pq. The Quadratic Residuosity (QR) assumption states that the QR problem is infeasible.: Let y Jm denote a non-quadratic residue modulo m (e.g., y = -1 is a non-quadratic residue modulo m when m is a Blum integer “p=q=3 mod 4”). Consider the following bit commitment scheme: ncommit(r, b) = ybr2 mod

42、 m, where r R Zm. In what sense is the scheme binding? In what sense is the scheme hiding? In what sense is the scheme homomorphic?2022-2-329Commitment using Quadratic Residuosity : Note that b = 0 if and only if commit(r, b) is a quadratic residue modulo m. Therefore, the scheme is information-theo

43、retically binding and computationally hiding(why? An important exercise). The homomorphic property for this scheme is given by commit(r, b) commit(r, b) = commit(rr, bb), hence the product of two commitments is a commitment to the XOR of the committed values. nComputationally hiding : 如果平方剩余問(wèn)題可解，那么如

44、果commnit(r,b)為平方剩余則b=0, 否則b=1. nInformation-theoretically binding: if there exists r1,r2, commit(r1,1) = commit(r2,0),then yr12=r22 mod n, then y= (r2r1-1)2 (mod n), it is contradiction to the condition.2022-2-330ApplicationsCoin FlippingAuctionsZero Knowledge2022-2-331Coin Flipping by TelephoneAlic

45、e and Bob want to make some decision based on a random coin - if the coin is “head” Alice gets the right and if the coin is “tail”, Bob gets the rightAlice is in BeijingBob is in Shanghai2022-2-332Using Commitment ProtocolAlice choose a random bit bAlice send to Bob her commitment blobBob guess the

46、value of the bitAlice open the BlobHead if Bob is wrong and tail if Bob is right2022-2-333 Coin Flipping Protocol A selects rA R 0,1; Commits to rA B sends bit rB R 0,1 Coin is rA rBIf A doesnt open - result is If As opening is invalid - result is 2022-2-334Interactive Proof SystemLet L 0,1* be a la

47、nguageOne party, the Prover P, want to convince the other party, Verifier V that X LIn our case: both parties are PPTM; nexchange messages and flip coinsProver P may have some extra information WAt the end of the protocol Verifier V state accept, rejectFor a given W the interaction between V and P i

48、nduces a distribution of the transcriptsProver PVerifier V 2022-2-335Witness Protection ProgramsA witness indistinguishable proof system for XL Prover p Verifier VCompleteness: if prover P has witness W - can construct effective proof that makes verifier V accept.Soundness: if XL no prover P* can su

49、cceed with high probability to make verifier V accept.Witness Indistinguishability: for every V* and any witnesses W1 and W2: distributions on transcripts are computationally indistinguishable.nNo polynomial time test can distinguish the two2022-2-336Example: HamiltonicityCommon input graph G=(V,E)L

50、 is the language of graphs with Hamiltonian cyclesG=(V,E) L if and only if there is a cycle C=(i1,i2, in) covering all nodes of V once and (ij,ij+1 ) E2022-2-337Example: HamiltonicityCommon input graph G=(V,E)L is the language of graphs with Hamiltonian cyclesWitness W a Hamiltonian Cycle C=(i1,i2,

51、in)Protocol:nProver P selects a random permutation of the nodes Commits to the adjacency matrix of (G)=(V), (E)wfor each entry separatelynVerifier V selects and sends a bit r R 0,1nIf r=0 P opens all the commitments and sends If r=1 P opens only the commitments corresponding to Cwentries ( (ij), (ij+1 )nVerifier V accepts if: r=0 and commit