Bounds and constructions for metering schemes

Metering schemes are cryptographic protocols to count the number of visits received by web sites. These measurement systems may be used to decide the amount of money to be paid to web sites hosting advertisements. Indeed, the amount of money paid by the publicity agencies to the web sites depends on the number of clients which visited the sites. In this paper we consider two generalizations of the metering scheme proposed by Naor and Pinkas (Vol. 1403 of LNCS, pp. 576–590). In their scheme a web site is paid if and only if the number of clients which visit the site is greater than a fixed threshold. We consider ramp metering schemes and metering schemes with pricing, that is, a scheme providing a tradeoff between the security and the complexity of information distribution and a scheme allowing to count the exact number of visits received by each server so that each server can be paid a proportional amount of money, respectively. We provide lower bounds on the size of the information distributed to clients and servers by these metering schemes and present schemes which achieve these lower bounds.

Full Text (PDF format)

Published 1 January 2002