Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing

Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing

1992 | Torben Pryds Pedersen
This paper presents a non-interactive verifiable secret sharing (VSS) scheme that allows a dealer to distribute a secret to n participants such that any k of them can reconstruct the secret, while fewer than k participants gain no information about it. The scheme ensures that no (Shannon) information about the secret is revealed during the distribution and verification process. The information rate of the scheme is 1/2, and the distribution and verification require approximately 2k modular multiplications per bit of the secret. The scheme is based on combining Shamir's secret sharing scheme with a commitment scheme that is unconditionally secure for the committer. The commitment scheme allows the dealer to commit to a secret value without revealing it, and it enables the verification of shares without requiring interaction between participants. The scheme is efficient, with the commitment process requiring less than 2|q| multiplications modulo p or less than two multiplications per bit of the secret. The paper also shows how a group of participants can choose a secret "in the well" and distribute it verifiably among themselves. This is achieved by having each participant generate a random value, distribute it verifiably, and then combine the values to form the secret. The resulting secret is uniformly distributed and remains unknown to fewer than k participants. The scheme is compared to other non-interactive VSS schemes, such as those in [Fel87], and is shown to be dual in nature. While [Fel87] relies on computational assumptions, this scheme provides unconditional security for the dealer but depends on the assumption that the dealer cannot solve the discrete logarithm problem. The paper also demonstrates that linear combinations of shared secrets can be computed efficiently, and that the scheme can be generalized to allow l participants to select and distribute a secret democratically. The scheme is efficient, secure, and suitable for practical applications, particularly in scenarios where non-interactive verification is required. It is optimal in the sense that it is impossible to construct a non-interactive VSS scheme that reveals no information about the secret and is secure against an infinitely powerful dealer.This paper presents a non-interactive verifiable secret sharing (VSS) scheme that allows a dealer to distribute a secret to n participants such that any k of them can reconstruct the secret, while fewer than k participants gain no information about it. The scheme ensures that no (Shannon) information about the secret is revealed during the distribution and verification process. The information rate of the scheme is 1/2, and the distribution and verification require approximately 2k modular multiplications per bit of the secret. The scheme is based on combining Shamir's secret sharing scheme with a commitment scheme that is unconditionally secure for the committer. The commitment scheme allows the dealer to commit to a secret value without revealing it, and it enables the verification of shares without requiring interaction between participants. The scheme is efficient, with the commitment process requiring less than 2|q| multiplications modulo p or less than two multiplications per bit of the secret. The paper also shows how a group of participants can choose a secret "in the well" and distribute it verifiably among themselves. This is achieved by having each participant generate a random value, distribute it verifiably, and then combine the values to form the secret. The resulting secret is uniformly distributed and remains unknown to fewer than k participants. The scheme is compared to other non-interactive VSS schemes, such as those in [Fel87], and is shown to be dual in nature. While [Fel87] relies on computational assumptions, this scheme provides unconditional security for the dealer but depends on the assumption that the dealer cannot solve the discrete logarithm problem. The paper also demonstrates that linear combinations of shared secrets can be computed efficiently, and that the scheme can be generalized to allow l participants to select and distribute a secret democratically. The scheme is efficient, secure, and suitable for practical applications, particularly in scenarios where non-interactive verification is required. It is optimal in the sense that it is impossible to construct a non-interactive VSS scheme that reveals no information about the secret and is secure against an infinitely powerful dealer.
Reach us at info@study.space