## CryptoDB

### Carles Padró

#### Affiliation: UPC, Spain

#### Publications

**Year**

**Venue**

**Title**

2018

EUROCRYPT

2012

JOFC

Ideal Multipartite Secret Sharing Schemes
Abstract

Multipartite secret sharing schemes are those having a multipartite access structure, in which the set of participants is divided into several parts and all participants in the same part play an equivalent role. In this work, the characterization of ideal multipartite access structures is studied with all generality. Our results are based on the well-known connections between ideal secret sharing schemes and matroids and on the introduction of a new combinatorial tool in secret sharing, integer polymatroids .Our results can be summarized as follows. First, we present a characterization of multipartite matroid ports in terms of integer polymatroids. As a consequence of this characterization, a necessary condition for a multipartite access structure to be ideal is obtained. Second, we use representations of integer polymatroids by collections of vector subspaces to characterize the representable multipartite matroids. In this way we obtain a sufficient condition for a multipartite access structure to be ideal, and also a unified framework to study the open problems about the efficiency of the constructions of ideal multipartite secret sharing schemes. Finally, we apply our general results to obtain a complete characterization of ideal tripartite access structures, which was until now an open problem.

2008

EUROCRYPT

2008

EPRINT

Detection of Algebraic Manipulation with Applications to Robust Secret Sharing and Fuzzy Extractors
Abstract

Consider an abstract storage device $\Sigma(\G)$ that can hold a
single element $x$ from a fixed, publicly known finite group $\G$.
Storage is private in the sense that an adversary does not have read
access to $\Sigma(\G)$ at all. However, $\Sigma(\G)$ is non-robust in the sense
that the adversary can modify its contents by adding some offset $\Delta \in \G$.
Due to the privacy of the storage device, the value $\Delta$ can only depend on an adversary's {\em a priori} knowledge of $x$. We introduce a new primitive called an {\em
algebraic manipulation detection} (AMD) code, which encodes a source $s$ into a value $x$ stored on $\Sigma(\G)$ so that any tampering
by an adversary will be detected, except with a small error probability $\delta$. We give a nearly optimal construction of AMD codes,
which can flexibly accommodate arbitrary choices for the length of the source $s$ and security level $\delta$. We use this construction in two applications:
\begin{itemize}
\item We show how to efficiently convert any linear secret sharing
scheme into a {\em robust secret sharing scheme}, which ensures that
no \emph{unqualified subset} of players can modify their shares and cause
the reconstruction of some value $s'\neq s$.
\item
We show how how to build nearly optimal {\em robust fuzzy
extractors} for several natural metrics. Robust fuzzy extractors enable one to reliably extract and later recover random keys from noisy and non-uniform secrets,
such as biometrics, by relying only on {\em non-robust public storage}. In the past, such constructions were known only in the random oracle model, or required the entropy rate of the secret to be greater than half. Our construction relies on a randomly chosen common reference string (CRS) available to all parties.
\end{itemize}

2007

CRYPTO

2006

EPRINT

On Secret Sharing Schemes, Matroids and Polymatroids
Abstract

The complexity of a secret sharing scheme is defined as the ratio between the maximum length of the shares and the length of the secret. The optimization of this parameter for general access structures is an important and very difficult open problem in secret sharing. We explore in this paper the connections of this open problem with matroids and polymatroids.
Matroid ports were introduced by Lehman in 1964. A forbidden minor characterization of matroid ports was given by Seymour in 1976. These results are previous to the invention of secret sharing by Shamir in 1979. Important connections between ideal secret sharing schemes and matroids were discovered by Brickell and Davenport in 1991. Their results can be restated as follows: every ideal secret sharing scheme defines a matroid, and its access structure is a port of that matroid. In spite of this, the results by Lehman and Seymour and other subsequent results on matroid ports have not been noticed until now by the researchers interested in secret sharing.
Lower bounds on the optimal complexity of access structures can be found by taking into account that the joint Shannon entropies of a set of random variables define a polymatroid. We introduce a new parameter, which is denoted by $\kappa$, to represent the best lower bound that can be obtained by this method. We prove that every bound that is obtained by this technique for an access structure applies to its dual structure as well.
By using the aforementioned result by Seymour we obtain two new characterizations of matroid ports. The first one refers to the existence of a certain combinatorial configuration in the access structure, while the second one involves the values of the parameter $\kappa$ that is introduced in this paper. Both are related to bounds on the optimal complexity. As a consequence, we generalize the result by Brickell and Davenport by proving that, if the length of every share in a secret sharing scheme is less than 3/2 times the length of the secret, then its access structure is a matroid port. This generalizes and explains a phenomenon that was observed in several families of access structures.
Finally, we present a construction of linear secret sharing schemes for the ports of the Vamos matroid and the non-Desargues matroid, which do not admit any ideal secret sharing scheme. We obtain in this way upper bounds on their optimal complexity. These new bounds are a contribution on the search of examples of access structures whose optimal complexity lies between 1 and 3/2.

2006

EPRINT

Ideal Multipartite Secret Sharing Schemes
Abstract

Multipartite secret sharing schemes are those having a multipartite access structure, in which the set of participants is divided into several parts and all participants in the same part play an equivalent role. In this work, the characterization of ideal multipartite access structures is studied with all generality. Our results are based on the well-known connections between ideal secret sharing schemes and matroids and on the introduction of a new combinatorial tool in secret sharing, integer polymatroids.
Our results can be summarized as follows. First, we present a characterization of multipartite matroid ports in terms of integer polymatroids. As a consequence of this characterization, a necessary condition for a multipartite access structure to be ideal is obtained.
Second, we use representations of integer polymatroids by collections of vector subspaces to characterize the representable multipartite matroids. In this way we obtain a sufficient condition for a multipartite access structure to be ideal, and also a unified framework to study the open problems about the efficiency of the constructions of ideal multipartite secret sharing schemes. Finally, we apply our general results to obtain a complete characterization of ideal tripartite access structures, which was until now an open problem.

2005

CRYPTO

2005

EPRINT

Representing small identically self-dual matroids by self-dual codes
Abstract

The matroid associated to a linear code is the representable matroid that is defined by the columns of any generator matrix. The matroid associated to a self-dual code is identically self-dual, but it is not known whether every identically self-dual representable matroid can be represented by a self-dual code.
This open problem was proposed by Cramer et al ("On Codes, Matroids and Secure Multi-Party Computation from Linear Secret Sharing Schemes", Crypto 2005), who proved it to be equivalent to an open problem on the complexity of multiplicative linear secret sharing schemes.
Some contributions to its solution are given in this paper. A new family of identically self-dual matroids that can be represented by self-dual codes is presented. Besides, we prove that every identically self-dual matroid on at most eight points is representable by a self-dual code.

2004

EPRINT

On codes, matroids and secure multi-party computation from linear secret sharing schemes
Abstract

Error correcting codes and matroids have been widely used in the study of ordinary secret sharing schemes. In this paper, we study the connections between codes, matroids, and a special class of secret sharing schemes: multiplicative linear secret sharing schemes. Such schemes are known to enable multi-party computation protocols secure against general (non-threshold) adversaries.
Two open problems related to the complexity of multiplicative LSSSs are considered in this paper.
The first one deals with strongly multiplicative LSSSs. As opposed to the case of multiplicative LSSSs, it is not known whether there is an efficient method to transform an LSSS into a strongly multiplicative LSSS for the same access structure with a polynomial increase of the complexity. We prove a property of strongly multiplicative LSSSs that could be useful in solving this problem. Namely, using a suitable generalization of the well-known Berlekamp-Welch decoder, we show that all strongly multiplicative LSSSs enable efficient reconstruction of a shared secret in the presence of malicious faults.
The second one is to characterize the access structures of ideal multiplicative LSSSs. Specifically, we wonder whether all self-dual vector space access structures are in this situation. By the aforementioned connection, this in fact constitutes an open problem about matroid theory, since it can be re-stated in terms of representability of identically self-dual matroids by self-dual codes. We introduce a new concept, the flat-partition, that provides a useful classification of identically self-dual matroids. Uniform identically self-dual matroids, which are known to be representable by self-dual codes, form one of the classes. We prove that this property also holds for the family of matroids that, in a natural way, is the next class in the above classification: the identically self-dual bipartite matroids.

2002

EPRINT

A Distributed RSA Signature Scheme for General Access Structures
Abstract

In a distributed digital signature scheme, a set of participants shares a secret information that allows them to compute a valid signature for a given message. These systems are said to be robust if they can tolerate the presence of some dishonest players.
Up to now, all the proposed schemes consider only threshold structures: the tolerated subsets of corrupted players as well as the subsets of players who can sign a message are defined according to their cardinality.
We propose a framework that is more general than the threshold one, considering a general access structure of players allowed to sign and a general family of dishonest players that the scheme can tolerate. If these general structures satisfy some combinatorial conditions, we can design a distributed and secure RSA signature scheme for this setting. Our construction is based on the threshold scheme of Shoup.

2002

EPRINT

Secret sharing schemes with three or four minimal qualified subsets
Abstract

In this paper we study secret sharing schemes whose access structure
has three or four minimal qualified subsets. The ideal case is
completely characterized and for the non-ideal case
we provide bounds on the optimal information rate.

2002

EPRINT

Secret sharing schemes on access structures with intersection number equal to one
Abstract

The characterization of ideal access structures and
the search for bounds on the optimal information rate
are two important problems in secret sharing.
These problems are studied in this paper for access structures
with intersection number equal to one, that is, access structures
such that there is at most one participant in the intersection
of any two different minimal qualified subsets.
The main result in this work is the complete characterization
of the ideal access structures with intersection number equal to one.
Besides, bounds on the optimal information rate
are provided for the non-ideal case.

2002

EPRINT

A Distributed and Computationally Secure Key Distribution Scheme
Abstract

In 1999, Naor, Pinkas and Reingold introduced schemes in which some groups of servers distribute keys among a set of users in a
distributed way. They gave some specific proposals both in the unconditional and in the computational security framework. Their computationally secure
scheme is based on the Decisional Diffie-Hellman Assumption. This model assumes secure communication between users and servers. Furthermore it
requires users to do some expensive computations in order to obtain a key.
In this paper we modify the model introduced by Naor et al., requiring authenticated channels instead of assuming the existence of secure channels. Our model makes the user's computations easier, because most computations of the protocol are carried out by servers, keeping to a more realistic situation. We propose a basic scheme, that makes use of ElGamal cryptosystem, and that fits in with this model in the case of a passive adversary. We then add zero-knowledge proofs and verifiable secret sharing to prevent from the action of an active adversary. We consider general structures (not only the threshold ones) for those subsets of servers that can provide a key to a user and for those tolerated subsets of servers that can be corrupted by the adversary. We find necessary combinatorial conditions on these structures in order to provide security to our scheme.

2001

EPRINT

A Linear Algebraic Approach to Metering Schemes
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.

2001

EPRINT

Improving the trade-off between storage and communication in broadcast encryption schemes
Abstract

The most important point in the design of broadcast encryption schemes (BESs) is obtain a good trade-off between the amount of secret information that must be stored by every user and the length of the broadcast message, which are measured, respectively, by the information rate $\rho$ and the broadcast information rate $\rho_B$. In this paper we present a simple method to combine two given BESs in order to improve the trade-off between $\rho$ and $\rho_B$ by finding BESs with good information rate $\rho$ for arbitrarily many different values of the broadcast information rate $\rho_B$. We apply this technique to threshold $(R,T)$-BESs and we present a method to obtain, for every rational value $1/R \le \rho_B \le 1$, a $(R,T)$-BES with optimal information rate $\rho$ among all $(R,T)$-BESs that can be obtained by combining two of the $(R,T)$-BESs proposed by Blundo et al.

2001

EPRINT

Linear broadcast encryption schemes
Abstract

A new family of broadcast encryption schemes (BESs), which will be called linear broadcast encryption schemes (LBESs), is presented in this paper by using linear algebraic techniques. This family generalizes most previous proposals and provide a general framework to the study of broadcast encryption schemes. We present a method to construct LBESs for a general specification structure in order to find schemes that fit in situations that have not been considered before.

#### Program Committees

- Asiacrypt 2019
- TCC 2012
- Eurocrypt 2005
- Asiacrypt 2003

#### Coauthors

- Amos Beimel (2)
- Aner Ben-Efraim (1)
- Carlo Blundo (1)
- Ronald Cramer (7)
- Vanesa Daza (3)
- Yevgeniy Dodis (2)
- Oriol Farràs (8)
- Serge Fehr (2)
- Ignacio Gracia (5)
- Torben Hansen (2)
- Javier Herranz (2)
- Tarik Kaced (3)
- Eike Kiltz (1)
- Gregor Leander (2)
- Noam Livne (1)
- S. Mart?n (1)
- Jaume Martí-Farré (9)
- Barbara Masucci (1)
- Sebastià Martín Molleví (4)
- Paz Morillo (1)
- Germán Sáez (3)
- Ilya Tyomkin (1)
- Jorge Jiménez Urroz (2)
- Daniel Wichs (2)
- Chaoping Xing (3)
- An Yang (2)