System for reconstruction of a secret shared by a plurality of participants

• US 5,764,767 A
• Filed: 08/21/1996
• Issued: 06/09/1998
• Est. Priority Date: 08/21/1996
• Status: Expired due to Fees

• Current Assignee: TECHNION RESEARCH AND DEVELOPMENT FOUNDATION, LTD.
• Original Assignee: TECHNION RESEARCH AND DEVELOPMENT FOUNDATION, LTD.
• Inventors: Chor, Ben-Zion, Beimel, Amos
• Primary Examiner(s): Cain, David C.
• Application Number:
  US08/700,866
• Time in Patent Office: 657 Days
• Field of Search: 380/23, 380/21, 380/49, 380/30, 380/28
• US Class Current: 713/180
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes

Abstract

A method for reconstructing a secret, over a public communication channel, using a perfect t-out-of-n secret sharing scheme. The scheme having a dealer which utilizes a delivering procedure for privately delivering n secret shares of the secret along with n keys to n participants that are interlinked by the channel. The scheme further having a secret reconstructing procedure for being executed by selected recipient participants, for reconstructing the secret by utilizing self secret share of the recipient participant and l-1 secret shares of the other participants. The secret reconstructing procedure includes the following steps:

(i) receiving over said public communication channel l-1 encoded secret shares from the l-1 participants, respectively;

(ii) decoding each one of the l-1 encoded secret shares, thereby obtaining l-1 decoded secret shares; and

(iii) reconstructing the secret from the l-1 decoded secret shares and from the self secret share of the recipient participant.

Claims

1. A method for reconstructing a secret, over a public communication channel, using a perfect t-out-of-n secret sharing scheme;

the t-out-of-n secret sharing scheme having a dealer which utilizes a delivering procedure for privately delivering n secret shares of said secret along with n keys to respective n participants that are interlinked by said public communication channel;

the key that is delivered to each one of said n participants is composed of, or is serving for generating n-1 key constituents for respectively communicating, over said public communication channel, with the remaining n-1 participants from among said n participants;

said secret sharing scheme further having a secret reconstructing procedure for being executed by each one of at least one recipient participant selected from a group of l participants from among said n participants, for reconstructing said secret by utilizing self secret share of said recipient participant and l-1 secret shares of the remaining l-1 participants from among said l participants;

said secret reconstructing procedure, executed by each one of said recipient participants, comprising the following steps;

(i) receiving over said public communication channel l-1 encoded secret shares from the l-1 participants, respectively;

the l-1 encoded secret shares being generated, each, by one and different participant from among said l-1 participants, by applying an encoding function which utilizes a key constituent from among said n-1 key constituents that is adapted for communicating between said one participant and said recipient participant;

(ii) decoding each one of said l-1 encoded secret shares, thereby obtaining l-1 decoded secret shares;

the l-1 decoded secret share are obtained, each, by applying a decoding function that utilizes said key constituent, stipulated in step (i), that is adapted for communication between said one participant and said recipient participant; and

(iii) reconstructing said secret from the l-1 decoded secret shares and from the self secret share of the recipient participant.

2. A method according to claim 1 wherein said n participants are further interlinked by means of private communication channel and wherein said delivering procedure is executed over said private communication channel.

3. A method according to claim 2, wherein said delivering procedure employs a Shamir technique.

4. A method according to claim 2, wherein said delivering procedure employs a Blakely technique.

5. A method according to claim 1, wherein the size of the secret share equals the size of the secret.

6. A method according to claim 1, wherein said secret reconstructing procedure is executed by exactly one recipient participant selected from the group of said l participants, and wherein said secret reconstructing procedure executed by the recipient participant further comprising the step of:

(iv) transmitting over said public communication channel l-1 encoded messages to the l-1 participants, respectively;

the l-1 encoded messages being generated, each, by applying to said secret an encoding function which utilizes a key constituent from among said n-1 key constituents that is adapted for communication between one and different participant, from among said l-1 participants, and said recipient participant; and

for executing by each one of said l-1 participants;

(v) receiving over said public communication channel, an encoded message from among said l-1 encoded messages and decoding it so as to obtain a decoded secret;

the decoded secret is obtained by applying to the encoded message a decoding function that utilizes the key constituent stipulated in step (iv) that is adapted for communication between one and different participant and said recipient participant.

7. A method according to claim 1, wherein each one of said l participants constitutes said recipient participant.

12. A method according to claim 1, wherein l≧

t.

13. A method according to claim 6, wherein l≧

t.

14. A method according to claim 7, wherein l≧

t.

15. A method according to claim 7, wherein l>

t.

16. A method according to claim 7, wherein l=t.

17. A method according to claim 1, wherein both said encoding and decoding functions being a modular add function.

18. A method according to claim 6, wherein both said encoding and decoding functions being a modular add function.

19. A method according to claim 7, wherein both said encoding and decoding functions being a modular add function.

21. A method according to claim 1, wherein both said encoding and decoding functions being a logical xor function.

22. A method according to claim 6, wherein both said encoding and decoding functions being a logical xor function.

23. A method according to claim 7, wherein both said encoding and decoding functions being a logical xor function.

25. A method according to claim 1, wherein said key constituent being a one time pad.

26. A method according to claim 6, wherein said key constituent being a one time pad.

27. A method according to claim 7, wherein said key constituent being a one time pad.

8. A method for reconstructing a secret, over a public communication channel, using a perfect t-out-of-n secret sharing scheme;

the t-out-of-n secret sharing scheme having a dealer capable of partitioning said secret to t sub-secrets each of which being subjected to a delivering procedure for privately delivering n sub secret shares thereof to respective n participants that are interlinked by said public communication channel;

said dealer is further capable of privately delivering n keys to the respective n participants;

the key that is delivered to each one of said n participants is composed of, or is serving for generating, n-1 key constituents for respectively communicating, over said public communication channel, with the remaining n-1 participants from among said n participants;

said secret sharing scheme further having a secret reconstructing procedure for being executed by each one of l participants (l≧

t), constituting, respectively, l recipient participants, from among said n participants, for reconstructing said secret by utilizing a self secret share of said recipient participant and l-1 secret shares of the remaining l-1 participants from among said l participants;

said secret reconstructing procedure, executed by each one of t participants from among said l recipient participants, comprising the following steps;

(i) receiving over said public communication channel t-1 encoded sub secret shares from the remaining t-1 participants, from among said t participants;

the t-1 encoded sub secret shares being generated, each, by one and different participant from among said t-1 participants, by applying to said sub secret share an encoding function which utilizes a key constituent from among said n-1 key constituents that is adapted for communicating between said one participant and said recipient participant;

(ii) decoding each one of said t-1 encoded sub secret shares, thereby obtaining t-1 decoded sub secret shares;

the t-1 decoded sub secret shares are obtained, each, by applying thereto a decoding function that utilizes said key constituent, stipulated in step (i), that is adapted for communication between said one participant and said recipient participant;

(iii) reconstructing said sub secret from the t-1 decoded sub secret shares and from the sub secret share of the recipient participant;

said secret reconstructing procedure, further comprising the steps

(iv)-(vi), executed by each one of said I recipient participants;

(iv) receiving over said public communication channel t or t-1 encoded sub secrets from said t or t-1 participants, respectively;

the t or t-1 encoded sub secrets being generated, each, by one and different participant from among said t or t-1 participants, by applying to said sub secret an encoding function which utilizes a key constituent from among said n-1 key constituents that is adapted for communicating between said one participant and said recipient participant;

(v) decoding each one of said t or t-1 encoded sub secrets so as to obtain t or t-1 decoded sub secrets;

the t or t-1 decoded sub secrets are obtained, each, by applying thereto a decoding function that utilizes said key constituent, stipulated in step (iv), that is adapted for communication between said one participant and said recipient participant, thereby accomplishing t sub secrets; and

(vi) reconstructing said secret from the t sub secrets.

9. A method according to claim 8, wherein said key is serving for generating said n-1 key constituent and wherein said P=t.

10. A method according to claim 9, wherein said key is generated by utilizing a Bloom technique.

11. A method according to claim 8, wherein said secret reconstruction procedure comprising an initial step of dividing said n participants into disjoint subsets t, 2t, . . . 2ⁱ t and possibly additional subset of size t, partially overlapping one of said disjoint sets, such that each one of said n participants belongs to one, or two, of said subsets.

20. A method according to claim 8, wherein both said encoding and decoding functions being a modular add function.

24. A method according to claim 8, wherein both said encoding and decoding functions being a logical xor function.

28. A method according to claim 8, wherein said key constituent being a one time pad.

29. A system for reconstructing a secret, over a public communication channel, using a perfect t-out-of-n secret sharing scheme;

the t-out-of-n secret sharing scheme having a dealing means for privately dealing n secret shares of said secret along with n keys to respective n participants interlinked by said public communication channel;

for each participant, the key that is dealt thereto is composed of, or is associated with generating means for generating n-1 key constituents for respectively communicating, over said public communication channel, with the remaining n-1 participants from among said n participants;

said secret sharing scheme further having a secret reconstructing means associated with each of at least one recipient participant selected from a group of l participants from among said n participants, for reconstructing said secret by utilizing self secret share of said recipient participant and l-1 secret shares of the remaining l-1 participants from among said l participants;

said secret reconstructing means associated with each of said at least one recipient participant is capable of;

(i) receiving over said public communication channel l-1 encoded secret shares from the l-1 participants, respectively;

the l-1 encoded secret shares being generated, each, by one and different participant from among said l-1 participants, by applying an encoding function which utilizes a key constituent from among said n-1 key constituents that is adapted for communicating between said one participant and said recipient participant;

(ii) decoding each one of said l-1 encoded secret shares, thereby obtaining l-1 decoded secret shares;

the l-1 decoded secret share are obtained, each, by applying a decoding function that utilizes said key constituent, stipulated in step (i), that is adapted for communication between said one participant and said recipient participant; and

(iii) reconstructing said secret from the l-1 decoded secret shares and from the self secret share of the recipient participant.

30. The system according to claim 29 wherein said n participants are further interlinked by means of private communication channel and wherein said delivering procedure is executed over said private communication channel.

31. The system according to claim 30, wherein said delivering procedure employs a Shamir technique.

32. The system according to claim 30, wherein said delivering procedure employs a Blakely technique.

33. The system according to claim 29, wherein the size of the secret share equals the size of the secret.

34. The system according to claim 29, wherein said reconstruction means is associated with exactly one recipient participant selected from the group of said l participants, and wherein said reconstructing means is further capable of:

(iv) transmitting over said public communication channel l-1 encoded messages to the l-1 participants, respectively;

the l-1 encoded messages being generated, each, by applying to said secret an encoding function which utilizes a key constituent from among said n-1 key constituents that is adapted for communication between one and different participant, from among said l-1 participants, and said recipient participant; and

for executing by each one of said l-1 participants;

(v) receiving over said public communication channel, an encoded message from among said l-1 encoded messages and decoding it so as to obtain a decoded secret;

the decoded secret is obtained by applying to the encoded message a decoding function that utilizes the key constituent stipulated in step (iv) that is adapted for communication between one and different participant and said recipient participant.

35. The system according to claim 29, wherein each one of said l participants constitutes said recipient participant.

36. The system according to claim 29, wherein l≧

t.

37. The system according to claim 34, wherein l≧

t.

38. The system according to claim 29, wherein both said encoding and decoding functions being a modular add function.

39. The system according to claim 34, wherein both said encoding and decoding functions being a modular add function.

40. The system according to claim 29, wherein both said encoding and decoding functions being a logical xor function.

41. The system according to claim 34, wherein both said encoding and decoding functions being a logical xor function.

42. The system according to claim 29, wherein said key constituent being a one time pad.

43. The system according to claim 34, wherein said key constituent being a one time pad.