Catálogo de publicaciones - libros

Recent work by Krawczyk [12] and Menezes [16] has highlighted the importance of understanding well the guarantees and limitations of formal security models when using them to prove the security of protocols. In this paper we focus on security models for authenticated key exchange (AKE) protocols. We observe that there are several classes of attacks on AKE protocols that lie outside the scope of the Canetti-Krawczyk model. Some of these additional attacks have already been considered by Krawczyk [12]. In an attempt to bring these attacks within the scope of the security model we extend the Canetti-Krawczyk model for AKE security by providing significantly greater powers to the adversary. Our contribution is a more compact, integrated, and comprehensive formulation of the security model. We then introduce a new AKE protocol called NAXOS and prove that it is secure against these stronger adversaries.

We study the multicast stream authentication problem when an opponent can drop, reorder and inject data packets into the communication channel. In this context, bandwidth limitation and fast authentication are the core concerns. Therefore any authentication scheme is to reduce as much as possible the packet overhead and the time spent at the receiver to check the authenticity of collected elements. Recently, Tartary and Wang developed a provably secure protocol with small packet overhead and a reduced number of signature verifications to be performed at the receiver.

In this paper, we propose an hybrid scheme based on Tartary and Wang’s approach and Merkle hash trees. Our construction will exhibit a smaller overhead and a much faster processing at the receiver making it even more suitable for multicast than the earlier approach. As Tartary and Wang’s protocol, our construction is provably secure and allows the total recovery of the data stream despite erasures and injections occurred during transmission.

In a threshold broadcast encryption scheme, a sender chooses (ad-hoc) a set of receivers and a threshold , 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 receivers cooperate. Previously proposed threshold broadcast encryption schemes have ciphertexts whose length is at least . In this paper, we propose new schemes, for both PKI and identity-based scenarios, where the ciphertexts’ length is . The constructions use 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.

We describe a hybrid hierarchical identity based encryption (HIBE) protocol which is secure in the full model without using the random oracle heuristic and whose security is based on the computational hardness of the decisional bilinear Diffie-Hellman (DBDH) problem. The new protocol is obtained by augmenting a previous construction of a HIBE protocol which is secure against chosen plaintext attacks (CPA-secure). The technique for answering decryption queries in the proof is based on earlier work by Boyen-Mei-Waters. Ciphertext validity testing is done indirectly through a symmetric authentication algorithm in a manner similar to the Kurosawa-Desmedt public key encryption protocol. Additionally, we perform symmetric encryption and authentication by a single authenticated encryption algorithm. A net result of all these is that our construction improves upon previously known constructions in the same setting.

Unforgeability of digital signatures is closely related to the security of hash functions since hashing messages, such as paradigm, is necessary in order to sign (arbitrarily) long messages. Recent successful collision finding attacks against practical hash functions would indicate that constructing practical collision resistant hash functions is difficult to achieve. Thus, it is worth considering to relax the requirement of collision resistance for hash functions that is used to hash messages in signature schemes. Currently, the most efficient strongly unforgeable signature scheme in the standard model which is based on the CDH assumption (in bilinear groups) is the Boneh-Shen-Waters (BSW) signature proposed in 2006. In their scheme, however, a collision resistant hash function is necessary to prove its security. In this paper, we construct a signature scheme which has the same properties as the BSW scheme but does not rely on collision resistant hash functions. Instead, we use a target collision resistant hash function, which is a strictly weaker primitive than a collision resistant hash function. Our scheme is, in terms of the signature size and the computational cost, as efficient as the BSW scheme.

We discuss two common pitfalls found in proofs of security of various certificateless signature (CLS) schemes. As a result of the first observation, we are able to show that a CLS scheme ([Goy06]), previously thought to be secure, is vulnerable to a key replacement attack. We then proceed to define a class of CLS schemes whose security is provable by standard techniques, leading to a more efficient version of a known CLS scheme ([ARP03]) and a (previously unknown) security proof for another ([LCS05]).

Ring signature is a kind of group-oriented signature. It allows a member of a group to sign messages on behalf of the group without revealing his/her identity. Certificateless public key cryptography was first introduced by Al-Riyami and Paterson in Asiacrypt 2003. In certificateless cryptography, it does not require the use of certificates to guarantee the authenticity of users’ public keys. Meanwhile, certificateless cryptography does not have the key escrow problem, which seems to be inherent in the Identity-based cryptography. In this paper, we introduce the notion of ring signature into certificateless public key cryptography and propose a concrete certificateless ring signature scheme. The security models of certificateless ring signature are also formalized. Our new scheme is provably secure in the random oracle model, with the assumption that the Computational Diffie-Hellman problem is hard.

Since 1985 and their introduction by Goldwasser, Micali and Rackoff, followed in 1988 by Feige, Fiat and Shamir, zero-knowledge proofs of knowledge have become a central tool in modern cryptography. Many articles use them as building blocks to construct more complex protocols, for which security is often hard to prove. The aim of this paper is to simplify analysis of many of these protocols, by providing the cryptographers with a theorem which will save them from stating explicit security proofs. Kiayias, Tsiounis and Yung made a first step in this direction at Eurocrypt’04, but they only addressed the case of so-called “triangular set of discrete-log relations”. By generalizing their result to any set of discrete-log relations, we greatly extend the range of protocols it can be applied to.

We prove that there are no black-box reductions from Collision-Free Hash Functions to secure time-stamping schemes, which means that in principle secure time-stamping schemes may exist even if there exist no collision-resistant hash functions. We show that there is an oracle relative to which there exist secure time-stamping schemes but no hash function is collision-free. The oracle we use is not new — a similar idea was already used by Simon in 1998 to show that collision-free hash functions cannot be constructed from one-way permutations in a black-box way. Our oracle contains a random hash function family and a universal collision-finder . We show that hash-tree time-stamping schemes that use as a hash function remain secure even in the presence of . From more practical view, our result is an implicit confirmation that collision-finding attacks against hash functions will tell us quite little about the security of hash-tree time-stamping schemes and that we need more dedicated research about back-dating attacks against practical hash functions.

Game-playing is an approach to write security proofs that are easy to verify. In this approach, security definitions and intractable problems are written as programs called games and reductionist security proofs are sequences of game transformations. This bias towards programming languages suggests the implementation of a tool based on compiler techniques (syntactic program transformations) to build security proofs, but it also raises the question of the soundness of such a tool. In this paper, we advocate the formalization of game-playing in a proof assistant as a tool to build security proofs. In a proof assistant, starting from just the formal definition of a probabilistic programming language, all the properties required in game-based security proofs can be proved internally as lemmas whose soundness is ensured by proof theory. Concretely, we show how to formalize the game-playing framework of Bellare and Rogaway in the Coq proof assistant, how to prove formally reusable lemmas such as the fundamental lemma of game-playing, and how to use them to formally prove the PRP/PRF Switching Lemma.