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.

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention relates generally to digital communications, and specifically to methods and systems for secure transmission and reception of digital information. 
       BACKGROUND OF THE INVENTION 
       [0002]    Many digital content distribution systems use conditional access (CA), which requires the receiver to meet certain criteria before being able to decrypt and display a given content item, such as a video program or broadcast channel. The content is encrypted using a secret key, referred to as a control word (CW). (This sort of encryption is commonly referred to as “scrambling.”) The CW itself is encrypted by entitlement control messages (ECMs), which are transmitted from the system head-end to receivers of the content item. The CA subsystem (such as a secure smart card) in each receiver decrypts the ECM to recover the CW for a given content channel, but only when the receiver is authorized to do so by an entitlement management message (EMM) for the given channel. EMMs are typically transmitted periodically (for example, once per month) to the CA subsystem, depending on the subscriber&#39;s service plan. 
         [0003]    In secret sharing schemes, a secret (such as a cryptographic key) is shared among a group of participants, each of whom is allocated a share of the secret. The secret can be reconstructed only when a sufficient number of secret-shares are combined together, while individual shares are of no use on their own. A method for secret sharing based on polynomials, for example, was described by Shamir in “How to Share a            
       SUMMARY 
       [0004]    Embodiments of the present invention that are described hereinbelow provide efficient methods for secret sharing. 
         [0005]    There is therefore provided, in accordance with an embodiment of the present invention, a cryptographic method, which includes generating, using a meta-secret, a first plurality of cryptographic keys, each cryptographic key associated with a respective key identifier. The meta-secret is used to create 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. Cryptographic operations are performed using the cryptographic keys. 
         [0006]    Typically, performing the cryptographic operations includes 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. In disclosed embodiments, encrypting the items of data includes 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. 
         [0007]    In some embodiments, the sets of secret-shares each include first and second secret-shares, and the method includes 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. The first and second devices may respectively include 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. Alternatively, the first and second devices may include respective first and second security modules. 
         [0008]    In other embodiments, the method includes 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. The sets of secret-shares may each include first and second secret-shares, which are decrypted respectively by two independent content access centers. In a disclosed embodiment, the items of the data are encrypted and the secret-shares are generated by a content provider, and 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. 
         [0009]    In disclosed embodiments, the meta-secret includes a sequence of matrices, and generating the cryptographic keys includes 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. Computing the respective bit string may include calculating a hash function over the key identifier. 
         [0010]    In a disclosed embodiment, combining all the secrets-shares includes 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. In some embodiments, the meta-secret includes a first sequence of first matrices, and creating the sets of the secret-shares includes, 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. In a disclosed embodiment, finding the second sequences includes 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   −1  that make up the secret-shares. 
         [0011]    Additionally or alternatively, combining all the secret-shares includes, 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. Generating the polynomial may include 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. 
         [0012]    The method may include 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. 
         [0013]    There is also provided, in accordance with an embodiment of the present invention, a cryptographic method, which includes receiving a set of secret-shares and receiving a plurality of key identifiers, each key identifier associated with a different, respective cryptographic key. All the secret-shares are used together with any one of the key identifiers to generate the associated cryptographic key, which may be used in performing a cryptographic operation. 
         [0014]    In some embodiments, using all the secret-shares includes applying each of the secret-shares 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. In some of these embodiments, applying each of the secret-shares includes applying first and second secret-shares respectively in different first and second devices in order to generate first and second key-shares, which are combined to generate the cryptographic key. The first and second devices may respectively include a security module and a host device, to which the security module is coupled and which is configured to perform the cryptographic operation using the cryptographic key. Alternatively, the first and second devices may respectively include first and second security modules, which are coupled to different respective host devices. 
         [0015]    In another embodiment, receiving the set of the secret-shares includes a ticket containing at least first and second secret-shares, and using all the secret-shares includes conveying the first and second secret-shares over a network to first and second servers, respectively, and receiving first and second key-shares from the first and second servers in order to generate the cryptographic key. The first and second servers may respectively include two independent and separate content access centers. 
         [0016]    Typically, the set of secret-shares is one of multiple different sets of different secret-shares, any of which sets can be used with any one of the key identifiers to generating the associated cryptographic key. 
         [0017]    There is additionally provided, in accordance with an embodiment of the present invention, cryptographic apparatus, including a memory, which is configured to hold a meta-secret. A processor is configured to generate, using the meta-secret, a first plurality of cryptographic keys, each cryptographic key associated with a respective key identifier, and to create, 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 to perform cryptographic operations using the cryptographic keys. 
         [0018]    There is further provided, in accordance with an embodiment of the present invention, cryptographic apparatus, including multiple memories, which are configured to store respective secret-shares in a set of the secret-shares. Multiple processors are coupled to respective ones of the memories and are configured to receive a plurality of key identifiers, each key identifier associated with a different, respective cryptographic key. The processors are configured to cooperate in using all the secret-shares together with any one of the key identifiers to generate the associated cryptographic key, so as to enable a cryptographic operation to be performed using the cryptographic key. 
         [0019]    There is moreover provided, in accordance with an embodiment of the present invention, cryptographic apparatus, including an interface, which is configured to receive over a network a set of secret-shares and to receive a key identifier associated with a cryptographic key. A processor is configured to transmit the secret-shares over the network to different, respective servers, to receive key-shares computed by the servers using the secret-shares, to combine the key-shares with any one of the key identifiers to generate the associated cryptographic key, and to perform a cryptographic operation using the cryptographic key. 
         [0020]    There is furthermore provided, in accordance with an embodiment of the present invention, a cryptographic system, including 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 is configured to produce second tickets, each including 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 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. A second content access center 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. The subscriber combines the first and second key-shares to generate the cryptographic key and decrypt the item of content. 
         [0021]    There is also provided, in accordance with an embodiment of the present invention, a computer software product, including a computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to generate, using a meta-secret, a first plurality of cryptographic keys, each cryptographic key associated with a respective key identifier, to create, 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 to perform cryptographic operations using the cryptographic keys. 
         [0022]    There is additionally provided, in accordance with an embodiment of the present invention, a computer software product, including a computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to receive a set of secret-shares and to receive a plurality of key identifiers, each key identifier associated with a different, respective cryptographic key, to use all the secret-shares with any one of the key identifiers to generate the associated cryptographic key, and to perform a cryptographic operation using the cryptographic key. 
         [0023]    The present invention will be more fully understood from the following detailed description of the embodiments thereof, taken together with the drawings in which: 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0024]      FIG. 1  is a schematic, pictorial illustration of a content distribution system, in accordance with an embodiment of the present invention; 
           [0025]      FIG. 2  is a block diagram that schematically illustrates a digital content receiver, in accordance with an embodiment of the present invention; 
           [0026]      FIG. 3  is a block diagram that schematically illustrates interactions between elements of a content distribution system using a secret-sharing scheme, in accordance with an embodiment of the present invention; and 
           [0027]      FIGS. 4-6  are block diagrams that schematically illustrate schemes for key generation, in accordance with an embodiment of the present invention. 
       
    
    
     DETAILED DESCRIPTION OF EMBODIMENTS 
     Overview 
       [0028]    Secret sharing can be an effective way to enhance the security of cryptographic applications, since such schemes require users to assemble multiple secret-shares in order to generate the desired key. Secret sharing techniques that are known in the art provide multiple sets of secret-shares where each set of secret-shares is equivalent in generating only a single key. This limitation can make large-scale applications impractical, as different sets of secret-shares are required for different keys. 
         [0029]    Embodiments of the present invention that are described hereinbelow address this limitation by providing secret-sharing schemes in which multiple different sets of secret-shares can be used (and re-used) to generate a large number of different keys. These keys may be applied in encrypting items of data, and are thus particularly useful in (broadcast) conditional-access content distribution systems, in which many data items are distributed to different subscribers. Each data item is encrypted with its own key, and many copies of the encrypted data item are distributed to many different subscribers. The different data items (which are encrypted with different keys) are identified by unique key identifiers. Each subscriber uses the appropriate identifier together with his or her own distinct set of secret-shares to generate the keys that are needed for decryption of each of the many data items. 
         [0030]    The secret-sharing schemes provided by embodiments of the present invention are based on a meta-secret - an ordered sequence of data values satisfying certain properties (as described below). The meta-secret is used both to generate multiple cryptographic keys and to generate multiple sets of secret-shares. As noted above, each key is typically associated with a particular asset (such as an item of data content), and is uniquely identified by a key identifier. The holder of the meta secret generates each cryptographic key by applying a key generation function to the respective key identifier and the meta-secret. The meta-secret holder also applies a secret-decomposition function to the meta-secret to generate the different sets of secret-shares. 
         [0031]    A set of secret-shares is distributed among different secret holders in such a way that they can generate keys uniquely identified by a key identifier without knowledge of the meta secret. Each secret-share within a set of secret-shares uniquely defines a key-share-generation function that when used with a particular key identifier will provide its corresponding key-share. The resulting set of key-shares (corresponding to the set of secret-shares) are combined to yield the content key. The key-shares can subsequently be traced back to the respective secret-shares that produced them, thus making it possible to detect and take action against users who attempt to foil the scheme by giving their key-shares to others. 
         [0032]    In some embodiments, the sets of secret-shares typically (although not necessarily) with two secret-shares in each set—are distributed to different, respective subscriber premises. Each secret-share in each set is provided to a different decryption devices in the subscriber premises, and these devices operate in combination to generate the cryptographic keys and decrypt the items of data. If one of the devices is swapped or absent, the remaining device (or devices) will be unable to generate the keys. For example, one secret-share may be stored in a security module, such as a smart card, while the other is installed in a host device to which the smart card is coupled. As another example, the two secret-shares are stored in two different smart cards, which are coupled to different host devices. These approaches are helpful both in reducing the vulnerability of the cryptographic system to hacking and in preventing subscribers from sharing their keys with other, unauthorized users because of the inherent pairing of the devices that hold the secret-shares. 
         [0033]    In another embodiment, a content provider uses the meta-secret in generating “virtual tickets” for sale to intermediaries, such as content brokers. Each virtual ticket is a data structure that enables a user (also referred to herein as a “subscriber”) to access an item of content distributed by the content provider. The content broker creates a user-specific-license for the content offered that corresponds to a single virtual ticket instantiated for the specific user. Each content item is encrypted using a key generated by the content provider using the meta-secret, as described above. Each virtual ticket contains a set of secret-shares in an encrypted form, so that the intermediary cannot access the secret-shares or the content. Rather, the subscribers receive corresponding key-shares from authorized secret-share holders, subject to authentication and conditional access checks by the authorized secret-share holders that preclude the possibility of reuse of the virtual tickets. The subscribers then use the key-shares to generate the appropriate key to decrypt the content item that they have selected. This scheme gives the content provider secure, reliable control over content distribution without requiring any sort of relationship of trust with the intermediaries. 
       System Description 
       [0034]      FIG. 1  is a schematic pictorial illustration of a system  20  for distribution of protected digital data, in accordance with an embodiment of the present invention. In the examples described herein, the digital data comprise program content and are alternatively referred to as “assets.” The assets in the present example comprise video programs, which are distributed via a network  22  to various subscriber premises. Network  22  may comprise, for example, a packet network such as the Internet, a commercial cable network, a satellite network, or any other suitable type of wired and/or wireless data communication network or combination of such networks that is known in the art. Each user premises is typically equipped with a suitable receiver  24 , such as personal computer or a set-top box (STB), which receives, decrypts, and decodes the asset from network  22  for user&#39;s consumption on a display monitor  26 . 
         [0035]    Receivers  24  may alternatively comprise any suitable sort of video decoder and may be implemented either as freestanding units, as shown in the figure, or in the form of embedded processing circuitry within a display device, such as a computer, entertainment console, or mobile media player. Furthermore, although the disclosed embodiments focus on video distribution, the principles of the systems and methods described herein may similarly be applied to distribution of substantially any type of media content, such as audio and/or textual media. 
         [0036]    Typically, the assets transmitted in system  20  are encrypted and may be accessed by the user only in accordance with conditional access (CA) constraints. Receiver  24  decrypts the content using a software program running in the receiver and/or a security module, such as a smart card  28 , which uses key-shares to generate control words to be used by the receiver in decrypting selected content. In the embodiments disclosed herein, smart card  28  operates in accordance with a secret sharing scheme, as described in greater detail hereinbelow. 
         [0037]    In the example pictured in  FIG. 1 , users purchase content from a content broker (CB)  30 , such as a local service provider who operates a portal and offers various content items from different content providers. One such content provider (CP)  32  is shown in  FIG. 1 , but in a typical scenario, multiple different content providers offer many different sorts of content items through many different content brokers. The secret-sharing scheme that is implemented in system  20  permits content brokers to purchase and re-sell user licenses for particular content items from content providers in substantially any desired quantity in a simple financial transaction (by automated on-line credit card payment, for example), without the need for any sort of relationship of trust or auditability. The instrument for effecting these transactions is a “virtual ticket,” based on cryptographic secret-sharing, as described below. 
         [0038]    CP  32  generates the keys (also referred to in this specific context as control words) for encrypting and decrypting content items, and also generates the secret-shares used in system  20  to generate the key-shares needed for content decryption by the user for its purchased content. For this purpose, CP  32  typically uses a computer, such as a cryptographic server, which is connected to network  22  by an interface  40 . The server comprises a memory  44 , which holds a meta-secret, i.e., a secret data structure that is used in generating the keys and secret-shares. A processor  42  accesses memory  44 , computes the keys and secret-shares as required, and applies the keys in encrypting content items. A user interface  46  may be used to control and monitor functions of the server. The encrypted content items may be streamed onto network  22  by CP  32 , or they may alternatively be stored in a content repository  34  for subsequent access. 
         [0039]    Processor  42  typically comprises a general-purpose computer processing unit (or a cluster of such units), which is programmed in software to carry out the functions that are described herein. This software may be downloaded to the processor in electronic form, over a network, for example. Additionally or alternatively, the software may be provided and/or stored on tangible computer-readable memory media, such as optical, magnetic, or electronic memory media. Further additionally or alternatively, at least some of the functions of processor  42  may be carried out by hard-wired or programmable digital logic circuits. The computational methods and data structures used by processor  42  in computing secret-shares and keys in one embodiment of the invention are described in the Appendix hereinbelow. 
         [0040]    The content distribution scheme that is described above is facilitated by a number of additional servers on network  22 : a user authorization center (UAC)  36 , which authenticates subscribers and provides user credentials respected by other entities, and two independent content access centers (CAC)  38  and  39 , which validate tickets for particular content items that subscribers purchase from CB  30 . CAC and CAC each can decrypt a respective secret-share that is contained in the user&#39;s “ticket” in order to generate respective key-shares to be sent to the user. Typically, CAC  38  and CAC  39  operate separate and independent servers, each of which holds one of the secret-shares needed to generate the corresponding key-share for any particular content item. Alternatively, the functionality of one of the servers, such as CAC  39 , can be implemented in smart card  28  or in a secure software module running in receiver  24 . Details of the operation of this system are described further hereinbelow with reference to  FIG. 3 . 
         [0041]      FIG. 2  is a block diagram that schematically shows details of receiver  24 , in accordance with an embodiment of the present invention. Receiver  24  sends and receives messages and receives content from network  22  via a network interface  50 . Assuming receiver  24  to be a set top box, a processor  52  in a security module, such as (optional) smart card  28 , may receive and process incoming messages including content licenses for specific content and users (referred to herein as “tickets”) and key-shares for given content items, as described below. The term “ticket,” as used in the context of the present patent application and in the claims, refers to data structures containing information used in controlling access to a particular data item for a particular user; such information includes the secret-shares (decrypted by the CACs) and any limitations on use of the content. A memory  54  in the smart card may store secret-share information, which may be received via interface  50 , as well, or may be pre-stored in the smart card before the card is inserted into receiver  24 . Interface  50  passes content in encrypted form to a host processor  56 , for decryption using appropriate control words. 
         [0042]    Typically, key-shares may be provided to host  56  by entities on network  22 , such as CAC  38  and CAC  39  (as in the embodiment of  FIG. 3 ) or by smart cards  28  (as in the embodiment of  FIG. 6 ); host  56  then combines the key-shares to generate the control word. Alternatively, (as in the embodiment of  FIG. 5 ), host  56  uses the key identifier together with its key-share generation function to produce its key share, and combines it with a second key-share produced by processor  52  in smart card  28  to generate the control word. As another alternative, host  56  has no secret-share and receives one key-share from CAC  38 , and a second key-share from smart card  28 . In any case, the host processor applies the control word to decrypt and output the video content selected by the user. 
         [0043]    Processor  52  and host processor  56  typically comprise general- or special-purpose programmable processors, which are programmed in software (typically firmware) to carry out the functions that are described herein. This software may be downloaded to the processors in electronic form, over a network, for example. Additionally or alternatively, the software may be provided and/or stored on tangible computer-readable memory media, such as optical, magnetic, or electronic memory media. Further additionally or alternatively, at least some of the functions of processors  52  and  56  may be carried out by hard-wired or programmable digital logic circuits. The computational methods and data structures used by these processors in computing and applying keys are described further hereinbelow. 
       Content Destribution Using Virtual Tickets With Secret-Shares 
       [0044]      FIG. 3  is a block diagram that schematically illustrates interactions between elements of system  20  in a scheme for content distribution based on virtual tickets, in accordance with an embodiment of the present invention. Content provider (CP)  32  uses a meta-secret held in memory  44  to produce a large number of serialized virtual tickets (VTs)  62  for content items that are listed in a catalog  60 . The catalog (but not the content itself) and the VTs are available on-line to any content broker (such as CB  30 ). Each VT is good for one content item (or package) and one virtual user, and contains individual secret-shares S 1  and S 2 , which are respectively targeted for the two on-line content access centers (CAC  38  and CAC  39 ). The secret-shares in each VT may be encrypted, using public keys belonging respectively to CAC  38  and CAC  39 , for example. There may be different grades (and prices) of VTs for different types of content items. 
         [0045]    CB  30  buys a batch of such VTs  62  as its business needs dictate, by a simple commercial transaction, such as an on-line credit card payment. Only CP  32  has the meta-secret needed to generate the secret-shares. Thus, content brokers (and other parties) are unable to create new valid VTs, and the VTs can be stored in non-secure storage. The entities responsible for content access and key-share generation preclude the use of VT clones. CB  30  sells or awards content offers  64  to (paying) users, by providing corresponding actual tickets  66  to users registered with UAC  36 . (Registration with UAC  36  is typically a one-time process, which provides credentials to the user and user equipment, such as receiver  24 , and/or smart card  28 . to enable validation and authentication of the user and equipment.) Tickets  66  are the content licenses that enable users to download and decrypt particular items of content from repository  34 . When CB  30  sells a content item from catalog  60  to a specific registered user, it creates the corresponding ticket  66  by securely assigning a single VT  62  to the user, and securely binding the identifier of the content item from the catalog, along with any specific rights and limitations (such as expiration date), to the user “identity,” including the user&#39;s content consumption equipment. The user&#39;s authentication and access to the content are handled by separate and independent CAC  38  and CAC  39 . CB  30  has no security requirements, as it can neither access the content nor duplicate usable VTs. 
         [0046]    Upon receiving ticket  66  from CB  30 , receiver  24  sends access requests to CAC  38  and CAC  39 , containing its UAC-generated credentials, the ticket, which includes the respective secret-shares S 1  and S 2  (typically encrypted, as noted above), and the key identifier (which may also be encrypted) for the content item in question. CAC  38  and CAC  39  check the user credentials, authenticate the user, verify that there are no clones to the ticket, and then generate and return the corresponding key-shares KS 1  and KS 2 , respectively to receiver  24 . Alternatively, after the user has registered with UAC  36 , receiver  24  may receive information that allows it to generate one of the key-shares from ticket  66  itself. CAC  38  (which acts as a sort of on-line smart card, but without knowledge of the control word) verifies that the content access is valid and, if so, uses its secret-share to generate the second key-share. The content access requests sent from receiver  24  to CAC  38  and/or CAC  39  may contain the serial number of the VT, which the CAC checks and then invalidates after use to prevent re-use and clones. 
         [0047]    CAC  38  and CAC  39  typically transmit their respective key-shares to receiver  24  in encrypted form. Receiver  24  decrypts and combines the key-shares in order to generate the required key (CW) from the two key-shares. The receiver then applies this CW in decrypting the content from repository  34 . 
         [0048]    In this system configuration, neither one of the content access centers alone nor the CB can itself produce the CW and access the content. Given this compartmentalization, there is no need for heavy operational security constraints to be imposed on any of these entities. There is also no need to maintain large databases of keys, since the key-share derivation is based on running a key-share generation function over the data in each ticket. 
         [0049]      FIG. 4  is a block diagram that schematically illustrates a scheme  70  for key generation that is used in system  20 , in accordance with an embodiment of the present invention. Although the scheme illustrated in  FIG. 3  uses only two secret-shares and two corresponding key-shares, the principles of the scheme are generalized in  FIG. 4  to including n secret-shares and key-shares. The upper row of blocks in the figure represents actions carried out by CP  32  in generating secret-shares and keys, while the remainder of the figure refers to actions of the secret-share holders. 
         [0050]    CP  32  applies a secret-decomposition function (S-DF)  74  to a meta-secret (MS)  72  in order to generate multiple sets  76  of secret-shares S ij . The meta-secret and secret-shares may have the form of sequences of matrices, as described in detail in the Appendix. Alternatively, other equivalent forms may be used. In the example shown in  FIG. 4 , there are m sets  76  with n secret-shares in each set. (Each secret-share S ij  can be decomposed in an equivalent manner into its own equivalent subset of secret-shares, as explained further in the Appendix.) 
         [0051]    Each secret-share in a given set is typically held by a different secret-holder. All of sets  76  are equivalent, in that any of these sets can be used, together with the appropriate unique key identifier (U k )  78 , to generate a key (AK k )  82 . The same sets  76  can be reused indefinitely to generate different keys based on different key identifiers. 
         [0052]    To generate the content access key AK k  for the content item identified by U k  (for encryption of a given content item, for example), CP  32  applies a meta-secret-based key-generation function (KGF-MS)  80  to MS  72 , using identifier (U k )  78 . Each secret-share holder derives its key-share for a given key using a different function: Each secret-share S ij  is used in a specific key-share generation function (KSGF-S ij )  84  together with U k  to generate a respective key-share (ks ijk ). (In this notation, the index i refers to the set of secret-shares, j to the secret-holder, and k to the key itself.) A combiner  86  mathematically combines the key-shares in a prescribed way to generate AK k . Details of the key generation process are described in the Appendix. In the scenario shown in  FIG. 3 , key-share generation functions (KSGF-S ij )  84  are typically carried out by CAC  38  and CAC 2   39 , while combiner  86  is implemented in receiver  24 , as a function of smart card  28 , for example. 
       Joint Key Derivation and Pairing of Decryption Devices Using Secret-Shares 
       [0053]      FIG. 5  is a block diagram that schematically illustrates a scheme  88  for key generation that may be used in receiver  24 , in accordance with an embodiment of the present invention. This method uses pairing between receiver  24  and smart card  28 , wherein one secret-share in each set  76  (S i1 ) is stored and applied by processor  52  in generating a first key-share, and the other secret-share (S i2 ) is stored and applied by host processor  56  to generate a second key-share. Host processor  56  combines the key-shares to generate key  82 . This approach is advantageous, as noted above, in preventing users from sharing smart cards among different receivers and from distributing the key-share generated by one smart card to other (non-paired) receivers. In addition, hacking receiver  24  or smart card  28  for its key share or secret share will not by itself permit theft of the control words. 
         [0054]    The underlying principles of scheme  88  are similar to those of scheme  70 , as described above, and generation of sets  76  of secret-shares and of key  82  from meta-secret  72  may be carried out in an identical fashion. Each set  76  of secret-shares is typically installed in a different receiver, labeled “HOME- 1 ” to “HOME-m” in  FIG. 5  to refer to the different subscriber premises in which the receivers are used. 
         [0055]    When the user of receiver  24  selects an item of content, the corresponding key identifier U k  may be transmitted to the receiver over network  22 , possibly in encrypted form, for example in an ECM  90 . Processor  52  in smart card  28  decrypts the ECM (if encrypted) and then uses the key identifier together with the secret-share S i1  in a key-share generation function (KSGF-S i1 )  92  to generate the key-share ks i1k . The smart card passes this key share together with the key identifier U k  to host processor  56 . For enhanced security, the key identifier and/or the key-share of smart card  28  may be passed to the host processor in encrypted form. Host processor  56  applies the key identifier U k  in its own key-share generation function (KSGF-S i2 )  94  to generate the second key-share ks i2k . It then combines the two key-shares to generate key  82  and uses this key as the control word for decrypting the content item. 
         [0056]      FIG. 6  is a block diagram that schematically illustrates a scheme  100  for key generation in a subscriber premises, in accordance with another embodiment of the present invention. This method uses pairing between two host devices, referred to as a master host  108  and a slave host  102 , which may have respective smart cards  106  and  104 . For example, hosts  102  and  108  may be two separate set-top boxes, personal computers, or entertainment consoles, or a combination of such devices, which are connected to communicate with one another over a local (wired or wireless) network in the subscriber premises or even over the Internet. When each host has a smart card, each of smart cards  104  and  106  stores one of the two secret-shares in the set  76  that is assigned to the subscriber. 
         [0057]    When the subscriber selects an item of content, both of smart cards  104  and  106  receive the key identifier U k , which is typically encrypted and transmitted to hosts  102  and  108  in ECM  90 . Smart card  104  in slave host  102  decrypts the ECM and then uses the key identifier together with the secret-share S i1  in the key-share generation function KSGF-S i1  to generate the key-share ks i1k , which it passes to master host  108 . Smart card  106  applies the second key-share generation function KSGF-S i2  to generate the second key-share ks i2k , which it then combines with ks i1k  to generate key  82 . Master host  108  uses this key as the control word for decrypting the content item. 
         [0058]    It will be appreciated that the embodiments described above are cited by way of example, and that the present invention is not limited to what has been particularly shown and described hereinabove. Rather, the scope of the present invention includes both combinations and subcombinations of the various features described hereinabove, as well as variations and modifications thereof which would occur to persons skilled in the art upon reading the foregoing description and which are not disclosed in the prior art. 
       APPENDIX 
     Computation of Secret-Shares and Keys 
       [0059]    Meta-Secret, MS 
         [0060]    A number N is known to everyone, wherein N=P·Q. P and Q are the two secret primes that factor N. Factoring the large N to its primes is widely accepted as a hard mathematical problem and thus is used here and in other cryptographic schemes. 
         [0061]    The meta-secret MS in the derivation below consists of a sequence of L 2×2 matrices C 1 , . . . , C L  whose entries are in Z N  (residues modulo N). The matrices {C i } commute, i.e., C i ·C j =C j ·C i . The use of 2×2 matrices is computationally convenient, but the principles of the present method can be extended in a straightforward manner to matrices of any desired size (such as 3×3). 
         [0062]    Secret Decomposition Function, S-DF 
         [0063]    MS can be decomposed into secret shares that serve specific (useful) purposes, and as such possess certain properties. In fact, many sets of secret-shares can be derived from MS. 
         [0064]    We define the i th  set of secret shares as: {S i,1 ,S i,2 , . . . , S i,j , . . . , S i,n }; other sets are given as i=1, . . . , m. The secret-shares of the i th  set are defined as below: 
         [0000]    
       
         
           
             
               S 
               
                 i 
                 , 
                 1 
               
             
             = 
             
               { 
               
                 
                   A 
                   
                     i 
                     , 
                     1 
                     , 
                     1 
                   
                 
                 , 
                 
                   A 
                   
                     i 
                     , 
                     1 
                     , 
                     2 
                   
                 
                 , 
                 
                   … 
                    
                   
                       
                   
                    
                   
                     A 
                     
                       i 
                       , 
                       1 
                       , 
                       L 
                     
                   
                 
               
               } 
             
           
         
       
       
         
           
             
               S 
               
                 i 
                 , 
                 2 
               
             
             = 
             
               { 
               
                 
                   A 
                   
                     i 
                     , 
                     2 
                     , 
                     1 
                   
                 
                 , 
                 
                   A 
                   
                     i 
                     , 
                     2 
                     , 
                     2 
                   
                 
                 , 
                 
                   … 
                    
                   
                       
                   
                    
                   
                     A 
                     
                       i 
                       , 
                       2 
                       , 
                       L 
                     
                   
                 
               
               } 
             
           
         
       
       
         
           … 
         
       
       
         
           
             
               S 
               
                 i 
                 , 
                 j 
               
             
             = 
             
               { 
               
                 
                   A 
                   
                     i 
                     , 
                     j 
                     , 
                     1 
                   
                 
                 , 
                 
                   A 
                   
                     i 
                     , 
                     j 
                     , 
                     2 
                   
                 
                 , 
                 
                   … 
                    
                   
                       
                   
                    
                   
                     A 
                     
                       i 
                       , 
                       j 
                       , 
                       L 
                     
                   
                 
               
               } 
             
           
         
       
       
         
           … 
         
       
       
         
           
             
               
                 S 
                 
                   i 
                   , 
                   n 
                 
               
               = 
               
                 { 
                 
                   
                     A 
                     
                       i 
                       , 
                       n 
                       , 
                       1 
                     
                   
                   , 
                   
                     A 
                     
                       i 
                       , 
                       n 
                       , 
                       2 
                     
                   
                   , 
                   
                     … 
                      
                     
                         
                     
                      
                     
                       A 
                       
                         i 
                         , 
                         n 
                         , 
                         L 
                       
                     
                   
                 
                 } 
               
             
             , 
           
         
       
     
         [0000]    Here Ai,j,k is a 2×2 matrix with entries in Z N , and all pairs of the matrices in S i,j  commute. By varying i=1, . . . , m, we get secret-shares belonging to other sets. 
         [0065]    Let A         B denote the tensor product of matrices A,B, χ(A) be the characteristic polynomial of matrix A, and f(x)|g(x) indicate that the polynomial f divides the polynomial g. The matrices A i,j,k  are chosen in a way that satisfies, for i=1, . . . , m: 
         [0000]    
       
         
           
             
               χ 
                
               
                 ( 
                 
                   C 
                   1 
                 
                 ) 
               
             
             | 
             
               χ 
                
               
                 ( 
                 
                   
                     A 
                     
                       i 
                       , 
                       1 
                       , 
                       1 
                     
                   
                   ⊗ 
                   
                     A 
                     
                       i 
                       , 
                       2 
                       , 
                       1 
                     
                   
                   ⊗ 
                   … 
                   ⊗ 
                   
                     A 
                     
                       i 
                       , 
                       n 
                       , 
                       1 
                     
                   
                 
                 ) 
               
             
           
         
       
       
         
           … 
         
       
       
         
           
             
               χ 
                
               
                 ( 
                 
                   C 
                   k 
                 
                 ) 
               
             
             | 
             
               χ 
                
               
                 ( 
                 
                   
                     A 
                     
                       i 
                       , 
                       1 
                       , 
                       k 
                     
                   
                   ⊗ 
                   
                     A 
                     
                       i 
                       , 
                       2 
                       , 
                       k 
                     
                   
                   ⊗ 
                   … 
                   ⊗ 
                   
                     A 
                     
                       i 
                       , 
                       n 
                       , 
                       k 
                     
                   
                 
                 ) 
               
             
           
         
       
       
         
           … 
         
       
       
         
           
             
               χ 
                
               
                 ( 
                 
                   C 
                   L 
                 
                 ) 
               
             
             | 
             
               χ 
                
               
                 ( 
                 
                   
                     A 
                     
                       i 
                       , 
                       1 
                       , 
                       L 
                     
                   
                   ⊗ 
                   
                     A 
                     
                       i 
                       , 
                       2 
                       , 
                       L 
                     
                   
                   ⊗ 
                   … 
                   ⊗ 
                   
                     A 
                     
                       
                         i 
                          
                         
                             
                         
                          
                         n 
                       
                       , 
                       L 
                     
                   
                 
                 ) 
               
             
           
         
       
     
         [0066]    Construction of a Set of Secret-Shares 
         [0067]    Generation of the i th  set of secret-shares S i,1 ,S i,2 , . . . , S i,n  (i=1,m) from C 1 , . . . , C L  is carried as follows: 
         [0068]    We randomly select L·(n−1) 2×2 matrices with non-zero determinants that commute with C 1 , . . . , C L , and are denoted as: 
         [0069]    A′ i,1,1, ,A′ i,1,2 , . . . A′ i,1,L ,
       A′ i,2,1 ,A′ i,2,2 , . . . A′ i,2,L , . . . , A′ i,n−1,2 , . . . A′ i,n−1,L          
 
         [0071]    We define the remaining matrices A′ i,n,1 ,A′ i,n,2 , . . . A′ i,n,L  as follows: 
         [0000]        A′   i,n,k   =C   k ·( A′   i,1,k   ·A′   i,2,k   ·. . .·A′   i,n−1,k ) −1  for k=1,  . . . , L.  
 
         [0072]    Definition of A i,j,r    
         [0073]    For 1≦i≦m and 1≦j≦n we select a random invertible matrix T i,j  and define A i,j,r =T i,j ·A′ i,j,r ·T i,j   −1 . Thus the i th  set of secret-shares S i,1 ,S i,2 , . . . , S i,j , . . . , S i,n  is given by: S i,j ={A i,j,1 ,A i,j,2 , . . . A i,j,L .}, for j=1, . . . , n. 
         [0074]    Calculation of the kth Asset Key, AK k    
         [0075]    There are two ways to generate AK k : 
         [0076]    a.) using MS, or 
         [0077]    b.) using any set of secret-shares. 
         [0000]    The parameter k identifies the key. 
         [0078]    MS Creation of AK k  (KGF-MS) 
         [0079]    The creator of AK k  is the possessor of the meta-secret MS. We transform k into a sequence of L bits (using a hash function) k→(b k,1 ,b k,2 , . . . , b L ). The key AK k  is defined as follows: AK k =tr(Π 1=1   L C i   b     k,i   ), wherein C i   b     k,i   =C i  for b k,i =1 and C i   b     k,i   =I for b k,i =0. 
         [0080]    (Note : for a 2×2 matrix X, tr(X)=X 1,1 +X 2,2 .) 
         [0081]    From Set of Secret-Shares to AK k  (KSGF-S i,j    
         [0082]    Given the i th  set of secret-shares S i,1 ,S i,2 , . . . , S i,n  (wherein S i,j ={A i,j,1 ,A i,j,2 , . . . A i,j,L }), we calculate AK k  as follows : 
         [0083]    The j th  secret holder (j=1, n) calculates the matrix B k,j =Π r=1   L A i,j,r   b     k,j    and defines the values t k,j =tr(B k,j ) and d k,j =det(B k,j ). 
         [0084]    The combiner gets the pairs (t k,j ,d k,j ) for all 1≦j≦n and calculates a polynomial P k,n (x) of degree 2 n  defined by the following recursive process: 
         [0085]    D k,1  is the 2×2 matrix 
         [0000]    
       
         
           
               
             
               ( 
               
                 
                   
                     0 
                   
                   
                     1 
                   
                 
                 
                   
                     
                       - 
                       
                         d 
                         
                           k 
                           , 
                           1 
                         
                       
                     
                   
                   
                     
                       t 
                       
                         k 
                         , 
                         1 
                       
                     
                   
                 
               
               ) 
             
           
         
       
     
         [0086]    Let D k,j  be a matrix of dimension 2 j−1 ×2 j−1  generated in the recursive process for 1≦j≦n−1. 
         [0087]    We define the matrix D k,n  as follows: 
         [0000]    
       
         
           
             
               D 
               
                 k 
                 , 
                 n 
               
             
             = 
             
               
                 D 
                 
                   k 
                   , 
                   
                     n 
                     - 
                     1 
                   
                 
               
               ⊗ 
               
                 
                   ( 
                   
                     
                       
                         0 
                       
                       
                         1 
                       
                     
                     
                       
                         
                           - 
                           
                             d 
                             
                               k 
                               , 
                               n 
                             
                           
                         
                       
                       
                         
                           t 
                           
                             k 
                             , 
                             n 
                           
                         
                       
                     
                   
                   ) 
                 
                 . 
               
             
           
         
       
     
         [0088]    D k,n  is a 2 n ×2 n  matrix of the form 
         [0000]    
       
         
           
             
               ( 
               
                 
                   
                     
                       0 
                       
                         
                           2 
                           
                             n 
                             - 
                             1 
                           
                         
                         × 
                         
                           2 
                           
                             n 
                             - 
                             1 
                           
                         
                       
                     
                   
                   
                     
                       D 
                       
                         k 
                         , 
                         
                           n 
                           - 
                           1 
                         
                       
                     
                   
                 
                 
                   
                     
                       
                         - 
                         
                           d 
                           
                             k 
                             , 
                             n 
                           
                         
                       
                       · 
                       
                         D 
                         
                           k 
                           , 
                           
                             n 
                             - 
                             1 
                           
                         
                       
                     
                   
                   
                     
                       
                         t 
                         
                           k 
                           , 
                           n 
                         
                       
                       · 
                       
                         D 
                         
                           k 
                           , 
                           
                             n 
                             - 
                             1 
                           
                         
                       
                     
                   
                 
               
               ) 
             
             . 
           
         
       
     
         [0089]    The polynomial P k,n (x) is defined as the characteristic polynomial of the matrix D k,n . 
         [0090]    The polynomial P k,n (x) contains the information needed to generate AK k ; we present two methods to calculate AK k  from P k,n (x): 
         [0091]    is the matrix 
         [0092]    First method: A center that knows MS sends the following couple: (k,q k (x)). In this expression, the polynomial q k (x) is a third-degree polynomial calculated as follows: Let h k (x) be the second-degree characteristic polynomial of the matrix Π i=1   n C i   b     k,i   . The coefficient of x in h k (x) is −AK k . We select a random element α and define q k (x)=(x−α)·h k (x). 
         [0093]    The combiner calculates gcd(q k (x), P k (x)). The greatest common denominator of these polynomials is equal to h k (x), and AK k  can be extracted from the coefficient of x. 
         [0094]    Second method (without the center): Every one of the secret holders has two sets of secrets, for example, the jth secret holder has S i,j  and S i′,j . The combiner calculates the two polynomials P k (x) and P′ k (x), using the matrices in S i,j  and S i′,j  respectively. Then the combiner calculates the second-degree polynomial gcd(P′ k (x),P k (x)), which is equal to h k (x). The value AK k  is obtained from the coefficient of x. 
         [0095]    It is possible to show that calculation of AK k  for a new k is hard problem even when the values of AK k     1   ,AK k     2   , . . . AK k     m    are given for arbitrary values k 1 ,k 2 , . . . k m . 
         [0096]    Decomposition of Secret-Shares 
         [0097]    Any secret share S (derived from MS) can be decomposed in the same way as was MS to generate one or more subsidiary sets of secret shares, wherein each of the sets is equivalent to S in producing keys. A tree of equivalent secret-shares set for a given secret-share can be constructed in this manner to arbitrary depth. 
         [0098]    For example, consider three generals (secret holders  1 , 2  and  3 ) with secret-shares S 1 , S 2  and S 3 , respectively, derived from MS, such that all three of them are needed to produce the key for a missile site. Assume general 1 is a traveling man and often not available to partake in the key generation ceremony. His secret share S 1  can be decomposed into two set of three secret shares: 
         [0099]    S 11 , S 12  and S 13    
         [0100]    S′ 11 , S′ 12  and S′ 13    
         [0000]    which are given to three of his trusted colonels, respectively. Each colonel gets two secret shares, one from each set: 
         [0101]    colonel 1  gets S 11 , S′ 11 ; 
         [0102]    colonel 2  gets S 12 , S′ 12 , 
         [0103]    colonel 3  gets S 12 , S′ 12 , 
         [0104]    If general  1  is unavailable to produce his key-share, then the three colonels&#39; secret-shares are a replacement for the general in the sense that the colonels can jointly generate the general&#39;s key-share. 
         [0105]    The above process follows exactly the methodology and complexity of the MS decomposition and key-share generation functions that were described above. Alternatively one could use only a single secret-share per colonel, but then the overall complexity (e.g., matrix size) of the method will be increased.