Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols
0 likes496 views
Presentation for CC5301 - Fundamentos de Criptograf鱈a exam. Based on the same name paper. DCC. Universidad de Chile. 2011.
Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols
- 1. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems Proof of Partial Knowledge and Simpli鍖ed Design of Witness Hiding Protocols Mauricio Quezada Mi辿rcoles 7 de Septiembre, 2011 Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 2. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems Outline 1 Proofs of Knowledge 2 Secret Sharing schemes 3 Main Result 4 Extensions, applications, open problems Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 3. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems Requirements A Proof of Knowledge with a few special properties An Access Structure for n participants Secret Sharing with the dual of the previous access structure Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 4. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems Proofs of Knowledge Let a binary relation R = {(x, w)} The witness set w(x) is the set of w such that (x, w ) R Let P a Proof of Knowledge protocol, in which there is a common input x (of length k bits) to a prover P and a veri鍖er V , and a private input w to P . The prover tries to convince the veri鍖er that w w(x). Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 5. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems Some restrictions Assume that P is a three round public coin protocol Conversations will be ordererd triples of the form m1 , c, m2 Where c is called the challenge, uniformly random bits chosen by the veri鍖er Also, assume that completeness holds with probability 1 I.e., if indeed w w(x), then the veri鍖er always accepts Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 6. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems Some restrictions P has the special soundness property: 1 The length of c is such that the number of possible values of c is super-polynomial in k 2 For any prover P , given two conversations between P and V , (m1 , c, m2 ) and (m1 , c , m2 ), where c = c , an element of w(x) can be computed in polynomial time. Also, is Honest Veri鍖er Zero Knowledge Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 7. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems Witness Indistinguishability and Witness Hiding A protocol is witness indistinguishable (WI) if conversations generated with same x, but di鍖erent elements from w(x) have indistinguishable distributions Even a cheating veri鍖er cant tell which witness the prover is using A protocol is witness hiding (WH), if it does not help even a cheating veri鍖er to compute a witness for x with non-negligible probability when x is generated under a certain distribution Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 8. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems WI, WH and PoK. Proposition 1 Let P a three round public coin proof of knowledge for a relation R. If P is honest veri鍖er zero-knowledge proof, then P is witness indistinguishable Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 9. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems Secret Sharing A Secret Sharing scheme is a method by which a secret s can be distributed among n participants by giving a share to each one. The subsets of participants which can reconstruct s are called quali鍖ed sets The collection of quali鍖ed sets is called the access structure for the scheme Monotone access structure property: If A is a quali鍖ed set, then any set containing A is also quali鍖ed Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 10. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems Access structures De鍖nition (Dual structures) Let be an access structure containing subsets of a set M . If A M , A denotes the complement of A in M . Now the dual access structure, is de鍖ned as follows: A i鍖 A / Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 11. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems Access structures The dual of a monotone access structure is monotone, and satis鍖es ( ) = Let be monotone. A is quali鍖ed in exactly when it has a non-empty intersection with every quali鍖ed set in Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 12. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems Notations Let D(s) denote the joint probability distribution of all shares resulting from distributing the secret s. For a set of A participants, DA (s) denotes the restriction of D to shares in A. As a secret sharing scheme S(k) is perfect, DA (s) is independent from s for any non-quali鍖ed set A Will be denoted DA whenever A is non-quali鍖ed Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 13. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems Requirements 1 All shares in S(k) have length polynomial in k 2 Distribution, reconstruction of a secret can be done in polynomial time 3 Veri鍖cation can be done in polynomial time in k 4 A set of non-quali鍖ed shares can be completed to a full set of shares according to D(s) and consistent to s (guess in how much time) 5 For any non-quali鍖ed set A, the probability distribution DA is such that shares in A are independent and uniformly chosen Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 14. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems Perfect Secret Sharing A perfect secret sharing scheme satisfying 1 to 4 is called semi-smooth. If 5 is also satis鍖ed, then is called smooth. Which protocol would be a good example? Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 15. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems Notations Let R be a binary relation Let = {(k)} a family of access structures on n(k) participants Let R be a relation de鍖ned as follows: ((x1 , . . . , xm ), (w1 , . . . , wm )) R i鍖 all xi are of the same length and the set of indices i for which (xi , wi ) R corresponds to a quali鍖ed set in (k) In a PoK for R , the prover proves to know witnesses to a set corresponding to a quali鍖ed set in (k). Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 16. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems Main Result Let P be a three round public coin honest veri鍖er zero-knowledge proof of knowledge for a relation R with special soundness property. Let = {(k)} be a family of monotone access structures and let {S(k)} be a family of smooth secret sharing schemes Such that the access structure of S(k) is (k) Then exists a three round public coin witness indistinguishable proof of knowledge for relation R Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 17. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems Proof A basic approach in the following is to interpret a challenge as a share (remember that the challenge is the message sent by the veri鍖er) If c is a challenge, share(c) will denote the corresponding share. A denotes the set of indices for which P knows a witness for xi The protocol is as follows: Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 18. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems The protocol (1/4) For each i A, P runs simulator S on input xi to produce conversations (mi , ci , mi ). 1 2 For each i A, P determines mi as what the prover in 1 P would send as m1 given a witness for input xi . P then sends the values mi , i = 1, . . . , n to V 1 Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 19. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems The protocol (2/4) V chooses a t-bit string s at random and sends it to P Note: t is the length of shares in S(k) Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 20. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems The protocol (3/4) Consider the set of shares {share(ci ) | i A} that correspond to the ci As A is not quali鍖ed in , P can complete these shares to a full set of shares (req. 4) For A, P now forms challenges ci for indices i A, such that share(ci ) corresponds to the share produced in the completion process. In step 1, S has produced a 鍖nal message, mi in P for 2 iA For i A, P knows a witness for xi , then can 鍖nd a valid mi for mi and ci by running the prover from P 2 1 Finally, P sends the set of messages ci , mi , i = 1, . . . , n 2 to V Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 21. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems The protocol (4/4) V checks that all conversations (mi , ci , mi ) now 1 2 produced would lead to acceptance by the veri鍖er of P, and shares share(ci ) are consistent with secret s. It accepts i鍖 these checks are satis鍖ed Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 22. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems Properties Completeness: trivial Soundness: Assume that some prover P for a given 鍖rst message {mi | i = 1, . . . , n} can answer correctly a 1 non-negligible fraction of possible choices of s As there are 2t possible values of s, any polynomial fraction contains at least 2 values of s. Call them s, s For any quali鍖ed set B in , there must be an i B, such that share(ci ) = share(ci ) Then we could compute a witness for xi (by special soundness property) So P knows a witness in every quali鍖ed set of Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 23. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems Properties Witness Indistinguishability: The distribution of the conversation is independent of which quali鍖ed set A the prover uses. The distribution of each mi depends only on xi , and is 1 the same of the prover of P (using that P is HVZK) Hence the veri鍖ers choice of s is independent of A As {share(ci )} is constructed by completing a set of shares in a non-quali鍖ed set, the joint distribution is simply D(s). Then the joint distribution of the ci s is independent of A Finally, the 鍖rst proposition implies that the distribution of mi depends only on xi , mi and ci and therefore 2 1 independent of A. Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 24. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems Extensions Three-round protocol can be generalized Another types of PoK, like special honest veri鍖er zero-knowledge with a SS semi-smooth protocol Using invulnerable generators for a relation R lead to designing protocols satisfying WI Then, using this technique we could turn a PoK protocol into a WI protocol Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 25. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems Applications (the typical example) Suppose we have n executives of a company, with public and private key (xi , wi ) Certain groups of them can do speci鍖c actions: taking decisions on behalf of the company, etc. We want to make them doing that actions as a quali鍖ed group, not revealing anything else about their identities This makes good sense, if they are to assume responsability on behalf of the company, rather than personally Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 26. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 27. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 28. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems Open problems The main theorem holds for ordinary soundness property in P? Can be generalized to other types of protocols than public coin protocols? Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne
- 29. Introduction Proofs of Knowledge Secret Sharing Main Result Extensions, applications, open problems References 1 Proofs of Partial Knowledge and Simpli鍖ed Design of Witness Hiding Protocols. Ronald Cramer, Ivan Damgardm Berry Schoenmakers. CRYPTO 94. Mauricio Quezada Proof of Partial Knowledge and Simpli鍖ed Design of Witne