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

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

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.