A Linear Algebraic Approach to Metering Schemes.
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 (Vol. 1403 of LNCS, pp. 576590) 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 (Vol. 1895 of LNCS, pp. 7287) 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.
Introduction
The current trend on the Internet suggests that the majority of revenues of web sites come from the
advertising potential of the World Wide Web. Like in every other advertising channel, web advertisers
must have a way to measure the exposure of their ads by obtaining usage statistics about web sites which
contain their ads. Indeed, the amount of money charged to display ads depends on the number of visits
received by the web sites. Consequently, advertisers should prevent the web sites from inflating the count
of their visits in order to demand more money.
An extended abstract of a preliminary version of this paper can be found in [7].
A metering scheme is a method to measure the interaction between servers and clients over a network.
In particular, we consider a scenario where there are many servers and clients, and an audit agency whose
task is to count the number of clients which have been served by each server during a certain number of
time frames. Even though metering originated in the field of web advertisements, there are several other
applications of secure metering schemes. For example, Franklin and Malkhi [13] suggested metering
schemes as a method to measure the amount of money that companies, willing to pay for the cost
required to access their web sites, should pay to the users' ISPs. Naor and Pinkas [21] considered a
different scenario, in which a newspaper distributes coupons to its clients, which give them access to an
online service. They suggested the use of metering schemes to provide verifiable measurements of the
exact number of users who have used these coupons.
Metering schemes were first described by Naor and Pinkas [21]. They analyzed metering schemes
where any server which has been visited by any set of h or more clients in a time frame, where h is
a parameter of the scheme, is able to compute a proof 1 , whereas, any server receiving visits from less
than h clients in a time frame has absolutely no information about its proof for that time frame. These
schemes are called threshold metering schemes.
The authors of [19] considered a more general situation. They showed how to construct a metering
scheme realizing any access structure, where the access structure is the family of all subsets of clients,
called qualified sets, which enable a server to compute its proof (i.e., if a server receives visits from
all clients belonging to some qualified set, then it can compute the proof). Metering schemes involve
distributing information to clients and servers. The clients participating in the metering process receive
some information from the audit agency and such information is used to compute the information passed
to the servers when visiting them. Since such information distribution affects the overall communication
complexity, a major goal is to construct metering schemes whose overhead to the overall communication
is as small as possible. Thus, the problem of establishing bounds on the size of the information distributed
to the parties has been addressed in several papers (see [4, 5, 12, 19, 20, 7]). A metering scheme is said
to be ideal if the information distributed to clients and servers is the minimum possible. Any access
structure for which there exists an ideal metering scheme realizing it is called an ideal access structure.
The authors of [8] showed how to construct a metering scheme realizing any ideal access structure. The
construction is based on the Brickell vector space construction for secret sharing schemes [9].
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.
The paper is organized as follows: In Section 2 we review the model and notation used to describe
metering schemes. In Section 3 we study the relationship between metering schemes and secret sharing
schemes. This relationship enables us to derive new lower bounds on the communication complexity
of metering schemes. In Section 4 we first review some concepts about linear secret sharing schemes;
afterwards, we present a linear algebraic approach to design metering schemes. This approach will enable
us to construct a metering scheme realizing an access structure from any linear secret sharing scheme
realizing the same access structure.
In metering schemes, a proof is a value that the server can compute at the end of each time frame if and only if it has
been visited by a fixed number of clients. Such a value, at the end of each time frame, is sent to the audit agency.
Metering Schemes for General Access Structures
A metering scheme consists of n clients, say C and an audit agency A
whose task is to measure the interaction between the clients and the servers in order to count the number
of client visits that any server receives. We assume that the scheme is active for - time frames and that
the audit agency is interested in the number of clients which visit each server during any time frame
be the set of clients. An access structure on C is a set \Gamma ' 2 C of subsets
of clients. The subsets in \Gamma are called qualified subsets. A metering scheme realizes the access structure
any server which has been visited by at least a qualified subset of clients in \Gamma during a time frame is
able to provide the audit agency with a proof for the visits it has received. The access structure that we
consider in this paper are monotone, i.e., they satisfy the following property: if
then Y 2 \Gamma. Indeed, if a server receives visits by a subset Y of clients which contains a qualified subset
then it can reconstruct its proof by ignoring the information provided by clients in Y n X .
In the following we recall the information theoretical model proposed in [19] for metering schemes
realizing any access structure \Gamma. With a boldface capital letter, say X, we denote a random variable taking
value on a set, denoted with the corresponding capital letter X; according to some probability distribution
(x)g x2X . The values such a random variable can take are denoted with the corresponding lower
letter. Given a random variable X we denote with H(X) the Shannon entropy of fPr X (x)g x2X . For a
complete treatment of the concepts of Information Theory, the reader is advised to consult [11].
There is an initialization phase, in which the audit agency provides each client with some information
about the server's proofs. For any by C i the random variable associated to the
information that the audit agency A gives to the client C i . During a regular operation, a client uses
the information received in the initialization phase to compute the information passed to servers when
visiting them. For any we denote by C t
i;j the random variable
associated to the information that the client C i sends to the server S j when visiting it in time frame t.
During the proof computation phase, servers compute the proofs to be sent to the audit agency. For any
we denote by P t
j the random variable associated to the proof computed
by the server S j when it has been visited by a qualified set of clients in time frame t. Given any set of
clients X we denote by X t
j the random variable associated to the information that clients in X send to
the server S j when visiting it in time frame t.
We consider a scenario in which a certain number s - m of servers can be corrupt. A corrupt server
can be assisted by corrupt clients and other corrupt servers in computing its proof. At time frame t, a
corrupt server gives to another corrupt server the information that it has received during time frames
t. For any we denote by V [t]
j the random variable associated to
the information known by a corrupt server S j in time frames t. Let S j 1
be a coalition of
servers and let g. We denote by P t
the random variable associated
to the proofs computed by servers having indices in B in time frame t. Similarly, we denote by V [t]
the
random variable associated to the information known by the servers in B in time frames t. Given
a set of clients X and a set of server indices B, we denote by X t
the random variable associated to the
information given by clients in X to servers having indices in B in time frame t.
servers can also be assisted by corrupt clients in computing their proofs. A corrupt client can
donate to any corrupt server the whole information received by the audit agency during the initialization
phase. A metering scheme realizing an access structure \Gamma is defined as follows.
Definition 2.1 An (n; m; -; c; s) metering scheme realizing the access structure \Gamma is a protocol to measure
the interaction between n clients C during - time frames in such a way
that the following properties are satisfied:
1. For any time frame t any client is able to compute the information needed to visit any server:
Formally, for any holds that
2. For any time frame any server which has been visited by a qualified subset of clients
in time frame t can compute its proof for t:
Formally, for any holds that
3. Let B s be a set of indices of corrupt servers and let D 62 \Gamma be a
coalition of corrupt clients. Assume that in some time frame t each corrupt server in the coalition
has been visited by a subset of clients X , where D [ X 62 \Gamma: Then, the servers in the coalition have
no information about their proofs for time frame t, even if they are helped by the corrupt clients in
D.
Formally, for any B '
that
The authors of [19] proved several lower bounds on the communication complexity of metering schemes
realizing monotone access structures. In particular, they proved that if the proofs for the servers are
uniformly chosen in a finite field F then the size of the information that any client passes to any server
during a visit is lower bounded by log jF j, that is,
log jC t
Moreover, if also the proofs for the servers are statistically independent, then the size of the information
distributed to any client during the initialization phase is lower bounded by s- log jF j, that is
log
Metering Schemes and Secret Sharing Schemes
In this section we study the relationship between metering schemes and secret sharing schemes. This
relationship enables us to restate all the bounds on the information rates of secret sharing schemes
realizing a given access structure, in order to new obtain lower bounds on the communication complexity
of metering schemes realizing the same access structure. These lower bounds generalize (1) and (2) and
do not depend only on the number s of corrupt servers and the number - of time frames, but also on
the information rate of the access structure realized by the metering scheme. In the following section we
recall some basic concepts about secret sharing schemes. The survey by Stinson [26] contains an unified
description of results in the area of secret sharing schemes.
3.1 Sharing Schemes
A secret sharing scheme is a method by which a dealer shares a secret among a set C of parties, by
distributing some information to each party, in such a way that only qualified subsets of parties, pooling
together their information, can reconstruct the secret; but subsets of parties that are not enabled to
recover the secret have absolutely no information about it. Secret sharing schemes were introduced by
Shamir [23] and Blakley [3]. They analyzed the case when only subsets of C of cardinality at least h,
for a fixed integer h - jCj, can reconstruct the secret. Subsequently, Ito, Saito, and Nishizeki [15] and
Benaloh and Leichter [2] showed how to realize a secret sharing scheme realizing any monotone access
structure.
be a set of parties. We denote by X the random variable associated to the information
distributed by the dealer to parties in X . Moreover, we denote by P the random variable associated to
the secret to be shared. A secret sharing scheme is defined as follows:
Definition 3.1 A secret sharing scheme realizing the access structure on C is a protocol to share a secret
chosen in P among the parties in C in such a way that
1. Any qualified set of participant is able to compute the secret.
Formally, for any X 2 \Gamma, it holds that
2. Any non-qualified set of participants has absolutely no information about the secret.
Formally, for any X 62 \Gamma, it holds that
The efficiency of a secret sharing scheme is usually quantified by a measurement called the information
rate of the scheme. Let \Sigma be a secret sharing scheme realizing an access structure \Gamma. The information
rate ae(\Sigma; \Gamma; P ) is defined as the ratio between the size of the secret and the maximum size of the shares
given to the participants. Secret sharing schemes with information rate ae = 1, which is the maximum
possible value of this parameter, are called ideal . An access structure \Gamma on C is said to be ideal if there
exists an ideal secret sharing scheme realizing it.
Given an access structure \Gamma on C, we will denote by ae   (\Gamma) the optimal information rate for a secret
sharing scheme realizing the access structure \Gamma. More precisely, ae
supremum is taken over all possible sets of secrets P with sharing schemes \Sigma
realizing the access structure \Gamma.
3.2 New Lower Bounds on the Communication Complexity
Let us consider Properties 2. and 3. of Definition 2.1. From these properties it follows that a metering
scheme realizing an access structure \Gamma can be seen as a secret sharing scheme realizing the access structure
\Gamma with set of secrets P t
shared among the clients C
from Property 2. of Definition 2.1, for any holds that
that is exactly the reconstruction property of the secret sharing scheme, i.e. Property 1.
of Definition 3.1. Moreover, from Property 3. of Definition 2.1 we obtain
\Gamma, that is the security property of the secret sharing scheme, i.e.,
Property 2. of Definition 3.1.
This implies that all known results on secret sharing schemes can be adapted to metering schemes. In
particular, we obtain a new lower bound on the size of the information distributed by clients to servers
during their visits, as stated by the next theorem.
Theorem 3.2 In any (n; m; -; c; s) metering scheme realizing the access structure \Gamma, for any
holds that
log jC t
ae   (\Gamma) :
In a similar way we can obtain a lower bound on the size of the information distributed by the audit
agency to each client during the initialization phase. Let S be the set of indices of the corrupt servers in
a metering scheme. It is easy to see that a metering scheme realizing an access structure \Gamma can be seen
as a secret sharing scheme realizing the access structure \Gamma with set of secrets P [-
shared
among the clients C
. From Property 2. of Definition
2.1, it holds that
s
that is, the reconstruction property of the secret sharing scheme.
\Gamma. We have that
Moreover,
Therefore, from (3) and (4) it follows that, for any
and also the security property of the secret sharing scheme holds. Therefore, we obtain the following
theorem, which establishes a lower bound on the size of the information distributed by the audit agency
to the clients during the initialization phase.
Theorem 3.3 In any (n; m; -; c; s) metering scheme realizing the access structure \Gamma it holds that
log
ae   (\Gamma) :
4 Designing Metering Schemes from Linear Secret Sharing Schemes
In this section, we present a method to construct an (n; m; -; c; s) metering scheme realizing an access
structure \Gamma from any linear secret sharing scheme realizing the same access structure. The optimality of
the metering scheme relies upon the optimality of the linear secret sharing scheme, that is, if we can find
a linear secret sharing scheme with optimal information rate for the access structure \Gamma, we will be able
to construct an optimal metering scheme realizing the access structure \Gamma.
4.1 Linear Secret Sharing Schemes
In this section we recall next some basic facts about linear secret sharing schemes. Let E be a vector
space with finite dimension over the finite field GF (q) and let be a set of participant.
For any C i is a special participant called dealer, let us consider a vector
space and a surjective linear mapping us suppose that these linear
mappings verify that, for any X ae C,
This family of vector spaces and linear surjective mappings determines the access structure
A secret sharing scheme with set of secrets defined as follows: for a
secret value is chosen at random and any participant C
receives the vector a its share.
The information rate of this scheme is sharing schemes constructed
in this way are called linear secret sharing schemes (LSSSs for short). In a LSSS, the secret
is computed by a linear mapping from the shares of the participants in a qualified subset. That is, for
every
2 \Gamma, there exists a linear mapping
that enables the
participants in X to compute the secret.
Linear secret sharing schemes were first introduced by Brickell [9], who considered only ideal linear
schemes, i.e., with dim C[fAg. General linear secret sharing schemes were introduced
by Simmons [24], Jackson and Martin [16] and Karchmer and Wigderson [18] under other names, such
as geometric secret sharing schemes ormonotone span programs.
In an ideal linear secret sharing scheme with dim we can consider that the surjective linear
mappings - i are non-zero vectors in the dual space E   . In that case, a subset X ae C is qualified if and
only if the vector - can be expressed as a linear combination of the vectors f- g. The
access structures that can be defined in this way are called vector space access structures . Threshold,
multilevel, and compartmented access structures [9] are a particular case of vector space access structures.
For example, if \Gamma is the (h; n)-threshold access structure, we can take q ? n a prime power and x
for any C different elements and consider
and
n. The ideal linear scheme we obtain in this way is
in fact equivalent to the Shamir's threshold scheme [23].
Using the monotone circuit construction due to Ito, Saito and Nishizeki [14], Simmons, Jackson and
Martin [25] proved that any access structure \Gamma can be realized by a linear secret sharing scheme. The
main drawback of the LSSSs that are constructed by using the general method proposed in [25] is that
their information rate is in general very small.
Nevertheless, using decomposition techniques, linear secret sharing schemes with much better information
rate can be found for some access structures. Those techniques consist of decomposing the given
access structure \Gamma into several substructures and combining secret sharing schemes on these substructures
in order to obtain a secret sharing scheme for \Gamma. For instance, one of the most powerful decomposition
techniques to construct secret sharing schemes with good information rate is the -decomposition construction
due to Stinson [27]. A linear secret sharing scheme is obtained when combining linear schemes
in a -decomposition construction.
4.2 The Scheme
In this section, we present a method to construct a metering scheme realizing an access structure \Gamma from
any linear secret sharing scheme realizing the same access structure.
\Gamma be an access structure on the set of clients g. Let s be the maximum number
of corrupt servers and let - be the number of time frames the scheme must be active. Let
linear mappings defining a LSSS with access structure \Gamma and set of
secrets . As we have mentioned in Section 3.1, for any
2 \Gamma, there exists
a linear mapping
that enables the clients in X to compute the secret.
Initialization Phase
ffl For any the audit agency A chooses (and makes public) the linear
defined by
in such a way that any set of s- such
linear maps \Pi t
j the corresponding vectors in the dual space (GF (q) s- )   are linearly independent.
ffl For any linear map \Pi t
j and for any
defined
by
ffl Next, A chooses a random matrix
ffl Afterwards, A distributes each row c
shares, in such a way that each
client C i receives s- shares:
In this way, given a qualified set of clients
2 \Gamma, we have that the k-th row in M
satisfies
Regular Operation Phase
ffl When client C i visits server S j in time frame t, C i computes
and sends it to server S j .
Proof Generation Phase
ffl Let us suppose that clients in
have visited a server S j in time frame t.
and has to compute the proof p t
j , which is defined by
ffl Let us see how server S j can obtain p t
Since MX is linear,
Since server S j possesses (c t
obtains the proof p t
.
4.2.1 Analysis of the Scheme
Now we prove that the above scheme is a metering scheme realizing the access structure \Gamma. We need to
prove that the scheme satisfies Properties 1., 2, and 3. of Definition 2.1.
It is immediate to verify that the scheme satisfies Property 1 of Definition 2.1. Indeed, for
any given by the audit agency to the client C i consists of a vector
i . For any the information given to the server S j
by client C i during a visit in time frame t is obtained by computing c t
for any time frame t, each client can compute the piece to be given to any visited server.
It is also easy to verify that the scheme satisfies Property 2 of Definition 2.1. Let
be a qualified set of clients visiting a server S j in time frame t. Then, S j has the values (c t
and can compute the proof p t
j as seen in Equation (5).
Finally, we prove that the scheme satisfies Property 3 of Definition 2.1. Instead of distinguishing
between a set of corrupt clients D and a set X , where D [ X 62 \Gamma, of honest clients visiting the servers
on time frame t, we can consider that the clients in X are also corrupt. That is, we simply consider
a subset D ae C, D 62 \Gamma, of corrupt clients helping a coalition of s corrupt servers in computing their
proofs for time frame - . The total information known to the coalition of corrupt servers is constituted
by the information collected in time frames and the information received in time frame - .
We consider the worst possible case, in which the corrupt servers have collected the maximum possible
information in time frames that is, we assume that each server S j in the coalition has been
visited by all clients C Therefore, we have to prove that
for any subset B of corrupt servers, with cardinality at most s. We need the following result.
Lemma 4.1 Let E, E 0 and E 1 be vector spaces over a finite field GF (q). Let us consider two linear
mappings, us suppose that a vector x
is chosen uniformly at random and let us consider the random variables X 0 and X 1 corresponding,
1.
2.
Proof. If we know the value of x we know that x
is any vector with ' 1 are equiprobable.
Then, x 0 can be uniquely determined from x 1 if and only if ' 0 (ker only if
. The value of x 1 does not provide any information about the value of x 0 if and only if
In any other case, the value of x 1 provides partial information about the value of x 0 .
Finally, we have to prove that ' 0 (ker us suppose
that ' 0 (ker there exists y 2 ker ' 1 such that ' 0
Reciprocally, if ker
In order to prove Equation (6) by means of Lemma 4.1, we need to determine the linear maps ' 0
respectively, to the random variables P -
and DV [- \Gamma1]
. Let us observe that the
information c held by each client C i has been obtained from the LSSS defined by
mappings Therefore,
vector such that - 0 (y k
On the other hand, we consider the linear map OE t
defined by OE t
corrupt server S j , where time frame t 2
Therefore, the kernel of the linear map ' 1 associated to the random variable DV [- \Gamma1]
is
i is the linear map defined by - i (y
Analogously,
(y). Therefore, the kernel of the linear map ' 0 associated to the random variable
B is
ker OE -
At this point, we just have to prove that
any vector in E s- . From the independence of maps f\Pi t
we have that
Then,
0;j (b
2 \Gamma, from the properties of the LSSS it holds that, for any
such that - 0 (z k Therefore,
On the other hand, observe that
0;j (b
Hence, (w Finally, we conclude that
4.2.2 Efficiency of the Scheme
In this section we show that the scheme described in Section 4 meets the bounds of Theorems 3.2 and
3.3.
Let
be the information rate of the LSSS \Sigma. Let q (a power of a prime) be the cardinality of the finite field
F q . The amount of information that a client C receives by the audit agency during the initialization
phase is log jC . Observe that
log
ae
log
ae
Therefore, the bound given in Theorem 3.3 is attained if \Sigma has optimal information rate, that is, if
The amount of information that a client sends to a server during a visit is log jC t
Observe that
log jC t
log jP t
Therefore, the bound given in Theorem 3.2 is attained if \Sigma has optimal information rate, that is, if
5 Some Examples
Optimal metering schemes can be constructed for any access structure A such that a LSSS with optimal
information rate is known for A. For example, let us consider the access structure on a set
of 4 clients whose minimal authorized subsets are A
This access structure is well known in the literature concerning secret sharing schemes [10]. It has been
proved in [10] that the information rate of any SSS for this access structure is at most 2=3. Besides, there
exists a linear secret sharing scheme \Sigma with information rate ae = 2=3. That is, the optimal information
rate of this access structure is ae   there exists a LSSS for A with Therefore, we
can construct a metering scheme realizing A and attaining the bounds showed in Section 3.
6 Conclusions
In this paper we have described a linear algebraic approach to design metering schemes realizing any
access structure. Namely, we have presented a method to construct a metering scheme realizing any
access structure, from any linear secret sharing scheme realizing the same access structure.
We have also proved 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.

Acknowledgements

This work was done while the third author was visiting the Departament de Matem'atica Aplicada IV at
the Universitat Polit'ecnica de Catalunya, Barcelona, Spain She would like to thank the Department for
its hospitality.
The research of the first and the third author is partially supported by C.N.R. under grant CN-
RRG008BF3: "Pubblicit'a Online: Nuove Misure per Nuovi Media. Auditing e Accounting Sicuro sul
WEB".



--R

Secure Schemes for Secret Sharing Schemes and Key Distribution


Metering Schemes with Pricing
Dynamic Multi-Threshold Metering Schemes
Tigh bounds on the Information Rate of Secret Sharing Schemes
New Bounds on the Communication Complexity of Metering Schemes
A Note on Ideal Metering Schemes
Some Ideal Secret Sharing Schemes
On the Size of the Shares in Secret Sharing Schemes
Elements of Information Theory.
An Information Theoretic Approach to Metering Schemes
Auditable Metering with Lightweight Security
sharing scheme realizing any access structure
Sharing Schemes Realizing any Access Structure
Geometric Secret Sharing Schemes and Their Duals Design
Secure and Lightweight Advertising on the Web

Metering Schemes for General Access Structures
Efficient Metering Schemes with Pricing
Secure and Efficient Metering
Secure Accounting and Auditing on the Web


The Geometry of Secret Sharing Schemes
An Explication of Secret Sharing Schemes
Decomposition Constructions for Secret-Sharing Schemes
--TR
Generalized secret sharing and monotone functions
How to (really) share a secret
Elements of information theory
Some improved bounds on the information rate of perfect secret sharing schemes
An explication of secret sharing schemes
Geometric secret sharing schemes and their duals
Tight Bounds on the Information Rate of Secret Sharing Schemes
Secure accounting and auditing on the Web
Secure and lightweight advertising on the Web
Auditable metering with lighweight security
How to share a secret
A note on optimal metering schemes
Metering Schemes with Pricing
Dynamic Multi-threshold Metering Schemes
Metering Schemes for General Access Structures
distributed audit;metering;secret sharing;cryptography;entropy