A Linear Algebraic Approach to Metering Schemes. Designs, Codes and Cryptography 33 (2004) 241-260.

A metering scheme  is a method by which an audit agency is able to measure the interaction between servers and clients during a certain number of time frames. Naor and Pinkas proposed metering schemes where any server is able to compute a  proof, i.e., a value to be shown to the audit agency at the end of each time frame, if and only if it has been visited by a number of clients larger than or equal to some threshold $h$ during the time frame. It has been shown later how to construct a metering scheme realizing any access structure, where the access structure is the family of all subsets of clients which enable a server to compute its proof. Subsequently, it has been shown how to construct a metering scheme realizing any ideal access structure by  using a generalization of the Brickell vector space construction for secret sharing schemes.

In this paper we describe a linear algebraic approach to design metering schemes for a general access structure. Namely, we present a method to construct, for any given access structure, a metering scheme from any linear secret sharing scheme with the same access structure. Besides, we prove some properties about the relationship between metering schemes and secret sharing schemes. These properties provide some new bounds on the information distributed to clients and servers in a metering scheme. According to these bounds, the optimality of the metering schemes obtained by our method relies upon the optimality of the linear secret sharing schemes for the given access structure.