Key generation using multiple sets of secret shares

• US 9,106,407 B2
• Filed: 04/23/2012
• Issued: 08/11/2015
• Est. Priority Date: 06/20/2011
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Kipnis, Aviad, Hibshoosh, Eliphaz
• Primary Examiner(s): Traore, Fatoumata
• Application Number:
  US13/976,717
• Publication Number:
  US 20130272521A1
• Time in Patent Office: 1,205 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 9/0816 Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
• CPC Class Codes: H04L 9/0833 involving conference or group key network architectures or network communication protocols for key management in group communication in a packet data network H04L63/065
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0869 involving random numbers or seeds

Abstract

A cryptographic method, including generating, using a meta-secret, a first plurality of cryptographic keys, each cryptographic key associated with a respective key identifier, creating, using the meta-secret, a second plurality of sets of secret-shares, which are capable, by combining all the secrets-shares in any one of the sets together with the respective key identifier, of generating the associated cryptographic key, and performing cryptographic operations using the cryptographic keys. Related methods and apparatus are also included.

Claims

1. A cryptographic method, comprising:

providing, by a processor, a meta-secret used both to generate a first plurality of cryptographic keys and a second plurality of different sets of secret-shares, each of the cryptographic keys being associated with a respective key identifier, the meta-secret being a secret data structure including an ordered sequence of data values;

generating, by the processor, each one of the cryptographic keys as a function of the meta-secret and the respective key identifier of the one cryptographic key;

creating, using the meta-secret, by the processor, the second plurality of different sets of secret-shares, which are capable;

by combining all the secret-shares in any one of the sets together with the respective key identifier without knowledge of the meta-secret, of generating the associated cryptographic key;

by combining all the secret-shares in any one of the sets together with a first key identifier without knowledge of the meta-secret, of generating a first cryptographic key; and

by combining all the secret-shares in any one of the sets together with a second key identifier without knowledge of the meta-secret, of generating a second cryptographic key;

wherein combining all the secret-shares in any one of the sets together with a different key identifier without knowledge of the meta-secret generates a different cryptographic key;

performing, by the processor, cryptographic operations using the cryptographic keys, wherein performing the cryptographic operations comprises encrypting an item of data using the first cryptographic key; and

distributing the sets of secret-shares over a network to different respective subscribers, using a network interface, wherein the different respective subscribers are operative to;

combine the received secret-shares together with the respective key identifier without knowledge of the meta-secret to generate the first cryptographic key; and

decrypt the item of data using the first cryptographic key, wherein the secret-shares in one of the sets are decrypted following a process of authentication so that the secret-shares can be used to generate the first cryptographic key so as to decrypt the item of data only after the authentication.

2. The method according to claim 1, wherein performing the cryptographic operations comprises encrypting an item of data using one of the cryptographic keys so as to enable decryption of the item only by combining all the secret-shares in any one of the sets.

3. The method according to claim 2, wherein encrypting the items of data comprises encrypting multiple items of data using different ones of the cryptographic keys, so as to enable decryption of the items by combining all the secret-shares in any one of the sets with different key identifiers that are respectively associated with the different ones of the cryptographic keys.

4. The method according to claim 3, wherein the sets of secret-shares each comprise first and second secret-shares, and wherein the method comprises:

providing the first and second secret-shares in each set to different first and second devices in each of the subscriber premises, which operate in combination to generate the cryptographic keys so as to decrypt the items of data.

5. The method according to claim 4, wherein the first and second devices respectively comprise a security module and a host device, to which the security module is coupled and which is configured to output the decrypted items of data.

6. The method according to claim 4, wherein the first and second devices comprise respective first and second security modules.

7. The method according to claim 1, wherein the sets of secret-shares each comprise first and second secret-shares, which are decrypted respectively by two independent content access centers.

8. The method according to claim 1, wherein the items of the data are encrypted and the secret-shares are generated by a content provider, and

wherein the secret-shares are distributed with the key identifiers to the subscribers by a content broker, which is unable to access the items of the data in an unencrypted form or to generate the secret-shares or the cryptographic keys.

9. The method according to claim 1, wherein the meta-secret comprises a sequence of matrices, and wherein generating the cryptographic keys comprises computing a respective bit string corresponding to each key identifier, and taking a trace of a product of a sub-sequence of the matrices that is indexed by the bit string.

10. The method according to claim 9, wherein computing the respective bit string comprises calculating a hash function over the key identifier.

11. The method according to claim 1, wherein combining all the secret-shares comprises:

applying each of the secret-shares within a set together with the key identifier to generate a respective key-share, thereby producing multiple, different key-shares; and

combining the key-shares to generate the cryptographic key.

12. The method according to claim 1, wherein the meta-secret comprises a first sequence of first matrices, and wherein creating the sets of the secret-shares comprises, for a given secret-share within a set, finding a second sequence of second matrices such that a first characteristic polynomial of a k^th matrix in the first sequence of first matrices divides a second characteristic polynomial of a tensor product of all k^th second matrices in the second sequence for all the secret-shares in the set.

13. The method according to claim 12, wherein finding the second sequences comprises:

finding matrices {A_ijk′

} such that a product of all the matrices A′

_ijk over a secret-share index j within the set is equal to the r^th matrix in the first sequence, and all A′

_ijk commute for all indices j and r; and

transforming the matrices {A_ijk′

} using random invertible matrices T_i,j to give transformed matrices A_ijk=T_i,j·

A_ijk′

·

T_i,j<sup>−

1</sup> that make up the secret-shares.

14. The method according to claim 12, wherein combining all the secret-shares comprises, for a given set in the second plurality:

computing a bit string corresponding to the respective key identifier;

for each of the secret-shares in the given set, computing a product of a respective sub-sequence of the second matrices that is indexed by the bit string, and generating a polynomial based on the product; and

extracting a coefficient of the polynomial to provide the cryptographic key that is associated with the key identifier.

15. The method according to claim 14, wherein generating the polynomial comprises:

taking a recursive tensor product of a set of third matrices defined by the product of the respective sub-sequence for all the secret-shares;

extracting a characteristic polynomial from the tensor product of all the third matrices; and

finding a greatest common denominator of the characteristic polynomial with a further polynomial that is associated with the key identifier to give a result polynomial from which the coefficient is extracted.

16. The method according to claim 1, and comprising decomposing at least one of the secret-shares to generating a subsidiary set of subsidiary secret-shares, which are capable, by combining all the subsidiary secret-shares in the subsidiary set together with the respective key identifier, of generating a key-share associated with the at least one of the secret-shares.

17. Cryptographic apparatus, comprising:

a memory, which is configured to hold a meta-secret used both to generate a first plurality of cryptographic keys and a second plurality of different sets of secret-shares, each of the cryptographic keys being associated with a respective key identifier, the meta-secret being a secret data structure including an ordered sequence of data values; and

a processor, which is configured;

to generate each one of the cryptographic keys as a function of the meta-secret and the respective key identifier of the one cryptographic key;

to create, using the meta-secret, the second plurality of different sets of secret-shares, which are capable;

by combining all the secret-shares in any one of the sets together with the respective key identifier without knowledge of the meta-secret, of generating the associated cryptographic key;

by combining all the secret-shares in any one of the sets together with a first key identifier without knowledge of the meta-secret, of generating a first cryptographic key; and

by combining all the secret-shares in any one of the sets together with a second key identifier without knowledge of the meta-secret, of generating a second cryptographic key;

wherein combining all the secret-shares in any one of the sets together with a different key identifier without knowledge of the meta-secret generates a different cryptographic key;

to perform cryptographic operations using the cryptographic keys; and

to distribute the sets of secret-shares over a network to different respective subscribers, using a network interface, wherein performing the cryptographic operations comprises encrypting an item of data using the first cryptographic key and wherein the different respective subscribers are operative to;

combine the received secret-shares together with the respective key identifier without knowledge of the meta-secret to generate, the first cryptographic key; and

decrypt the item of data using the first cryptographic key, wherein the secret-shares in one of the sets are decrypted following a process of authentication so that the secret-shares can be used to generate the first cryptographic key so as to decrypt the item of data only after the authentication.

18. A computer software product, comprising a non-transitory computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to:

provide a meta-secret used both to generate a first plurality of cryptographic keys and a second plurality of different sets of secret-shares, each of the cryptographic keys being associated with a respective key identifier, the meta-secret being a secret data structure including an ordered sequence of data values;

generate each one of the cryptographic keys as a function of the meta-secret and the respective key identifier of the one cryptographic key;

create, using the meta-secret, the second plurality of different sets of secret-shares, which are capable;

by combining all the secret-shares in any one of the sets together with the respective key identifier without knowledge of the meta-secret, of generating the associated cryptographic key;

by combining all the secret-shares in any one of the sets together with a first key identifier without knowledge of the meta-secret, of generating a first cryptographic key; and

by combining all the secret-shares in any one of the sets together with a second key identifier without knowledge of the meta-secret, of generating a second cryptographic key;

wherein combining all the secret-shares in any one of the sets together with a different key identifier without knowledge of the meta-secret generates a different cryptographic key;

perform cryptographic operations using the cryptographic keys, wherein performing the cryptographic operations comprises encrypting an item of data using the first cryptographic key; and

distribute the sets of secret-shares over a network to different respective subscribers, using a network interface, wherein the different respective subscribers are operative to;

combine the received secret-shares together with the respective key identifier without knowledge of the meta-secret to generate the first cryptographic key; and

decrypt the item of data using the first cryptographic key, wherein the secret-shares in one of the sets are decrypted following a process of authentication so that the secret-shares can be used to generate the first cryptographic key so as to decrypt the item of data only after the authentication.