1,721,016 research outputs found
Sharing Multiple Secrets: Models, Schemes, and Analysis
Full text linkA multi-secret sharing scheme is a protocol to share more than one secret among a set
of participants, where each secret may have a distinct family of subsets of participants (also called
‘access structure’) that are qualified to recover it. In this paper we use an information-theoretic
approach to analyze two different models for multi-secret sharing schemes. The proposed models
generalize specific models which have already been considered in the literature. We first analyze
the relationships between the security properties of the two models. Afterwards, we show that the
security property of a multi-secret sharing scheme does not depend on the particular probability distribution
on the sets of secrets. This extends the analogous result for the case of single-secret sharing
schemes and implies that the bounds on the size of the information distributed to participants
in multi-secret sharing schemes can all be strengthened. For each of the two models considered in
this paper, we show lower bounds on the size of the shares distributed to participants. Specifically,
for the general case in which the secrets are shared according to a tuple of arbitrary (and possibly
different) access structures, we show a combinatorial condition on these structures that is sufficient
to require a participant to hold information of size larger than a certain subset of secrets. For specific
access structures of particular interest, namely, when all access structures are threshold structures,
we show tight bounds on the size of the information distributed to participants
Anonymous Membership Broadcast Schemes
Full text linkA membership broadcast scheme is a method by which a dealer broadcasts a secret identity
among a set of users, in such a way that only a single user is sure that he is the intended recipient.
Anonymous membership broadcast schemes have several applications, such as anonymous delegation,
cheating prevention, etc.
In a w-anonymous membership broadcast scheme any coalition of at most w users, which does not
include the user chosen by the dealer, has no information about the identity of the chosen user. Wang and
Pieprzyk proposed a combinatorial approach to 1-anonymous membership broadcast schemes. In
particular, they proposed a 1-anonymous membership broadcast scheme offering a logarithmic complexity
for both communication and storage. However, their result is non-constructive.
In this paper, we consider w-anonymous membership broadcast schemes. First, we propose a formal
model to describe such schemes and show lower bounds on the communication and randomness
complexities of the schemes. Afterwards, we show that w-anonymous membership broadcast schemes can
be constructed starting from .w . 1.-wise independent families of permutations. The communication and
storage complexities of our schemes are logarithmic in the number of users
- …
