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

Claim 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.

Claim 2

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.

Claim 9

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.

Claim 10

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.

Claim 31

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.

Claim 32

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.