Methods and apparatus for password-based secret sharing schemes

Patent metadata

Field	Value
Publication number	US-9813243-B1
Application number	US-201514672507-A
Country	US
Kind code	B1
Filing date	Mar 30, 2015
Priority date	Mar 30, 2015
Publication date	Nov 7, 2017
Grant date	Nov 7, 2017

Abstract

Methods and apparatus are provided for password-based secret sharing. An exemplary method comprises obtaining a secret; obtaining a fixed value from at least one party; setting at least one polynomial coefficient of a polynomial employed by a polynomial-based secret sharing scheme to a value that depends on the fixed value and the secret; and applying the polynomial-based secret sharing scheme to the secret to obtain a plurality of secret shares, wherein the plurality of secret shares comprises at least one fixed share derived from the at least one polynomial coefficient. Another exemplary secret sharing method comprises selecting at least one fixed share of a plurality of shares employed by an additive secret sharing scheme that splits the secret into the plurality of shares needed for reconstruction of the secret, wherein the at least one fixed share depends on the fixed value; and setting at least one masked version of the secret employed by the additive secret sharing scheme, wherein the at least one masked version of the secret depends on the at least one fixed share.

First claim

What is claimed is:

1. A method, comprising:
obtaining a secret, wherein said secret protects at least one data item;
obtaining a fixed value from at least one party, wherein said fixed value is distinct from said secret;
setting, using at least one processing device, at least one polynomial coefficient of a polynomial employed by a polynomial-based secret sharing scheme to a value that depends on said fixed value and said secret, wherein said at least one polynomial coefficient has a degree of at least one;
applying, using said at least one processing device, said polynomial-based secret sharing scheme to said secret to obtain a plurality of secret shares, wherein said plurality of secret shares comprises at least one fixed share derived from said at least one polynomial coefficient; and
providing one or more of said plurality of secret shares to at least one device during a secret sharing phase, such that said secret is reconstructed during a secret reconstruction phase only when a predefined minimum number of said plurality of secret shares are provided to one or more authentication servers.

2. The method of claim 1 , wherein said fixed value comprises one or more of secret information related to said at least one party and a password of said at least one party.

3. The method of claim 1 , wherein said at least one polynomial coefficient depends on a value obtained by applying a compressed-range function to said fixed value.

4. The method of claim 1 , wherein a different one of said fixed values is obtained from each of a plurality of parties and wherein said step of setting at least one polynomial coefficient of a polynomial comprises setting a plurality of said polynomial coefficients in a manner that depends on said fixed values obtained from said plurality of parties and said secret.

5. The method of claim 1 , wherein said at least one polynomial coefficient further depends on a random value.

6. The method of claim 1 , further comprising the step of setting a second polynomial coefficient of said polynomial to be equal to said secret.

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

8. 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 secret, wherein said secret protects at least one data item;
obtaining a fixed value from at least one party, wherein said fixed value is distinct from said secret;
setting, using at least one processing device, at least one polynomial coefficient of a polynomial employed by a polynomial-based secret sharing scheme to a value that depends on said fixed value and said secret, wherein said at least one polynomial coefficient has a degree of at least one;
applying, using said at least one processing device, said polynomial-based secret sharing scheme to said secret to obtain a plurality of secret shares, wherein said plurality of secret shares comprises at least one fixed share derived from said at least one polynomial coefficient; and
providing one or more of said plurality of secret shares to at least one device during a secret sharing phase, such that said secret is reconstructed during a secret reconstruction phase only when a predefined minimum number of said plurality of secret shares are provided to one or more authentication servers.

9. A secret sharing method, comprising:
obtaining a secret, wherein said secret protects at least one data item;
obtaining a fixed value from at least one party, wherein said fixed value is distinct from said secret;
selecting, using at least one processing device, at least one fixed share of a plurality of shares employed by an additive secret sharing scheme that splits said secret into said plurality of shares needed for reconstruction of said secret, wherein said at least one fixed share depends on a value obtained by applying a compressed-range function to said fixed value;
setting, using said at least one processing device, at least one masked version of said secret employed by said additive secret sharing scheme, wherein said at least one masked version of said secret depends on said at least one fixed share; and
providing one or more of said plurality of shares to at least one device during a secret sharing phase, such that said secret is reconstructed during a secret reconstruction phase only when a predefined minimum number of said plurality of shares are provided to one or more authentication servers.

10. The method of claim 9 , wherein said fixed value comprises one or more of secret information related to said at least one party and a password of said at least one party.

11. The method of claim 9 , further comprising the step of selecting one or more non-fixed shares for one or more additional parties, wherein said one or more non-fixed shares comprise a randomly selected κ-bit string.

12. The method of claim 11 , further comprising the steps of providing said fixed share to said at least one party; and providing said one or more non-fixed shares to said corresponding one or more additional parties.

13. The method of claim 9 , wherein said step of setting at least one masked version of said secret further comprises a result of an additive operation applied to an encrypted version of a unique nonce associated with each of said plurality of shares needed for said reconstruction of said secret.

14. The method of claim 13 , wherein said unique nonce associated with each of said plurality of shares masks said secret for each of said plurality of shares independently of other shares.

15. The method of claim 9 , wherein each party in a minimal set of parties needed to reconstruct said secret can decrypt said at least one masked version of said secret by incrementally removing one or more mask values from a current masked version of said secret to recover said secret.

16. The method of claim 9 , wherein t shares comprise a minimal authorized set needed for said reconstruction of said secret and wherein said t shares must be obtained in a predefined order to reconstruct said secret.

17. The method of claim 9 , further comprising the step of providing one or more of a derived share for reconstruction of said secret and a response to a mask value query performed to reconstruct said secret.

18. The method of claim 9 , further comprising the step of providing a plurality of parties in a given authorized set with auxiliary information comprising a unique nonce and said at least one masked version of said secret, wherein said plurality of parties in said given authorized set jointly unmask the secret.

19. The method of claim 9 , further comprising the step of providing a plurality of parties in a given authorized set with auxiliary information comprising a unique nonce, wherein each of said plurality of parties in said given authorized set provide a derived share to a reconstructor entity possessing said at least one masked version of said secret for reconstruction of said secret.

20. The method of claim 9 , wherein each of said plurality of parties in said given authorized set provide a derived share for a particular unique nonce to a reconstructor entity for reconstruction of said secret.

21. The method of claim 9 , wherein said at least one masked version of said secret comprises said secret, and wherein one or more of

Assignees

• Emc Ip Holding Co Llc

Inventors

• Triandopoulos Nikolaos
• Rivest Ronald

Classifications

• H04L9/08

  Key distribution {or management, e.g. generation, sharing or updating, of cryptographic keys or passwords (network architectures or network communication protocols for supporting key management in a packet data network H04L63/06)} · CPC title

• H04L9/0869

  involving random numbers or seeds · CPC title

• H04L63/083

  using passwords (cryptographic mechanisms or cryptographic arrangements for entity authentication using a predetermined code H04L9/3226) · CPC title

• H04L2209/24

  Key scheduling, i.e. generating round keys or sub-keys for block encryption · CPC title

• H04L9/3093 Primary

  involving Lattices or polynomial equations, e.g. NTRU scheme · CPC title