Method for secure accounting and auditing on a communications network

• US 6,055,508 A
• Filed: 06/05/1998
• Issued: 04/25/2000
• Est. Priority Date: 06/05/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: Naor, Moni, Pinkas, Binyamin
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): Myhre, James W.
• Application Number:
  US09/092,069
• Time in Patent Office: 690 Days
• Field of Search: 705/11, 705/404, 705/405, 713/168
• US Class Current: 705/7.38
• CPC Class Codes: G06Q 10/0639 Performance analysis of employees; Performance analysis of enterprise or organisation operations
• 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/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 41/28 Restricting access to network management systems or functions, e.g. using authorisation function to access network configuration
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/022 by sampling
• CPC Class Codes: H04L 43/06 Generation of reports
• CPC Class Codes: H04L 9/321 involving a third party or a trusted authority
• CPC Class Codes: H04L 9/3271 using challenge-response

Abstract

A method for secure accounting and auditing of a communications network operates in an environment in which many servers serve an even larger number of clients (e.g. the web), and are required to meter the interaction between servers and clients (e.g. counting the number of clients that were served by a server). The method (metering process) is very efficient and does not require extensive usage of any new communication channels. The metering is secure against fraud attempts by servers which inflate the number of their clients and against clients that attempt to disrupt the metering process. Several secure and efficient constructions of this method are based on efficient cryptographic techniques, are also very accurate, and preserver the privacy of the clients.

Claims

1. A method for secure accounting and auditing of a communications network, said network having at least one server, a plurality of clients, and at least one audit-agency, the method comprising the steps of:

initializing, beginning of a metered time frame, interacting with a client, and processing at end of time frame;

wherein;

(a.) initializing includes an audit-agency choosing a substantially random key and said audit-agency securely sending, to each server and to each client, data that depends on at least said key and on identity-data of the server or the client receiving said sending;

(b.) beginning of a metered time frame includes the audit-agency sending a challenge to at least one server;

(c.) interacting with a client, of said initialized clients, includes firstly a server sending to the client a challenge which depends on at least the challenge that the server received from the audit-agency, and secondly the client replying with an answer that is computationally dependant on the challenge that said client received and on information that said client received in its initialization step; and

(d.) processing at end of time frame includes firstly a server performing a computation which depends on at least the answers said server received from clients, and secondly sending to the audit-agency a compact proof for the number of clients served by said server.

2. A method according to claim 1 wherein sending to the client a challenge is accomplished implicitly by computations of the servers and of the clients.

3. A method according to claim 1 wherein sending to the server a challenge is accomplished implicitly by computations of the audit-agency and of the servers.

4. A method according to claim 1 wherein a proof for the number of clients served, being K clients visiting a server S in a time period T, includes:

(e.) in the initializing, the audit-agency generating a random polynomial Q(x,y) over a predetermined finite field Zp, of degree k-1 in x and d-1 in y; and

each client C receiving the polynomial Qc(y)=P(C,y) which is constructed from P by substituting C for x, and is of degree d-1 in y;

(f.) such that a client C that visits server S at data t sends a value Qc(St)=P(C,ST) wherein St is a function of S and t, in Zp;

(g.) and a proof generation includes, for the polynomial P(x,St), after serving k clients in time period T, S interpolating the polynomial and calculating P(0,St);

(h.) and a proof of serving k clients in time period T by the audit-agency includes verifying this value by evaluating the polynomial P at a predetermined location.

5. A method according to claim 1 wherein the computational dependency of the challenge is based on hash trees.

6. A method according to claim 1 wherein the computational dependency of the challenge is based on pricing-via-processing.

7. A method according to claim 1 wherein the computational dependency of the challenge is based on secure function evaluation.

8. A method according to claim 1 wherein the computational dependency of the challenge is based on micro-payments.

9. A method according to claim 1 wherein the computational dependency of the challenge is based on secret sharing.

10. A method according to claim 9 wherein error-correcting properties are used to reconstruct the secret.

11. A method according to claim 1 wherein the interacting includes a client sending a share to a server, said server evaluating a polynomial of degree d-1 wherein said evaluating uses a computation requiring d multiplications using Horner'"'"'s rule, and said evaluating is performed in a field Zp wherein 1/p is the error probability.

12. A method according to claim 11 wherein the field Zp is set to be 32 bits long.

13. A method according to claim 11 wherein the field Zp is set to be with 2³² -5 elements.

14. A method according to claim 11 wherein the field Zp is set to be a Galois field with 2³² elements.

15. A method according to claim 1 wherein the clients are divided at random into n classes, and wherein the server is asked to prove a predetermined number of visits from a random class.

16. A method according to claim 1 wherein the clients are divided at random into n classes, and wherein the server is asked to prove a predetermined number of visits from at least one predetermined class.

17. A method according to claim 1 wherein a number of measurements in which the method is used is of the same order as d, the degree of y in P, times the number of classes n.

18. A method according to claim 1 wherein interacting includes a server counting client turnover or counting visits by clients of a predetermined audience or counting requests for royalty-payment-requiring-property or counting requests for an access-cost payment-service by a third party or counting coupons received from clients;

and wherein processing at end of time frame includes a proof for any of said countings.

19. A method according to claim 1 wherein a server verifies the answer received from the client.

20. A method according to claim 1 wherein a client'"'"'s answer has a domain that is unknown to the server.

21. A method according to claim 1 wherein the computational dependency of the challenge is based on quorum systems.