A note on optimal metering schemes

A metering scheme is a method by which an audit agency is able to measure the interaction between servers (e.g., web servers) and clients (e.g., browsers) during a certain number of time frames. Metering schemes involve distributing information to clients and servers. Obviously, such information distribution affects the overall communication complexity. A metering scheme is said to be optimal if the information distributed to clients and servers is the minimum possible. Optimal metering schemes have been proposed by Naor and Pinkas [Lecture Notes in Comput. Sci., Vol. 1403, pp. 576-590] and Masucci and Stinson [Lecture Notes in Comput. Sci., Vol. 1895, pp. 72-87). In this paper we show a construction for optimal metering schemes, called the vector space construction, that generalizes previous constructions for optimal metering schemes.