Key Generation Using Multiple Sets of Secret Shares

• US 20130272521A1
• Filed: 04/23/2012
• Published: 10/17/2013
• 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
• Granted Patent: US 9,106,407 B2
• Time in Patent Office: Days
• US Class Current: 380/44
• 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 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 respective key identifier, the meta-secret being a secret data structure including an ordered sequence of data values;

generating 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, the second plurality of different 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 without knowledge of the meta-secret, of generating the associated cryptographic key; and

performing cryptographic operations using the cryptographic keys.

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:

distributing the sets of secret-shares to different, respective subscriber premises; and

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 3, and comprising distributing the sets of secret-shares to different, respective subscribers in an encrypted form, wherein the secret-shares in each of the sets are decrypted following a process of authentication so that the secret-shares can be used to generate the cryptographic keys so as to decrypt the items of data only after the authentication.

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

9. The method according to claim 7, 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.

10. 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.

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

12. The method according to claim 1, wherein combining all the secrets-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.

13. 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.

14. The method according to claim 13, 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.

15. The method according to claim 13, 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.

16. The method according to claim 15, 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.

17. 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 secrets-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.

18-26. -26. (canceled)

27. 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, and to create, using the meta-secret, the second plurality of different 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 without knowledge of the meta-secret, of generating the associated cryptographic key, and to perform cryptographic operations using the cryptographic keys.

28-53. -53. (canceled)

54. A cryptographic system, comprising:

a content provider, which is configured to generate a first plurality of cryptographic keys, each cryptographic key associated with a respective key identifier, to encrypt a respective item of content using each cryptographic key, to generate a second plurality of sets of secret-shares, and to produce first tickets, each containing a respective set of the secret-shares;

a content broker, which is configured to produce second tickets, each comprising the respective set of the secret-shares in a respective one of the first tickets and the respective key identifier for the item of content that is encrypted using the associated cryptographic key, and to furnish the second tickets to subscribers;

a first content access center, which is coupled to receive from a subscriber a first one of the secret-shares in one of the second tickets, to authenticate the subscriber, and to return a first key-share to the subscriber; and

a second content access center, which is coupled to receive from the subscriber a second one of the secret-shares in one of the second tickets, to validate access to the item of content, and to return a second key-share to the subscriber,

whereby the subscriber combines the first and second key-shares to generate the cryptographic key and decrypt the item of content.

55. A computer software product, comprising a 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 secrets-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; and

perform cryptographic operations using the cryptographic keys.

56. (canceled)