Distributed proactive password-based secret sharing

• US 9,813,244 B1
• Filed: 12/30/2015
• Issued: 11/07/2017
• Est. Priority Date: 12/30/2015
• Status: Active Grant

• Current Assignee: RSA Security LLC (Symphony Technology Group LLC)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Triandopoulos, Nikolaos, Zhang, Yupeng
• Primary Examiner(s): Tolentino, Roderick
• Application Number:
  US14/984,389
• Time in Patent Office: 678 Days
• Field of Search: 380277-282
• CPC Class Codes: H04L 63/061 for key exchange, e.g. in peer-to-peer networks cryptographic mechanisms or cryptographic arrangements for key agreement H04L9/0838
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0863 involving passwords or one-time passwords network architectures or network communication protocols for using one-time keys in a packet data network H04L63/067
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying

Abstract

Distributed proactive threshold password-based secret sharing schemes are provided. An exemplary method comprises obtaining a difference between updated and prior values of a share for at least one fixed-share party. The updated value comprises a fixed share that is one of a plurality of shares of a secret held by a plurality of parties. A fixed-share party randomly selects a first correction polynomial employed by a polynomial-based secret sharing scheme such that at least one polynomial coefficient corresponding to the fixed-share party is a value that depends on the difference. A non-fixed-share party randomly selects a second correction polynomial such that at least one corresponding polynomial coefficient corresponding to the non-fixed-share party is approximately zero. A polynomial coefficient of the second correction polynomial is obtained from the non-fixed-share party and the fixed share is updated by combining the prior value of the share with the at least one corresponding polynomial coefficient of the first correction polynomial and the polynomial coefficient of the second correction polynomial.

Claims

1. A method, comprising:

obtaining a difference between an updated value of a share and a prior value of said share for at least one fixed-share party, wherein said updated value comprises a fixed share that is one of a plurality of shares of a secret, wherein said plurality of shares are held by a plurality of parties;

substantially randomly selecting, by said at least one fixed-share party, a first correction polynomial employed by a polynomial-based secret sharing scheme such that at least one polynomial coefficient corresponding to said at least one fixed-share party is a value that depends on the difference, wherein at least one non-fixed-share party substantially randomly selects a second correction polynomial such that at least one corresponding polynomial coefficient corresponding to said at least one non-fixed-share party is approximately zero;

obtaining said at least one corresponding polynomial coefficient of said second correction polynomial from said at least one non-fixed-share party; and

updating said fixed share by combining said prior value of said share with said at least one corresponding polynomial coefficient of said first correction polynomial and said at least one corresponding polynomial coefficient of said second correction polynomial.

2. The method of claim 1, wherein said step of substantially randomly selecting said first correction polynomial further comprises setting a polynomial coefficient corresponding to said secret to approximately zero.

3. The method of claim 1, wherein said step of substantially randomly selecting said first correction polynomial further comprises setting at least one polynomial coefficient of said first correction polynomial corresponding to other parties having at least one fixed share to a value that is approximately zero.

4. The method of claim 1, wherein said at least one non-fixed-share party substantially randomly selects said second correction polynomial such that at least one polynomial coefficient of said second correction polynomial corresponding to parties having at least one fixed share has a value that is approximately zero.

5. The method of claim 1, wherein said difference is zero.

6. The method of claim 1, further comprising the step of performing a share verification process to verify a correctness of correction polynomials chosen by said plurality of parties and resolving zero or more conflicts using an accusation phase.

7. The method of claim 1, wherein said polynomial-based secret sharing scheme comprises a (2t−

1, n) secret sharing scheme for said plurality, n, of parties, wherein t shares comprise a minimal authorized set needed for reconstruction of said secret and wherein t−

1 of said plurality of shares comprise public shares, wherein said first and second correction polynomials are of degree 2t−

2, and wherein said public shares are updated by substantially randomly selecting, by each of said fixed-share parties and said non-fixed-share parties, a third correction polynomial employed by said polynomial-based secret sharing scheme for each party managing a public share, such that coefficients corresponding to said public share parties are approximately zero;

wherein each of said fixed-share parties, said non-fixed-share parties and said public share parties sends corresponding coefficients to others of said fixed-share parties, said non-fixed-share parties and said public share parties;

wherein each of said fixed-share parties, said non-fixed-share parties and said public share parties computes an update value for a given public share and sends said update value for said given public share to said corresponding public share party; and

wherein said corresponding public share party computes said corresponding public share and publishes said corresponding public share.

8. The method of claim 1, further comprising the steps of verifying, for said at least one fixed-share party by at least one additional party, that a coefficient corresponding to said secret is approximately zero, that coefficients of said first correction polynomial corresponding to each additional fixed-share party are approximately zero, a fourth correction polynomial raised to a power based on coefficients of said first correction polynomial corresponding to each of said fixed-share parties is set to said fourth correction polynomial raised to a desired shift of said respective fixed-share party, providing, by said fixed-share parties, said fourth correction polynomial raised to said respective desired shift;

and verifying, by said fixed-share parties, that a received shift is substantially equal to an evaluation of said first correction polynomial at a point corresponding to said respective fixed-share party.

9. The method of claim 1, wherein a number of parties compromised by one or more adversaries is known to be significantly less than the total number of parties, and wherein only 2t−

1 of said parties randomly select said first correction polynomial, wherein said 2t−

1 parties include said fixed-share parties.

10. The method of claim 1, wherein said polynomial-based secret sharing scheme comprises a (t−

1,k,n) secret sharing scheme with a gap between a reconstruction threshold and a number of malicious parties, such that a party with k shares can reconstruct the secret, while an adversary with t−

1 shares cannot learn the secret, where k>

t−

1, wherein a polynomial f of degree k+t−

2 is chosen and wherein t−

1 public shares are published, wherein m parties, where m≦

t−

2 change their shares to new fixed values, and k−

2−

m additional parties keep their shares unchanged and do not receive information to update their shares, and wherein only 2t−

1 parties compute said first correction polynomial.

11. The method of claim 1, wherein said fixed share is based on one or more of secret information related to said at least one party and a password of said at least one party.

12. The method of claim 11, wherein said at least one polynomial coefficient depends on a value obtained by applying a compressed-range function to said one or more of said secret information related to said at least one party and said password of said at least one party.

13. The method of claim 1, wherein said secret protects at least one data item.

14. The method of claim 1, wherein t shares comprise a minimal authorized set needed for reconstruction of said secret and wherein said t shares must be obtained to reconstruct said secret.

15. A non-transitory machine-readable recordable storage medium, wherein one or more software programs when executed by one or more processing devices implement the following steps:

obtaining a difference between an updated value of a share and a prior value of said sham for at least one fixed-share party, wherein said updated value comprises a fixed share that is one of a plurality of shares of a secret, wherein said plurality of shares are held by a plurality of parties;

substantially randomly selecting, by said at least one fixed-share party, a first correction polynomial employed by a polynomial-based secret sharing scheme such that at least one polynomial coefficient corresponding to said at least one fixed-share party is a value that depends on the difference, wherein at least one non-fixed-share party substantially randomly selects a second correction polynomial such that at least one corresponding polynomial coefficient corresponding to said at least one non-fixed-share party'"'"' is approximately zero;

obtaining said at least one corresponding polynomial coefficient of said second correction polynomial from said at least one non-fixed-share party; and

updating said fixed share by combining said prior value of said share with said at least one corresponding polynomial coefficient of said first correction polynomial and said at least one corresponding polynomial coefficient of said second correction polynomial.

16. An apparatus, comprising:

a memory, and

at least one hardware device, coupled to the memory, operative to implement the following steps;

obtaining a difference between an updated value of a share and a prior value of said share for at least one fixed-share party, wherein said updated value comprises a fixed share that is one of a plurality of shares of a secret, wherein said plurality of shares are held by a plurality of parties;

substantially randomly selecting, by said at least one fixed-share party, a first correction polynomial employed by a polynomial-based secret sharing scheme such that at least one polynomial coefficient corresponding to said at least one fixed-share party is a value that depends on the difference, wherein at least one non-fixed-share party substantially randomly selects a second correction polynomial such that at least one corresponding polynomial coefficient corresponding to said at least one non-fixed-share party is approximately zero;

obtaining said at least one corresponding polynomial coefficient of said second correction polynomial from said at least one non-fixed-share party; and

updating said fixed share by combining said prior value of said share with said at least one corresponding polynomial coefficient of said first correction polynomial and said at least one corresponding polynomial coefficient of said second correction polynomial.

17. The apparatus of claim 16, further comprising the step of performing a share verification process to verify a correctness of correction polynomials chosen by said plurality of parties and resolving zero or more conflicts using an accusation phase.

18. The apparatus of claim 16, wherein said polynomial-based secret sharing scheme comprises a (2t−

1, n) secret sharing scheme for said plurality, n, of parties, wherein t shares comprise a minimal authorized set needed for reconstruction of said secret and wherein t−

1 of said plurality of shares comprise public shares, wherein said first and second correction polynomials are of degree 2t−

2, and wherein said public shares are updated by substantially randomly selecting, by each of said fixed-share parties and said non-fixed-share parties, a third correction polynomial employed by said polynomial-based secret sharing scheme for each party managing a public share, such that coefficients corresponding to said public share parties are approximately zero;

wherein each of said fixed-share parties, said non-fixed-share parties and said public share parties sends corresponding coefficients to others of said fixed-share parties, said non-fixed-share parties and said public share parties;

wherein each of said fixed-share parties, said non-fixed-share parties and said public share parties computes an update value for a given public share and sends said update value for said given public share to said corresponding public share party, and wherein said corresponding public share party computes said corresponding public share and publishes said corresponding public share.

19. The apparatus of claim 16, further comprising the steps of verifying, for said at least one fixed-share party by at least one additional party, that a coefficient corresponding to said secret is approximately zero, that coefficients of said first correction polynomial corresponding to each additional fixed-share party are approximately zero, a fourth correction polynomial raised to a power based on coefficients of said first correction polynomial corresponding to each of said fixed-share parties is set to said fourth correction polynomial raised to a desired shift of said respective fixed-share party providing, by said fixed-share parties, said fourth correction polynomial raised to said respective desired shift;

and verifying, by said fixed-share parties, that a received shift is substantially equal to an evaluation of said first correction polynomial at a point corresponding to said respective fixed-share party.

20. The apparatus of claim 16, wherein t shares comprise a minimal authorized set needed for reconstruction of said secret and wherein said t shares must be obtained to reconstruct said secret.