[Resource Topic] 2001/087: A Linear Algebraic Approach to Metering Schemes

Welcome to the resource topic for 2001/087

A Linear Algebraic Approach to Metering Schemes

Authors: C. Blundo, S. Martìn, B. Masucci, C. Padrò


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.

ePrint: https://eprint.iacr.org/2001/087

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .