How to Share a Secret

How to Share a Secret

November 1979 | Adi Shamir
This paper presents a method for securely sharing a secret by dividing it into n pieces such that any k pieces can reconstruct the secret, but fewer than k pieces reveal no information about it. This is known as a (k, n) threshold scheme. The scheme is useful for key management in cryptographic systems, allowing secure and reliable access even if some pieces are lost or compromised. For example, with n=2k-1, the scheme ensures that the original key can be recovered even if k-1 pieces are destroyed, while an attacker cannot reconstruct the key even if they obtain k-1 pieces. The scheme is based on polynomial interpolation. A random polynomial of degree k-1 is created, with the constant term being the secret. Each piece is a value of this polynomial evaluated at a distinct point. Any k pieces allow reconstruction of the polynomial and thus the secret, while fewer than k pieces do not. Modular arithmetic is used to ensure security. The scheme has several advantages over mechanical locks and keys. Each piece is no larger than the original data, and pieces can be dynamically added or removed. The secret can be changed by updating the polynomial without altering the existing pieces. Additionally, the scheme can be hierarchical, allowing different levels of access based on the importance of participants. The paper also mentions a different threshold scheme developed by Blakley. The method is efficient and practical for key management, with algorithms for polynomial evaluation and interpolation discussed. The scheme is applicable in various scenarios, including digital signatures and secure group cooperation.This paper presents a method for securely sharing a secret by dividing it into n pieces such that any k pieces can reconstruct the secret, but fewer than k pieces reveal no information about it. This is known as a (k, n) threshold scheme. The scheme is useful for key management in cryptographic systems, allowing secure and reliable access even if some pieces are lost or compromised. For example, with n=2k-1, the scheme ensures that the original key can be recovered even if k-1 pieces are destroyed, while an attacker cannot reconstruct the key even if they obtain k-1 pieces. The scheme is based on polynomial interpolation. A random polynomial of degree k-1 is created, with the constant term being the secret. Each piece is a value of this polynomial evaluated at a distinct point. Any k pieces allow reconstruction of the polynomial and thus the secret, while fewer than k pieces do not. Modular arithmetic is used to ensure security. The scheme has several advantages over mechanical locks and keys. Each piece is no larger than the original data, and pieces can be dynamically added or removed. The secret can be changed by updating the polynomial without altering the existing pieces. Additionally, the scheme can be hierarchical, allowing different levels of access based on the importance of participants. The paper also mentions a different threshold scheme developed by Blakley. The method is efficient and practical for key management, with algorithms for polynomial evaluation and interpolation discussed. The scheme is applicable in various scenarios, including digital signatures and secure group cooperation.
Reach us at info@study.space