International Association
for Cryptologic Research

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.