Efficient metering schemes with pricing

In order to decide on advertisement fees for Web servers, Naor and Pinkas i ntroduced metering schemes. They proposed metering schemes in which any ser ver is able to compute a proof to be sent to an audit agency if and only if it has been visited by at least a certain number, say h, of clients. In su ch schemes, any server which has been visited by less than h clients has no information about the proof; consequently, it does not receive any money f rom the audit agency. In order to have a more flexible payment system, Blun do, De Bonis, and Masucci introduced metering schemes with pricing. These s chemes allow different rates of payments based on the number of visits that each server has received. In this paper, we are interested in the efficiency of metering schemes with pricing. We propose a new model for metering schemes with pricing and we p rovide lower bounds on the size of the information distributed to clients a nd servers, and on the number of random bits needed by the audit agency to set up a metering scheme with pricing. These bounds are tight, as we provid e a scheme which achieves them with equality. Compared to the scheme presen ted by Blundo, De Bonis, and Masucci, our scheme distributes less informati on to clients and servers. The drawback of our scheme is that it requires s ervers to interact with the audit agency in order to compute their proofs.