Catálogo de publicaciones - libros

We prove in a non-black-box way that every bounded list and set commitment scheme is . This is a new and rather strong security condition, which makes the security definitions for time-stamping much more natural compared to the previous definitions, which assume of adversaries. As a direct consequence, list and set commitment schemes with partial opening property are sufficient for secure time-stamping if the number of elements has an explicit upper bound . On the other hand, white-box reductions are in a sense strictly weaker than black-box reductions. Therefore, we also extend and generalize the previously known reductions. The corresponding new reductions are times more efficient, which is important for global-scale time-stamping schemes where is very large.

We describe the first efficient ring signature scheme secure, without random oracles, based on standard assumptions. Our ring signatures are based in bilinear groups. For members of a ring our signatures consist of 2 + 2 group elements and require 2 + 3 pairings to verify. We prove our scheme secure in the strongest security model proposed by Bender, Katz, and Morselli: namely, we show our scheme to be anonymous against full key exposure and unforgeable with respect to insider corruption. A shortcoming of our approach is that all the users’ keys must be defined in the same group.

The ring signature allows a signer to leak secrets anonymously, without the risk of identity escrow. At the same time, the ring signature provides great flexibility: No group manager, no special setup, and the dynamics of group choice. The ring signature is, however, vulnerable to malicious or irresponsible signers in some applications, because of its anonymity. In this paper, we propose a traceable ring signature scheme. A traceable ring scheme is a ring signature except that it can restrict “excessive” anonymity. The traceable ring signature has a that consists of a list of ring members and an that refers to, for instance, a social affair or an election. A ring member can make any signed but anonymous opinion regarding the issue, but only once (per tag). If the member submits another signed opinion, possibly pretending to be another person who supports the first opinion, the identity of the member is immediately revealed. If the member submits the same opinion, for instance, voting “yes” regarding the same issue twice, everyone can see that these two are linked. The traceable ring signature can suit to many applications, such as an anonymous voting on a BBS. We formalize the security definitions for this primitive and show an efficient and simple construction in the random oracle model.

We provide a positive result about the Fiat-Shamir (FS) transform in the standard model, showing how to use it to convert three-move identification protocols into with a proof of security that makes a standard assumption on the hash function rather than modeling it as a random oracle. The result requires security of the starting protocol against attacks. We can show that numerous protocols have the required properties and so obtain numerous efficient two-tier schemes. Our first application is a two-tier scheme based transform of any unforgeable signature scheme into a strongly unforgeable one. (This extends Boneh, Shen and Waters [8] whose transform only applies to a limited class of schemes.) The second application is new one-time signature schemes that, compared to one-way function based ones of the same computational cost, have smaller key and signature sizes.

At PKC 2006 Crutchfield, Molnar, Turner and Wagner proposed a generic threshold version of on-line/off-line signature schemes based on the “hash-sign-switch” paradigm introduced by Shamir and Tauman. Such a paradigm strongly relies on which are collision-resistant functions, with a secret trapdoor which actually allows to find arbitrary collisions efficiently. The “hash-sign-switch” paradigm works as follows. In the off-line phase, the signer hashes and signs a random message . When, during the on-line phase, he is given a message to sign the signer uses its knowledge of the hash trapdoor to find a second preimage and “switches” with the random . As shown by Crutchfield adapting this paradigm to the threshold setting is not trivial. The solution they propose introduces additional computational assumptions which turn out to be implied by the so-called one-more discrete logarithm assumption.

In this paper we present an alternative solution to the problem. As in the previous result by Crutchfield , our construction is and can be based on any threshold signature scheme, combined with a chameleon hash function based on discrete log. However we show that, by appropriately modifying the chameleon function, our scheme can be proven secure based on the traditional discrete logarithm assumption. While this produces a slight increase in the cost of the off-line phase, the efficiency of the on-line stage (the most important when optimizing signature computation) is unchanged. In other words the is essentially preserved. Finally, we show how to achieve for our scheme. Compared to the work by Crutchfield , our main solution tolerates at most (arbitrarily) malicious players instead of however we stress that we do not rely on random oracles in our proofs. Moreover we briefly present a variant which can achieve robustness in the presence of malicious players.

In the CT-track of the 2006 RSA conference, a new multivariate public key cryptosystem, which is called the Medium Field Equation (MFE) multivariate public key cryptosystem, is proposed by Wang, Yang, Hu and Lai. We use the second order linearization equation attack method by Patarin to break MFE. Given a ciphertext, we can derive the plaintext within 2-multiplications, after performing once for any given public key a computation of complexity less than 2. We also propose a high order linearization equation (HOLE) attack on multivariate public key cryptosystems, which is a further generalization of the (first and second order) linearization equation (LE). This method can be used to attack extensions of the current MFE.

Multivariate Cryptography has been an active line of research for almost twenty years. While most multivariate cryptosystems have been under attack, variations of the basic schemes came up as potential repairs. In this paper, we study the Internal Perturbation variation of HFE recently proposed by Ding and Schmidt. Although several results indicate that HFE is vulnerable against algebraic attacks for moderate size parameters, Ding and Schmidt claim that the cryptosystem with internal perturbation should be immune against them. However in this paper, we apply the recently discovered method of differential analysis to the Internal Perturbation of HFE and we find a subtle property which allows to disclose the kernel of the perturbation. Once this has been achieved, the public key can be inverted by attacking the underlying HFE provided the parameters were taken low enough to make the perturbed scheme of competitive performance.

We propose a new basic trapdoor IC (ℓ-Invertible Cycles) of the mixed field type for ultivariate uadratic public key cryptosystems. This is the first new basic trapdoor since the invention of Unbalanced Oil and Vinegar in 1997. IC can be considered an extended form of the well-known Matsumoto-Imai Scheme A (also MIA or ), and share some features of stagewise triangular systems. However IC has very distinctive properties of its own. In practice, IC is much faster than MIA, and can even match the speed of single-field schemes.

We propose a practical key encapsulation mechanism with a simple and intuitive design concept. Security against chosen-ciphertext attacks can be proved in the standard model under a new assumption, the Gap Hashed Diffie-Hellman (GHDH) assumption. The security reduction is tight and simple.

Secure key encapsulation, combined with an appropriately secure symmetric encryption scheme, yields a hybrid public-key encryption scheme which is secure against chosen-ciphertext attacks. The implied encryption scheme is very efficient: compared to the previously most efficient scheme by Kurosawa and Desmedt [Crypto 2004] it has 128 bits shorter ciphertexts, between 25-50% shorter public/secret keys, and it is slightly more efficient in terms of encryption/decryption speed. Furthermore, our scheme enjoys (the option of) public verifiability of the ciphertexts and it inherits all practical advantages of secure hybrid encryption.

Key-insulated cryptography is a crucial technique for protecting private keys. To strengthen the security of key-insulated protocols, Hanaoka, Hanaoka and Imai recently introduced the idea of parallel key-insulated encryption (PKIE) where distinct physically-secure devices (called helpers) are independently used in key updates. Their motivation was to reduce the risk of exposure for helpers by decreasing the frequency of their connections to insecure environments. Hanaoka showed that it was non-trivial to achieve a PKIE scheme fitting their model and proposed a construction based on the Boneh-Franklin identity-based encryption (IBE) scheme. The security of their system was only analyzed in the idealized random oracle model. In this paper, we provide a fairly efficient scheme which is secure in the standard model (i.e. without random oracles). To do so, we first show the existence of a relation between PKIE and the notion of aggregate signatures (AS) suggested by Boneh We then describe our random oracle-free construction using bilinear maps. Thus, our contributions are both on the concrete side, namely the first realization of parallel key-insulated encryption without the random oracle idealization, and on the conceptual side revealing the relationships between two seemingly unrelated primitives.