## CryptoDB

### Germán Sáez

#### Affiliation: UPC

#### Publications

**Year**

**Venue**

**Title**

2008

EPRINT

Flaws in Some Efficient Self-Healing Key Distribution Schemes with Revocation
Abstract

Dutta and Mukhopadhyay have recently proposed some very efficient
self-healing key distribution schemes with revocation. The
parameters of these schemes contradict some results (lower bounds)
presented by Blundo et al. In this paper different attacks against
the schemes of Dutta and Mukhopadhyay are explained: one of them
can be easily avoided with a slight modification in the schemes,
but the other one is really serious. The conclusion is that the
results of Dutta and Mukhopadhyay are wrong.

2006

EPRINT

New Results on Multipartite Access Structures
Abstract

In a multipartite access structure, the set of players is divided
into $K$ different entities, in such a way that all players of the same entity play the same role in the structure. Not many results are known about these structures, when $K \geq 3$.
Even if the total characterization of ideal multipartite access structures seems a very ambitious goal, we take a first step in this direction. On the one hand, we detect some conditions that directly imply that a multipartite structure cannot be ideal. On the other hand, we prove that three wide families of multipartite access structures are ideal. We believe that the techniques employed in these proofs are so general that they could be used to prove in the future more general results related to the characterization of ideal multipartite access structures.

2004

EPRINT

Distributed Ring Signatures for Identity-Based Scenarios
Abstract

In a ring signature scheme, a signer in a subset (or {\it ring})
of potential signers produces a signature of a message in such a
way that the receiver can verify that the signature comes from a
member of the ring, but cannot know which member has actually
signed.
In this work, we extend this concept to that of distributed ring
signatures, where a subset of users cooperate to compute a
distributed anonymous signature on a message, on behalf of a
family of subsets. We propose two schemes, one for general
families of subsets, and a more efficient one for threshold
families of subsets. The security of both proposals is formally
proved, assuming the hardness of the Computational Diffie-Hellman
problem.
Our two schemes run in an identity-based scenario, where public
keys of the users can be derived from their identities. This fact
avoids the necessity of digital certificates, and therefore allows
more efficient implementations of such systems.

2004

EPRINT

New Distributed Ring Signatures for General Families of Signing Subsets
Abstract

In a distributed ring signature scheme, a subset of users
cooperate to compute a distributed anonymous signature on a
message, on behalf of a family of possible signing subsets. The
receiver can verify that the signature comes from a subset of the
ring, but he cannot know which subset has actually signed.
In this work we use the concept of dual access structures to
construct a distributed ring signature scheme which works with
general families of possible signing subsets. The length of each
signature is linear on the number of involved users, which is
desirable for some families with many possible signing subsets.
The scheme achieves the desired properties of correctness,
anonymity and unforgeability. The reduction in the proof of
unforgeability is tighter than the reduction in the previous
proposals which work with general families.
We analyze the case in which our scheme runs in an identity-based
scenario, where public keys of the users can be derived from their
identities. This fact avoids the necessity of digital
certificates, and therefore allows more efficient implementations
of such systems. But our scheme can be extended to work in more
general scenarios, where users can have different types of keys.

2003

EPRINT

Forking Lemmas in the Ring Signatures' Scenario
Abstract

Pointcheval and Stern introduced in 1996 some forking lemmas useful to prove the security of a family of digital signature schemes. This family includes, for example, Schnorr's scheme and a modification of ElGamal signature scheme.
In this work we generalize these forking lemmas to the ring signatures' scenario. In a ring signature scheme, a signer in a subset (or {\it ring}) of potential signers produces a signature of a message in such a way that the receiver can verify that the signature comes from a member of the ring, but cannot know which member has actually signed.
We propose a new ring signature scheme, based on Schnorr signature scheme, which provides unconditional anonymity. We use the generalized forking lemmas to prove that this scheme is existentially unforgeable under adaptive chosen-message attacks, in the random oracle model.

2003

EPRINT

Revisiting fully distributed proxy signature schemes
Abstract

In a proxy signature scheme, a potential signer delegates his
capabilities to a proxy signer, who can sign documents on behalf of
him. The recipient of the signature verifies both identities: that of
the delegator and that of the proxy signer. There are many proposals
of proxy signature schemes, but security of them has not been considered
in a formal way until the appearance of the work by Boldyreva et al.
If the entities which take part in a proxy signature scheme are formed
by sets of participants, then we refer to it as a fully distributed
proxy signature scheme.
In this work, we extend the security definitions introduced by
Boldyreva et al. to the scenario of fully distributed proxy signature
schemes, and we propose a specific scheme which is secure in this new
model.

2003

EPRINT

A provably secure ID-based ring signature scheme
Abstract

Identity-based (ID) cryptosystems avoid the necessity of certificates to authenticate public keys
in a digital communications system. This is desirable, specially for these applications which
involve a large number of public keys in each execution. For example, any computation and
verification of a ring signature scheme, where a user anonymously signs a message on behalf of a
set of users including himself, requires to authenticate the public keys of all the members of the
set.
We use bilinear pairings to design a new ID-based ring signature scheme. We extend to the
ID-based scehario some known results about the security of generic ring signature schemes.
This allows us to formally prove the security of our scheme, under the assumption that the
Computational Diffie-Hellman problem is hard to solve.

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

Fully Distributed Proxy Signature Schemes
Abstract

In a proxy signature scheme, a potential signer delegates his signing capability to a proxy entity, who signs a message on behalf of the original signer. All the proposals of proxy signature schemes made until now have been based on Schnorr's signature scheme. Threshold versions of these schemes have also been proposed, in which the power of the proxy signer is distributed among a group of players, in such a way that any subset with a minimum number (threshold) of players can sign a message on behalf of the original signer.
We consider a model that is fully distributed, because we want to distribute not only the power of the proxy signer, but also the original signer ability to delegate his signing capability. Furthermore, we consider general structures, instead of only the threshold ones, for both the tolerated subsets of dishonest players and the subsets of honest players authorized to execute a valid instance of the protocol, and in both the original and the proxy signer entities. We find sufficient combinatorial conditions that these structures must satisfy in order to design a fully distributed, secure and robust proxy signature scheme for this general scenario.
We propose such a scheme for this setting. It is also based on Schnorr's signature scheme.

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.

2002

EPRINT

Some Applications of Threshold Signature Schemes to Distributed Protocols
Abstract

In a threshold signature scheme, a group of players share a secret information in such a way that only those subsets with a minimum number of players can compute a valid signature. We propose methods to construct some useful and computationally secure distributed protocols from threshold signature schemes satisfying some suitable properties.
Namely, we prove that any threshold signature scheme which is non-interactive can be used to construct a metering scheme. We also design a distributed key distribution scheme from any deterministic threshold signature scheme. The security of these news schemes is reduced to the security of the corresponding threshold signature schemes. Furthermore, the constructed protocols reach some desirable properties.

#### Coauthors

- Vanesa Daza (3)
- Javier Herranz (11)
- Carles Padró (3)