ALGORITHMS

TECHNICAL FIELD

The present invention relates generally to cryptography, and in particular to a traitor tracing scheme.

BACKGROUND

This section is intended to introduce the reader to various aspects of art, which may be related to various aspects of the present invention that are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present invention. Accordingly, it should be understood that these statements are to be read in this light, and not as admissions of prior art. Premium content is usually encrypted so as to control its distribution.

In content distribution systems, authorized users are given a hardware or software decoder containing a decryption key that allows them to get access to the content in the clear.

However, less honest users may collude and try to produce a pirate decoder; i.e. a non-registered decoder able to decrypt. Traitor tracing schemes enable an authority to recover the identity of at least one of the legitimate users who participated in the construction of a pirate decoder. Such a user is called a traitor. The aim of traitor tracing schemes is to deter users to build pirate decoders. Ciphertext expansion is used as a metric to measure the "quality" of a traitor tracing scheme. In that sense, an optimal traitor scheme could be obtained under the assumption of tamper resistance. If the data stored in the decoder (including the cryptographic keys) are protected against unauthorized access, there is no need to add tracing capabilities. Tamper resistance rules out colluding attacks. So, further assuming that decoders cannot be cloned, the same decryption key could be used in all decoders. The size of the ciphertexts would therefore be constant, regardless of the number of users in the system. A possible implementation is to rely on smart cards: they are tamper-resistant and unclonable. However, such a system also requires that the decryption algorithm in the smart card is properly implemented. In particular, the implementation should not leak information about the decryption key. Examples of implementation attacks include side- channel attacks and fault attacks that are both well known to the person skilled in the art. Software-based solutions offer a number of advantages. They are cheaper and easier to distribute and to update (for example if a security flaw is identified). Software tamper resistance can be achieved through a combination of well-known obfuscation techniques and cryptographic hashing. Cryptographic hashing checks the integrity as the program is running while obfuscation makes it harder to realize intended changes in functionality (and in particular to bypass the integrity checks). Unclonability is difficult to achieve without resorting to hardware. The present application does not solve the unclonability problem, but intends to deter users from distributing copies of their [software] decoder. A possible approach is to embed copy-specific watermarks in the code [see Christian S. Collberg and Clark Thomborson. Watermarking, tamper-proofing, and obfuscation— Tools for software protection. IEEE Transactions on Software Engineering, 28(8):735-746, 2002]. This enables tracking illegal copies. A concrete implementation, nicely combining with integrity checking techniques, is presented in Bill G. Home, Lesley R. Matheson, Casey Sheehan, and Robert Endre Tarjan. Dynamic self-checking techniques for improved tamper resistance. In T. Sander, editor, Security and Privacy in Digital Rights Management (ACM-DRM 2001), volume 2320 of Lecture Notes in Computer Science, pages 141-159, Springer, 2002. It may however be interesting to provide a solution that does not require verification of watermarks to detect unauthorized copies of a decryption application. The present invention provides such a solution.

SUMMARY OF INVENTION

In a first aspect, the invention is directed to a method for decrypting a digital ciphertext c of a plaintext message m, the ciphertext c having been encrypted with an encryption key that corresponds to a decryption key d. A device executing a computer program using at least a partial key ofo related to an identifying value aiD by a relation R such that cfo) = d, the identifying value 0 _\ D being derived from an identifier ID through a derivation function /, receives the digital ciphertext c; decrypts the digital ciphertext c to obtain plaintext message m using the computer program taking as further input the identifying value 0\D, ^' and outputs the plaintext message m. An entity knowing the derivation function / is able to trace the user identifier ID by observing whether the computer program correctly decrypts ciphertext c

In a first preferred embodiment, the relation R is given by one of the following: a multiplicative splitting, an additive splitting, a Euclidean splitting.

In a second preferred embodiment, the relation R is private.

In a third preferred embodiment, the derivation function / is one of the following: an identity map, a cryptographic hash function, an authentication function, a symmetric encryption function.

In a fourth preferred embodiment, the digital ciphertext has been encrypted using a public-key encryption scheme.

It is advantageous that the public encryption scheme is an RSA cryptosystem with public modulus N, public exponent e, and private exponent d matching e through the relation ed = 1 (mod λ(Λ/)), where λ denotes Carmichael's function; in particular (mod λ(Λ/)), or c/iD = ( ⁽²⁾ ), with c/| _D ^{(1 )} = and c/| _D ⁽²⁾ = c/ mod σ, ₀ . It is alternatively advantageous that the public encryption scheme is a generalized EIGamal cryptosystem in a group of order q; in particula (mod q) or c/| _D = (c/| _D ^{(1 )} , c/| _D ⁽²⁾ ), with c/| _D ^{(1 )} = and d mod Q It is alternatively advantageous that the public encryption scheme is a

Cramer-Shoup cryptosystem in a group of order g; in particular

(mod q = (c/| _D ^{(1 )} , c/| _D ⁽²⁾ ), with c/| _D ^{(1 )} = and In a second aspect, the invention is directed to a device for decrypting a digital ciphertext c of a plaintext message m, the ciphertext c having been encrypted with an encryption key that corresponds to a decryption key d. The device comprises an interface for receiving the digital ciphertext c, and outputting the plaintext message m; and a processor for executing a computer program using at least a related to an identifying value aiD by a relation R such that the identifying value aiD being derived from an identifier ID through a derivation function, the computer program decrypting the digital ciphertext c to obtain plaintext message m taking as further input the identifying value 0\D- An entity knowing the derivation function f is able to trace the user identifier ID by observing whether the computer program correctly decrypts ciphertext c when 0\D = f(\D).

In a third aspect, the invention is directed to a computer program product storing instructions that, when executed by a processor, perform the method of the first aspect. In a fourth aspect, the invention is directed to a method for signing a digital plaintext m to produce signature s using a signing key d that corresponds to a signature verification key. A device executing a computer program using at least a partial key ofo related to an identifying value 0\D by a relation R such that cfo) = d, the identifying value aiD being derived from an identifier ID through a derivation function /, receives the digital plaintext m, signs the digital plaintext m to obtain signature s using the computer program taking as further input the identifying value aiD, and outputs the signature s. An entity knowing the derivation function / is able to trace the identifier ID by observing whether the computer program correctly verifies, using the signature verification key, the signature s when 0\D = (ID).

In a fifth aspect, the invention is directed to a device for signing a digital plaintext m to produce signature s using a signing key d that corresponds to a signature verification key. The device comprises an interface for receiving the digital plaintext m; and outputting the signature s; and a processor adapted to execute a computer program using at least a partial key ofo related to an identifying value 0\D by a relation R such that being derived from an identifier ID through a derivation function, the computer program signing the digital plaintext m to obtain signature s using the computer program taking as further input the identifying value 0\D- An entity knowing the derivation function / is able to trace the identifier ID by observing whether the computer program correctly verifies, using the signature verification key, the signature s

BRIEF DESCRIPTION OF DRAWINGS

Preferred features of the present invention will now be described, by way of non-limiting example, with reference to the accompanying drawings, in which

Figure 1 illustrates classical RSA decryption;

Figure 2 illustrates a traitor tracing decryption algorithm according to a preferred embodiment of the present invention; Figure 3 illustrates a RSA decryption algorithm according to a first variant embodiment of the present invention;

Figure 4 illustrates a RSA decryption algorithm according to a second variant embodiment of the present invention;

Figure 5 illustrates a RSA decryption algorithm according to a third variant embodiment of the present invention;

Figure 6 illustrates an EIGamal decryption algorithm according to a fourth variant embodiment of the present invention;

Figure 7 illustrates a Cramer-Shoup decryption algorithm according to a fifth variant embodiment of the present invention; and

Figure 8 illustrates an apparatus according to a preferred embodiment of the present invention.

DESCRIPTION OF EMBODIMENTS

When compared to the solution provided by Home et al., the approach described in the present application is different, complementary. It is required that each decoder has a different private key while being compatible with any encryption algorithm. A main inventive idea is to add an extra entry, specific to the instance of the algorithm, to the decryption algorithm so that this extra entry together with the private key embedded in the software decoder enables decryption of ciphertexts. In its most basic version, the decryption key (known to some authority) is split into two shares. Each registered user receives from the authority a first private share and a software decoder embedding the second share. Upon reception of a ciphertext and a private share, the decoder first recovers the entire decryption key from the two shares (i.e., the input share and the embedded share) and next uses it to decrypt the ciphertext and obtain the content in clear. In more advanced versions, it is not necessary to explicitly recompute the decryption key. Advantageously, the approach described herein can allow for flexible traitor tracing, in a black-box fashion, meaning that there is no need to "open"' the software decoder as tracing can be achieved by observing the output of the software decoder from known inputs. Secret splitting

Before going into further details, several key splitting techniques will be described. Secret splitting or secret sharing is a cryptographic technique to split a secret key in (at least) two components. See e.g. George R. Blakley. Safeguarding Cryptographic Keys. In Proceedings of the National Computer Conference, volume 48 of AFIPS Conference Proceedings, pages 313-317, 1979 and Adi Shamir. How to Share a Secret. Communications of the ACM, 22(1 1 ):612-613, 1979. Learning one of the components does not reveal half of the secret; if well implemented it actually reveals no information at all. A simple way to split a / -bit key K in two shares is to choose uniformly at random Κι ε {0,1 }^ and to define K ₂ = K 0 Ki . It is easily verified that knowledge of Ki (or K ₂ ) yields no information about K. The two shares are needed to reassemble secret key K.

For RSA [see notably Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21 (2):120-126, 1978], or more generally for most public-key cryptosystems, the underlying algebraic structure can be exploited to derive further key splitting schemes with different properties. For concreteness, consider an RSA modulus N = pq where p and q are two large equal-size primes. The public primitive consists in raising some x ε Έ _Ν to the e-th power modulo N and the corresponding private primitive consists in raising some y ε Έ _Ν to the d-th power. Public exponent e is coprime to K(N) and matches private exponent d through the relation ed ≡ 1 (mod λ(Λ/)), where λ denotes Carmichael function. By construction, if y = x ⁶ mod N then x can be recovered as mod N:

≡ (x ^e ) ^d ≡ ) ^{d mod} ≡ x (mod N).

Multiplicative splitting

The multiplicative splitting breaks down private exponent d into two components (d^, cfc) where

· and

• cfc is computed as dld^ mod K(N). Private exponentiation, mod N, can then be evaluated as (y^ ² mod N.

The multiplicative splitting was introduced by Colin Boyd (in Digital Multisignatures. In H. J. Beker and F. C. Piper, editors, Cryptography and Coding, pages 241-246. Oxford University Press, 1987) as a means to produce digital multisignatures. Each party receives a share d, (/ ^' ε {1 ,2}), which is then used to create a joint signature.

Additive splitting

The additive splitting, also used by Boyd as an alternative to produce multisignatures, is a variant where private exponent d is split additively into two shares (d^, cfc) where

• {0}; and

• d ₂ = d - d mod K{N).

Private exponentiation, mod N, can then be evaluated as y ^d1 - y^ ² mod N.

With the multiplicative splitting, the two half exponentiations are performed in a serial way. In contrast, the additive splitting prescribes parallel operation. This was used to design a variant of RSA, known as mediated RSA (mRSA) [Dan Boneh, Xuhua Ding, Gene Tsudik, and Chi Ming Wong. A Method for Fast Revocation of Public Key Certificates and Security Capabilities. In Proceedings of the 10th USENIX Security Symposium, pages 297-308. USENIX Association, 2001 .], providing immediate revocation capabilities. mRSA involves an on-line semi-trusted entity, called SEM, that issues message-specific tokens. The SEM is given key share while the user receives the second share, cfc- If the user wants to sign or to decrypt a "message" y, she must first obtain the token ^ ¹ mod N. To revoke the user's ability to sign or decrypt messages, the SEM simply stops issuing tokens. A multiplicative version of mRSA is presented in Ravi Ganesan. Yaksha: Augmenting Kerberos with public-key cryptography. In Proceedings of the 1995 Symposium on Network and Distributed System Security, pages 132— 143. Internet Society, 1995.

Euclidean splitting

Key splitting techniques also find applications in the development of countermeasures against certain implementation attacks. The Euclidean splitting [Mathieu Ciet and Marc Joye. (Virtually) Free Randomization Techniques for Elliptic Curve Cryptography. In S. Qing, D. Gollmann, and J. Zhou, editors, Information and Communications Security (ICICS 2003), volume 2836 of Lecture Notes in Computer Science, pages 348-359. Springer, 2003.] splits private exponent d into two components (c/i, d ₂ ) where

• d _\ is a random element in {0, 1 } ^K , d _\ ≠ 0, for some parameter κ; and

• d ₂ = (d2,h, cfc,/) is computed as ofc,/, = [d/d^\ and d ₂ = d mod d^ .

Remarking that d = dvd ₂ ,h+d ₂ , the private exponentiation can be evaluated as

(y ^d i) ^d 2,h■ yd ₂ ,i _moc J jv.

The advantage of the Euclidean splitting is computational. If parameter K is set to \d\ ₂ 2 « \N\ ₂ 2 (i.e., half the bit length of N), then the entity holding d ₂ has to perform a double exponentiation of the form z ^d2 > ^h - y ^d u (mod N), where exponents d ₂ ,h and d ₂ are half-sized. Since the cost of a double exponentiation is only slightly more expensive than a single exponentiation using Straus' method [Ernst Gabor Straus. Addition chains of vectors (problem 5125). The American Mathematical Monthly, 71 (7):806-808, 1964] (a.k.a. Shamir's trick; see [Taher EIGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 31 (4):469-472, 1985.]), the overall computation is roughly twice faster.

More generally, it is noticed that Euclidean splitting can be applied directly to d or to an equivalent representation thereof like d + kX(N) for some integer k. RSA Traitor tracing schemes

As already mentioned, one aim of the present invention is to deter users from distributing decryption software received from content providers. To this end, each user receives a personalized decryption software containing a unique decryption key. Yet a same encrypted content can be decrypted using any personalized decryption software. A key property of the provided schemes is that it is possible to identify an instance of a personalized decryption software. In other words, it is possible to trace a given implementation or a copy thereof. Properly implemented decryption algorithms make use of state-of-the- art obfuscation and tamper-resistant techniques. The present RSA traitor tracing schemes rely only on software and do not require secure hardware.

Basic scheme

Imagine that a same digital content is to be sent to a large number of subscribers. The content are encrypted using RSA with public key (N, e) and private key d. Specifically, using the RSA cryptosystem, a binary string m is encrypted as c = μ(τηψ mod N for some (probabilistic) padding function μ (e.g., Optimal Asymmetric Encryption Padding, OAEP). Then, as illustrated in Figure 1 , given ciphertext c, m is recovered from c ^d mod N using private key d; an indicator J- is returned in case decryption fails. A classical solution is to provide each legitimate user with a protected software implementation of the decryption box. Moreover, to prevent illegal re-distribution, implementations are equipped with copy-specific watermarks for tracing purposes.

The approach of the present invention, illustrated in Figure 2, is complementary to the prior art solution. It is proposed to split the decryption key into two components. The first component, aiD, is derived from a unique identifier ID. The second component, c/| _D , is defined so that the value of decryption key d can be recovered from the pair (aiD, ofo); R denotes the combining function that on input aiD, and ofo returns d. Component c/| _D is embedded in a protected software implementation while component 0\D serves as an additional input to the decryption software. In more detail, the scheme goes as follows. In the initialization phase, a content provider sets up an RSA modulus N and a pair of encryption/decryption keys (e, d). When a user wants to subscribe to the system, she produces unique identifier ID (e.g., email address, bank account number, password, ...) for the system. The user then receives her personal string 0\D together with a protected software implementation (decoder) which embeds the matching secret value ofo. When a registered user wishes to access to an encrypted content c, she enters her string 0\D in her decoder which decrypts c in two steps as:

2. compute c ^d mod N;

where the last operation recovers and returns the plain content m or returns -L in case the decryption failed.

Selecting am

Without loss of generality, it is assumed that the unique identifier ID of a user is a binary string. There are several possibilities to derive the identifying value 0\D from the unique identifier ID. Writing 0\D = (ID), and requiring that the function / : {0, 1 }*→ {0, 1 }' is collision-resistant, there are several possible choices for function /, such as for example:

· the identity map (the string ID is seen as an integer);

• a cryptographic hash function (e.g. SHA-1 , SHA-2 family...);

• a [deterministic] authentication function (e.g. HMAC, RSA-FDH ...); or

• a [deterministic] symmetric encryption function (e.g. AES, Serpent...).

Defining c/m

The value of ofo is defined from the string 0\D and the decryption key d.

Again, there are plenty of choices. For example, viewing d as a binary string, it is possible to define ofo = σ _!0 Θ d (and thus cfo) = σ _!0 Θ ofo). As will be shown hereinafter, the way ofo is constructed may simplify the implementation. Tracing traitors Tracing a traitor is now pretty easy. Suppose that a legitimate user (corresponding to identifier ID) is allegedly suspected to have made available illegal copies of her software decoder. When such a copy is found, it can be tested, in a black-box fashion, whether it corresponds to ID as follows:

· obtain a valid ciphertext c;

• compute σ _Ό = f(ID) (where ID is the identifier of the putative traitor) using derivation function f;

• input c and σ _Ό to the pirated copy of the software decoder and check whether c decrypts correctly or not. If the decryption is correct, the user with identifier ID is identified as the source of leakage. Interestingly, the tracing capability requires the knowledge of derivation function f. If function f is public, anyone can test if a given software decoder corresponds to some identifier ID. In contrast, if function f is private (for instance, if it is keyed), traitor tracing is solely possible for "authorized" entities (namely, those knowing f).

Enhanced schemes

Although the prior art scheme is applicable to any cryptosystem, it can be intricate to implement in a secure way. The proposed implementation is different from existing ones. Indeed, in addition to the usual decryption function (i.e., c ^d mod N in the case of RSA), the basic scheme of the present invention first requires reconstruction of d from 0\D and C ID- A possible fix to mitigate possible damages is to keep the combining function R private.

A better approach would be to design a software implementation that solely performs operations similar to the usual decryption function. This allows one to get a protected implementation at minimum cost, augmented with the tracing method of the present invention. More importantly, this allows one to base the security on proven techniques. While this may appear difficult in the general case, it will be seen that for RSA it is not. It is possible to exploit the underlying algebraic structure. The "usual decryption function" for RSA is the modular exponentiation. The goal is, on input (c, O _\ o), to evaluate c ^d (mod N) using a routine that can securely evaluate operations of the form x ^d ' ^D mod N for a fixed value ofo. This is where the key splitting techniques described hereinbefore come into play.

Application of the different splitting techniques lead to the schemes depicted in Figures 3 to 5. Given identifier ID and corresponding identifying value aiD, the value of ofo is respectively defined as:

• multiplicative scheme (Figure 3): ofo = d/a _O (mod K(N));

• additive scheme (Figure 4): d _\ o≡d - σ _Ώ (mod K(N));

•

It may be argued that the enhanced schemes involve modular exponentiations with an exponent other than c/| _D , namely for the computation of Co. It should be noted that aiD is not a public value. Therefore, the value of Co (as well as its computation) does not reveal sensitive information. For the Euclidean variant, we suppose that the double exponentiation in Step 2 is evaluated as an atomic operation based on the Straus-Shamir technique.

Further schemes

Most public-key cryptosystems are based on group theory. Provided the discrete logarithm problem is (presumably) hard, cryptographic schemes can be devised. Examples include multiplicative groups of finite fields or elliptic curves over finite fields.

Consider a (multiplicatively written) cyclic group G = <g> of order q, generated by an element g. The well-known EIGamal cryptosystem can easily be extended to this generalized setting. Let a cryptographic hash function H: G→ M that maps elements of G to elements of message space M. The private key is a random element d ε TL _q and the corresponding public key is y = g ^d . A message m ε M is encrypted as c = (g ^k , m © H f)) where k is uniformly chosen at random in TL _q . Given ciphertext c = (u, v), message m is recovered as v 0 H(u ^d ). The correctness follows by observing that u ^d = (gh ^d = . Remarking that the main operation for the decryption process is an exponentiation in G (i.e. u ^d ), the previously described splitting techniques readily apply here as well. For example, defining c/| _D = mod q, the multiplicative splitting

yields the 'enhanced' scheme illustrated in Figure 6.

The conversion from u to uo is analogous to the proxy re-encryption technique used in Matt Blaze, Gerrit Bleumer, and Martin Strauss. Divertible Protocols and Atomic Proxy Cryptography. In K. Nyberg, editor, Advances in Cryptology - EUROCRYPT'98, volume 1403 of Lecture Notes in Computer Science, pages 127-144. Springer, 1998. Actually, the enhanced schemes of the present invention can be seen as the re-encryption of a ciphertext for the user holding private key ofo, followed by the regular decryption with key ofo.

Another embodiment is an enhanced scheme of Cramer-Shoup cryptosystem (see Ronald Cramer and Victor Shoup. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In H. Krawczyk, editor, Advances in Cryptology - EUROCRYPT'94, volume 1462 of Lecture Notes in Computer Science, pages 13— 25, Springer, 1998), a variant secure against chosen-ciphertext attacks of EIGamal cryptosystem.

The Cramer-Shoup cryptosystem makes use of a universal one-way function {0,1} ^* → TL _q . Let g and h be two random generators of G. The private key is {d, s ₁ , s ₂ , t ₁ , t ₂ } that are elements in TL _q . The public key is {y, y ₁ ,y ₂ } where y = g ^d , y ₁ = g ^{Sl ■} h ^S2 and y ₂ = g* ¹ - h ^t2 . A message m E M is encrypted as c = (u, u', v, w) with u = g ^k , u' = h ^k , v = m @ H(y ^k ), cc = H' (u, u', v) and w = y ₁ ^k y ₂ ^k . Given a ciphertext c = (u, u' , v, w), message m is recovered as v @ H(u ^d ) . The correctness follows by observing _u ^{Sl+ti ■} (u') ^{S2 +t2a} with a = H' (u, u', v) .

Remarking that the main operation for the decryption process is an exponentiation in G (\.e. u ^d ), the previously described splitting techniques readily apply here as well. For example, defining d _m = d - σ _ΙΌ mod q, the additive splitting yields the 'enhanced' scheme illustrated in Figure 7.

Further traitor tracing schemes can be obtained similarly using others splitting techniques or others cryptosystems.

Figure 8 illustrates a decryption device according to a preferred embodiment of the present invention. The device 800 comprises at least one interface unit 810 adapted for communication with other devices (not shown), at least one processor 820 and at least one memory 830 adapted for storing data, such as accumulators and intermediary calculation results. The processor 820 is adapted to perform a decryption according to any of the embodiments of the inventive methods, as previously described herein. It will be appreciated that it is possible to provide two (or possibly more) separate devices that each computes a value; as the invention is directed to software implementations, each of these devices resembles the one described in Figure 8. A computer program product 840 such as a CD-ROM or a DVD comprises stored instructions that, when executed by the processor 820, performs the method according to any of the embodiments of the invention.

It will be appreciated that the general idea of the invention can be applied to other applications than encryption and traitor tracing. An example of such an application is group signature where the present scheme would allow to trace a traitor that has divulgated its signing secret to an Outside' party. In this example, the signing key would be split in the same way as described above. Recovering the secret divulgated by the traitor would then allow to find the identity of the traitor in a similar manner.

Each feature disclosed in the description and (where appropriate) the claims and drawings may be provided independently or in any appropriate combination. Features described as being implemented in hardware may also be implemented in software, and vice versa. Reference numerals appearing in the claims are by way of illustration only and shall have no limiting effect on the scope of the claims.