Method of protecting broadcast data by fingerprinting a common decryption function

• US 6,044,464 A
• Filed: 05/08/1998
• Issued: 03/28/2000
• Est. Priority Date: 05/08/1998
• Status: Expired due to Term

• Current Assignee: Yeda Research and Development Co. Ltd. (Weizmann Institute of Science)
• Original Assignee: Yeda Research and Development Co. Ltd. (Weizmann Institute of Science)
• Inventors: Shamir, Adi
• Primary Examiner(s): Peeso, Thomas R.
• Application Number:
  US09/074,415
• Time in Patent Office: 690 Days
• Field of Search: 380/255, 380/258, 713/170, 713/182, 713/186, 713/201, 713/159, 713/161, 713/172, 713/185
• US Class Current: 713/186
• CPC Class Codes: G06F 21/10 Protecting distributed programs or content, e.g. vending or licensing of copyrighted material protection in video systems or pay television H04N7/16 ; Digital rights management [DRM]
• CPC Class Codes: G06F 21/16 Program or content traceability, e.g. by watermarking
• CPC Class Codes: H04L 2209/601 Broadcast encryption
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying
• CPC Class Codes: H04N 21/6334 for authorisation, e.g. by transmitting a key wireless communications network key management H04W12/04; wireless communications network access security H04W12/08

Abstract

A well-known technique to discourage piracy of digital objects is to fingerprint the version each customer receives. The invention provides a novel way of fingerprinting the decryption functions given by broadcasters to their customers (usually in the form of smart cards). The main difficulty is to ensure that all the algorithms provided by the broadcaster implement the same decryption function, and yet to make it computationally difficult for a pirate who obtains a large number of such implementations to find even one fundamentally different implementation which is not traceable to a particular customer.

Claims

1. A method of fingerprinting a common function in broadcast systems comprising the steps of

(a) determining for each customer a unique function,

(b) arranging the functions to be identical on a subset X of inputs, and different (with high probability) on other inputs, and

(c) broadcasting only inputs in X in order to enable all customers to compute common outputs, whereby to enable pirate cards to be traced to particular customers by analyzing their computations on arguments which are not necessarily in X.

2. The method of claim 1, including the further step of using the common outputs to decrypt encrypted data broadcast to all the customers.

3. The method of claim 1, including the further step of implementing the unique functions in software on a set top box or a personal computer.

4. The method of claim 1, including the further step of implementing the unique functions in a high security microprocessor.

5. The method of claim 1, including the further step of implementing the unique functions in a smart card.

6. The method of claim 1, including the further step of deriving the unique functions by applying a unique hash function to the input and XOR'"'"'ing it with entries from a precomputed unique table.

7. The method of claim 1, including the further steps of selecting the input as a pair of values (i,x_i), and computing the output as f_k (i,x)=h(k,x) XOR t_i where k is a unique key, and t_i is the i-th entry in a unique table T, which is precomputed by the broadcaster as t_i =h(k,x_i) XOR y_i.

8. A method of fingerprinting a common function in broadcast systems comprising the steps of:

(a) establishing for each customer of a broadcaster a unique function and a unique modification table,

(b) broadcasting to each customer a common input,

(c) receiving, by each customer, the common input,

(d) applying, by each customer, to the common input his unique function and modifying the result with entries from his unique modification table,

(e) the results being identical on a subset X of inputs, and different (with high probability) on other inputs, so that

(f) pirate functions are traceable to particular customers by analyzing the unique key and modification table used in their computations.

9. The method of claim 8, including the further step of the broadcaster periodically broadcasting new inputs from X, and using the common outputs as part of an encryption key.

10. The method of claim 8, including the further step of implementing the unique functions and tables in software on a set top box or a personal computer.

11. The method of claim 8, including the further step of implementing the unique functions and tables in a high security microprocessor.

12. The method of claim 8, including the further step of implementing the unique functions and tables in a smart card.

13. The method of claim 8, including the further step of applying a unique hash function to the input and then XOR'"'"'ing with an entry from the unique modification table.

14. The method of claim 8, in which the input is a pair of values (i,x_i), and the output is computed as f_k (i,x)=h(k,x) XOR t_i where k is a unique key, and t_i is the i-th entry in the unique modification table T, which is precomputed by the broadcaster as t_i =h(k,x_i) XOR y_i, where y_i is the common output value.

15. Apparatus for fingerprinting a common function in broadcast systems comprising:

(a) a first controller for establishing for each customer of a broadcaster a unique function and a unique modification table,

(b) a broadcaster for broadcasting to each customer a common input,

(c) a receiver for receiving, by each customer, the common input,

(d) a second controller for applying, by each customer, to the common input his unique function and modifying the result with entries from his unique modification table,

(c) the results being identical on a subset X of inputs, and different (with high probability) on other inputs, so that

(e) pirate functions are traceable to particular customers by analyzing the unique key and modification table used in their computations.

16. The apparatus of claim 15, including a third controller for the broadcaster to periodically broadcast new inputs from X, and to use the common outputs as part of an encryption key.

17. Apparatus for protecting broadcast data by fingerprinting a common decryption function comprising

(a) a controller for determining for each customer a unique function, with the functions arranged to be identical on a subset X of inputs, and different (with high probability) on other inputs, and

(b) a broadcaster to broadcast only inputs in X in order to enable all customers to compute common outputs, whereby to enable pirate cards to be traced to particular customers by analyzing their computations on arguments which are not necessarily in X.

18. The apparatus of claim 17, including a further controller for use by an authorized customer receiving said broadcast to use the common outputs to decrypt encrypted broadcast data.

19. The apparatus of claim 18, wherein the further controller implements the unique functions in one of software on a set top box or a personal computer, a high security microprocessor and a smart card.

20. The apparatus of claim 17, wherein the controller derives the unique functions by applying a unique hash function to the input and XOR'"'"'ing it with entries from a precomputed unique table.

21. The apparatus of claim 17, wherein the controller selects the input as a pair of values (i,x_i), and computes the output as f_k (i,x)=h(k,x) XOR t_i where k is a unique key, and t_i is the i-th entry in a unique table T, which is precomputed as t_i =h(k,x_i) XOR y_i.