Methods, apparatus, and program products for inferring service usage

• US 7,296,158 B2
• Filed: 11/08/2002
• Issued: 11/13/2007
• Est. Priority Date: 11/08/2002
• Status: Active Grant

• Current Assignee: Gula Consulting Limited Liability Company (Intellectual Ventures LLC)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Staddon, Jessica N., Johnson, Robert T.
• Primary Examiner(s): REVAK, CHRISTOPHER A
• Application Number:
  US10/291,310
• Publication Number:
  US 20040091116A1
• Time in Patent Office: 1,831 Days
• Field of Search: 713/163, 713/171, 726/22, 726/26, 380/278, 380/279, 705/53, 705/71
• US Class Current: 713/171
• CPC Class Codes: G06Q 20/3829 involving key management
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 2209/60 Digital content management, e.g. content distribution
• CPC Class Codes: H04L 2209/80 Wireless network architectures or network communication protocols for wireless network security H04W12/00
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/062 for key distribution, e.g. centrally by trusted party cryptographic mechanisms or cryptographic arrangements for key distribution involving a central third party H04L9/0819
• CPC Class Codes: H04L 9/0833 involving conference or group key network architectures or network communication protocols for key management in group communication in a packet data network H04L63/065

Abstract

Given the recent changes in the policy governing Internet content distribution, such as the institution of per listener royalties for Internet radio broadcasters, content distributors now have an incentive to under-report the size of their audience. Previous audience measurement schemes only protect against inflation of audience size. We present the first protocols for audience measurement that protect against both inflation and deflation attempts by content distributors. The protocols trade-off the amount of additional information the service providers must distribute to facilitate audience inference with the amount of infrastructure required and are applicable to Internet radio, web plagiarism, and software license enforcement. The protocols can be applied to other situations, such as auditing website screen scrapers and per-seat licensed software installations.

Claims

1. A method for computing an estimated number of serviced clients, comprising:

partitioning a plurality of keys into a plurality of key sets;

for each serviced client in a plurality of serviced clients;

selecting a key set from said plurality of key sets; and

providing a collection of keys from said key set to said serviced client;

selecting a key identifier from an intersection of key collections, where said intersection of key collections includes one or more associated keys associated with said plurality of serviced clients; and

computing an estimated number of said plurality of serviced clients from said key identifier, wherein the estimated number is associated with a predetermined confidence level.

2. The method of claim 1, further comprising steps of:

encrypting data to be decrypted using a key identified by said key identifier;

providing said key identifier to one or more of said plurality of serviced clients;

providing said encrypted data to said one or more of said plurality of serviced clients; and

decrypting said encrypted data using said key.

3. The method of claim 2, wherein said data is provided by a service.

4. The method of claim 3, wherein said service is that of providing content, providing software, utilization of a resource, usage of a program, usage of a database, or access to a service where an owner of said service desires to know the amount the service is used.

5. The method of claim 1, further comprising providing said plurality of keys to a service provider.

6. The method of claim 1, further comprising providing said collection of keys to a service provider.

7. The method of claim 6, further transforming said collection of keys.

8. A system that computes an estimated number of serviced clients, comprising:

a network;

a key server, in communication with the network, comprising;

a partition mechanism configured to partition a plurality of keys into a plurality of key sets;

a key distribution mechanism configured to;

for each serviced client in a plurality of serviced clients;

selecting a key set from said plurality of key sets; and

providing a collection of keys from said key set to said serviced client;

a service provider, in communication with the network, configured to select a key identifier from an intersection of key collections, where said intersection of key collections includes one or more associated keys associated with said plurality of serviced clients; and

an audit client, in communication with the network, configured to compute an estimated number of said plurality of serviced clients from said key identifier, wherein the estimated number is associated with a predetermined confidence level.

9. The system of claim 8, wherein the service provider further comprises:

an encryption mechanism configured to encrypt data to be decrypted using a key identified by said key identifier; and

a transmission mechanism configured to send, over the network, said key identifier and said encrypted data to one or more of said plurality of serviced clients.

10. The system of claim 9, wherein the audit client comprises a decryption mechanism configured to decrypt said encrypted data using said key.

11. The system of claim 9, wherein said data is provided by a service.

12. The system of claim 11, wherein said service is that of providing content, providing software, utilization of a resource, usage of a program, usage of a database, or access to a service where an owner of said service desires to know the amount the service is used.

13. The system of claim 8, wherein the key distribution mechanism further provides said plurality of keys to the service provider.

14. The system of claim 8, wherein said serviced client further comprises a key forwarding mechanism configured to provide said collection of keys to a service provider.

15. The system of claim 14, wherein the key forwarding mechanism further comprises a key transformation mechanism configured transform said collection of keys.

16. A method for computing an estimated number of serviced clients, comprising:

sending a request for a service;

receiving a collection of keys belonging to one of a plurality of key sets;

receiving a key identifier identifying a key in said collection of keys; and

computing an estimated number of a plurality of serviced clients from said key identifier and information about said plurality of key sets, wherein the estimated number is associated with a predetermined confidence level.

17. The method of claim 16, further comprising sending said collection of keys to a service provider.

18. The method of claim 16, wherein said service is that of providing content, providing software, utilization of a resource, usage of a program, usage of a database, or access to a service where an owner of said service desires to know the amount the service is used.

19. The method of claim 17, further comprising transforming said collection of keys.

20. The method of claim 16, wherein the collection of keys is provided by a key server.

21. The method of claim 20, further comprising receiving information about said plurality of key sets.

22. The method of claim 16, further comprising receiving encrypted data responsive to said request.

23. An apparatus that computes an estimated number of serviced clients, comprising:

a network interface;

a request mechanism configured to send a request for a service using the network interface;

a first reception mechanism, responsive to the request mechanism, configured to receive a collection of keys belonging to one of a plurality of key sets;

a second reception mechanism configured to receive a key identifier identifying a key in said collection of keys; and

an inference mechanism configured to compute an estimated number of a plurality of serviced clients from said key identifier and information about said plurality of key sets, wherein the estimated number is associated with a predetermined confidence level.

24. The apparatus of claim 23, further comprising a key forwarding mechanism configured to send said collection of keys to a service provider.

25. The apparatus of claim 23, wherein said service is that of providing content, providing software, utilization of a resource, usage of a program, usage of a database, or access to a service where an owner of said service desires to know the amount the service is used.

26. The apparatus of claim 24, further comprising a transformation mechanism configured to transform said collection of keys.

27. The apparatus of claim 23, wherein the collection of keys is provided by a key server.

28. The apparatus of claim 27, further comprising a third reception mechanism configured to receive information about said plurality of key sets.

29. The apparatus of claim 23, further comprising a third reception mechanism configured to receive encrypted data responsive to said request.

30. A method for computing an estimated number of serviced clients, comprising steps of:

sending a request for a service;

receiving a collection of keys belonging to one of a plurality of key sets;

sending said collection of keys;

receiving a key identifier identifying a key in said collection of keys; and

utilizing said key to compute an estimated number of said plurality of serviced clients, wherein the estimated number is associated with a predetermined confidence level.

31. The method of claim 30, wherein the step of sending said collection of keys sends said collection of keys to a service provider of said service.

32. The method of claim 30, further comprising transforming said collection of keys.

33. The method of claim 30, wherein said service is that of providing content, providing software, utilization of a resource, usage of a program, usage of a database, or access to a service where an owner of said service desires to know the amount the service is used.

34. A method for computing an estimated number of serviced clients, comprising steps of:

receiving one or more requests for a service from a plurality of serviced clients;

receiving a key identification list for each of said one or more requests; and

selecting a key identifier from an intersection of key collections responsive to said key identification list, where said intersection of key collections includes one or more associated keys associated with said plurality of serviced clients, wherein the one or more associated keys is used to compute an estimated number of said plurality of serviced clients, wherein the estimated number is associated with a predetermined confidence level.

35. The method of claim 34, further comprising steps of:

encrypting data responsive to said service, said encrypted data to be decrypted using a key identified by said key identifier; and

transmitting said encrypted data to one or more of said plurality of serviced clients.

36. The method of claim 35, further comprising transmitting said key identifier to one or more of said plurality of serviced clients.

37. The method of claim 36, wherein said key identifier is transmitted with said encrypted data.

38. The method of claim 34, wherein a key server provides said key identification list and the method further comprising forwarding said one or more requests to said key server.

39. The method of claim 34, further comprising receiving a plurality of keys from a key server.

40. The method of claim 34, further comprising receiving a plurality of keys from one or more of said plurality of serviced clients.

41. The method of claim 34, wherein said service is that of providing content, providing software, utilization of a resource, usage of a program, usage of a database, or access to a service where an owner of said service desires to know the amount the service is used.

42. A method for computing an estimated number of serviced clients, comprising steps of:

partitioning a plurality of keys into a plurality of key sets;

receiving a request for a service for one of a plurality of serviced clients;

selecting a collection of keys from one of said plurality of key sets, said collection of keys identified by a key identification list;

sending said collection of keys to said one of said plurality of serviced clients;

sending said key identification list to a service provider;

selecting a key identifier from an intersection of key collections, where said intersection of key collections includes one or more associated keys associated with said plurality of serviced clients; and

computing an estimated number of said plurality of serviced clients from said key identifier, wherein the estimated number is associated with a predetermined confidence level.

43. The method of claim 42, further comprising sending said plurality of keys to said service provider.

44. The method of claim 42, wherein said request was forwarded by said service provider.