**A Linear Algebraic Approach to Metering Schemes**

*C. Blundo and S. Mart́n and B. Masucci and C. Padṛ*

**Abstract: **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.
Masucci and Stinson
showed 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.
They also provided lower bounds on the communication
complexity of metering schemes.

In this paper we describe a linear algebraic approach to design metering schemes realizing any access structure. Namely, given any access structure, we present a method to construct a metering scheme realizing it 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.

**Category / Keywords: **electronic commerce and payment, secret sharing, information theory

**Date: **received 26 Oct 2001

**Contact author: **masucci at dia unisa it

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

**Version: **20011026:130526 (All versions of this report)

**Short URL: **ia.cr/2001/087

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]