## CryptoDB

### Javier Herranz

#### Affiliation: Universitat Politecnica de Catalunya

#### Publications

**Year**

**Venue**

**Title**

2019

ASIACRYPT

Structure-Preserving and Re-randomizable RCCA-Secure Public Key Encryption and Its Applications
Abstract

Re-randomizable RCCA-secure public key encryption (Rand-RCCA PKE) schemes reconcile the property of re-randomizability of the ciphertexts with the need of security against chosen-ciphertexts attacks. In this paper we give a new construction of a Rand-RCCA PKE scheme that is perfectly re-randomizable. Our construction is structure-preserving, can be instantiated over Type-3 pairing groups, and achieves better computation and communication efficiency than the state of the art perfectly re-randomizable schemes (e.g., Prabhakaran and Rosulek, CRYPTO’07). Next, we revive the Rand-RCCA notion showing new applications where our Rand-RCCA PKE scheme plays a fundamental part: (1) We show how to turn our scheme into a publicly-verifiable Rand-RCCA scheme; (2) We construct a malleable NIZK with a (variant of) simulation soundness that allows for re-randomizability; (3) We propose a new UC-secure Verifiable Mix-Net protocol that is secure in the common reference string model. Thanks to the structure-preserving property, all these applications are efficient. Notably, our Mix-Net protocol is the most efficient universally verifiable Mix-Net (without random oracle) where the CRS is an uniformly random string of size independent of the number of senders. The property is of the essence when such protocols are used in large scale.

2014

PKC

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.

2008

EPRINT

Restricted Adaptive Oblivious Transfer
Abstract

In this work we consider the following primitive, that we call {\it restricted adaptive oblivious transfer}. On the one hand, the owner of a database wants to restrict the access of users to this data according to some policy, in such a way that a user can only obtain information satisfying the restrictions imposed by the owner. On the other hand, a legitimate user wants to privately retrieve allowed parts of the data, in a sequential and adaptive way, without letting the owner know which part of the data is being obtained.
After having formally described the components and required properties of a protocol for restricted adaptive oblivious transfer, we propose two schemes to realize this primitive. The first one is only of theoretical interest at the current time, because it uses a cryptographic tool which has not been realized yet: cryptosystems which are both multiplicatively and additively homomorphic. The second scheme, fully implementable, is based on secret sharing schemes.

2008

EPRINT

Additive Homomorphic Encryption with t-Operand Multiplications
Abstract

Homomorphic encryption schemes are an essential ingredient to design protocols where different users interact in order to obtain some information from the others, at the same time that each user keeps private some of his information. When the algebraic structure underlying these protocols is complicated, then standard homomorphic encryption schemes are not enough, because they do not allow to crypto-compute at the same time additions and products of plaintexts.
In this work we define a theoretical object, $t$-chained encryption schemes, which can be used to design crypto-computers for the addition and product of $t$ integer values. Previous solutions in the literature worked for the case $t=2$. Our solution is not only theoretical: we show that some existing (pseudo-)homomorphic encryption schemes (some of them based on lattices) can be used to implement in practice the concept of $t$-chained encryption scheme.

2007

EPRINT

CCA2-Secure Threshold Broadcast Encryption with Shorter Ciphertexts
Abstract

In a threshold broadcast encryption scheme, a sender chooses (ad-hoc) a set of $n$ receivers and a threshold $t$, and then encrypts a message by using the public keys of all the receivers, in such a way that the original plaintext can be recovered only if at least $t$ receivers cooperate. Previously proposed threshold broadcast encryption schemes have ciphertexts whose length is $\O(n)$.
In this paper, we propose new schemes, for both PKI and identity-based scenarios, where the ciphertexts' length is $\O(n-t)$. The construction uses secret sharing techniques and the Canetti-Halevi-Katz transformation to achieve chosen-ciphertext security. The security of our schemes is formally proved under the Decisional Bilinear Diffie-Hellman (DBDH) Assumption.

2006

EPRINT

The Kurosawa-Desmedt Key Encapsulation is not Chosen-Ciphertext Secure
Abstract

At CRYPTO 2004, Kurosawa and Desmedt presented a hybrid public-key encryption scheme that is chosen-ciphertext secure in the standard model. Until now it was unknown if the key-encapsulation part of the Kurosawa-Desmedt scheme by itself is still chosen-ciphertext secure or not. In this short note we answer this question to the negative, namely we present a simple chosen-ciphertext attack on the Kurosawa-Desmedt key encapsulation mechanism.

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.

2006

EPRINT

KEM/DEM: Necessary and Sufficient Conditions for Secure Hybrid Encryption
Abstract

The KEM/DEM hybrid encryption paradigm combines the efficiency and large message space of secret key encryption with the advantages of public key cryptography. Due to its simplicity and flexibility, the approach has ever since gained increased popularity and has been successfully adapted in encryption standards.
In hybrid public key encryption (PKE), first a key encapsulation mechanism (KEM) is used to fix a random session key that is then fed into a highly efficient data encapsulation mechanism (DEM) to encrypt the actual message. A composition theorem states that if both the KEM and the DEM have the highest level of security (i.e. security against chosen-ciphertext attacks), then so does the hybrid PKE scheme. It is not known if these strong security requirements on the KEM and DEM are also neccessary, nor if such general composition theorems exist for weaker levels of security. In this work we study neccessary and sufficient conditions on the security of the KEM and the DEM in order to guarantee a hybrid PKE scheme with a certain given level of security. More precisely, using nine different security notions for KEMs, ten for DEMs, and six for PKE schemes we completely characterize which combinations lead to a secure hybrid PKE scheme (by proving a composition theorem) and which do not (by providing counterexamples).
Furthermore, as an independent result, we revisit and extend prior work on the relation among security notions for KEMs and DEMs.

2005

EPRINT

Deterministic Identity-Based Signatures for Partial Aggregation
Abstract

Aggregate signatures are a useful primitive which allows to aggregate into a single and constant-length signature many signatures on different messages computed by different users. Specific proposals of aggregate signature schemes exist only for PKI-based scenarios. For identity-based scenarios, where public keys of the users are directly derived from their identities, the signature schemes proposed up to now do not seem to allow constant-length aggregation.
We provide an intermediate solution to this problem, by designing a new identity-based signature scheme which allows aggregation when the signatures to be aggregated come all from the same signer. The new scheme is deterministic and enjoys some better properties than the previous proposals. We formally prove that the scheme is unforgeable, in the random oracle model, assuming that the Computational co-Diffie-Hellman problem is hard to solve.

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

- Fabrice Benhamouda (1)
- Vanesa Daza (4)
- Alex Escala (1)
- Antonio Faonio (1)
- Dario Fiore (1)
- Philippe Gaborit (2)
- David Galindo (1)
- Dennis Hofheinz (2)
- Marc Joye (1)
- Eike Kiltz (3)
- Fabien Laguillaumie (1)
- Benoît Libert (2)
- Carlos AGUILAR MELCHOR (2)
- Paz Morillo (1)
- Carles Padró (2)
- Carla Ràfols (4)
- Germán Sáez (11)