Catálogo de publicaciones - libros

The book was inadvertently published with an incorrect name of the copyright holder. The name of the copyright holder for this book is: © Springer-Verlag Berlin Heidelberg. The book has been updated with the changes.

Let be an element of prime order in an abelian group and . We show that if , , and are given for a positive divisor of –1, we can compute the secret in group operations using memory. If (=0,1,2,..., ) are provided for a positive divisor of +1, can be computed in group operations using memory. This implies that the strong Diffie-Hellman problem and its related problems have computational complexity reduced by from that of the discrete logarithm problem for such primes.

Further we apply this algorithm to the schemes based on the Diffie-Hellman problem on an abelian group of prime order . As a result, we reduce the complexity of recovering the secret key from to for Boldyreva’s blind signature and the original ElGamal scheme when –1 (resp. +1) has a divisor ≤ (resp. ≤) and signature or decryption queries are allowed.

Despite well-known results in theoretical cryptography highlighting the vulnerabilities of unauthenticated encryption, the IPsec standards mandate its support. We present evidence that such “encryption-only” configurations are in fact still often selected by users of IPsec in practice, even with strong warnings advising against this in the IPsec standards. We then describe a variety of attacks against such configurations and report on their successful implementation in the case of the Linux kernel implementation of IPsec. Our attacks are realistic in their requirements, highly efficient, and recover the complete contents of IPsec-protected datagrams. Our attacks still apply when integrity protection is provided by a higher layer protocol, and in some cases even when it is supplied by IPsec itself.

The Isomorphism of Polynomials (IP) [28], which is the main concern of this paper, originally corresponds to the problem of recovering the secret key of a C scheme [26]. Besides, the security of various other schemes (signature, authentication [28], traitor tracing [5], ...) also depends on the practical hardness of IP. Due to its numerous applications, the Isomorphism of Polynomials is thus one of the most fundamental problems in multivariate cryptography. In this paper, we address two complementary aspects of IP, namely its theoretical and practical difficulty. We present an upper bound on the theoretical complexity of “IP-like” problems, i.e. a problem consisting in recovering a particular transformation between two sets of multivariate polynomials. We prove that these problems are not NP-Hard (provided that the polynomial hierarchy does not collapse). Concerning the practical aspect, we present a new algorithm for solving IP. In a nutshell, the idea is to generate a suitable algebraic system of equations whose zeroes correspond to a solution of IP. From a practical point of view, we employed a fast Gröbner basis algorithm, namely F [17], for solving this system. This approach is efficient in practice and obliges to modify the current security criteria for IP. We have indeed broken several challenges proposed in literature [28, 29, 5]. For instance, we solved a challenge proposed by O. Billet and H. Gilbert at Asiacrypt’03 [5] in less than one second.

This talk illustrates the everyday challenges met by embedded security practitioners by five real examples. All the examples were actually encountered while designing, developing or evaluating commercial products.

This note, which is not a refereed research paper, presents the details of one of these five examples. It is intended to help the audience follow that part of our presentation.

Motivated by the representation of biometric and multimedia objects, we consider the problem of hiding noisy point-sets using a secure sketch. A point-set consists of points from a -dimensional discrete domain [0, – 1]. Under permissible noises, for every point , each may be perturbed by a value of at most . In addition, at most points in may be replaced by other points in [0, – 1]. Given an original , we want to compute a secure sketch . A known method constructs the sketch by adding a set of random points , and the description of (∪) serves as part of the sketch. However, the dependencies among the random points are difficult to analyze, and there is no known non-trivial bound on the entropy loss. In this paper, we first give a general method to generate and show that the entropy loss of (∪) is at most (logΔ+ + 0.443), where Δ= 2+1. We next give improved schemes for = 1, and special cases for = 2. Such improvements are achieved by pre-rounding, and careful partition of the domains into cells. It is possible to make our sketch short, and avoid using randomness during construction. We also give a method in = 1 to demonstrate that, using the size of as the security measure would be misleading.

Juels andWeis (building on prior work of Hopper and Blum) propose and analyze two shared-key authentication protocols - HB and HB - whose extremely low computational cost makes them attractive for low-cost devices such as radio-frequency identification (RFID) tags. Security of these protocols is based on the conjectured hardness of the “learning parity with noise” (LPN) problem: the HB protocol is proven secure against a passive (eavesdropping) adversary, while the HB protocol is proven secure against active attacks.

Juels and Weis prove security of these protocols only for the case of executions, and explicitly leave open the question of whether security holds also in the case of or executions. In addition to guaranteeing security against a stronger class of adversaries, a positive answer to this question would allow the HB protocol to be parallelized, thereby substantially reducing its round complexity.

Adapting a recent result by Regev, we answer the aforementioned question in the affirmative and prove security of the HB and HB+ protocols under parallel/concurrent executions. We also give what we believe to be substantially security proofs for these protocols which are more in that they explicitly address the dependence of the soundness error on the number of iterations.

We propose simple, realistic protocols for polling that allow the responder to plausibly repudiate his response, while at the same time allow accurate statistical analysis of poll results. The protocols use simple physical objects (envelopes or scratch-off cards) and can be performed without the aid of computers. One of the main innovations of this work is the use of techniques from theoretical cryptography to rigorously prove the security of a realistic, physical protocol. We show that, given a few properties of physical envelopes, the protocols are unconditionally secure in the universal composability framework.

We introduce a practical stream cipher with provable security named QUAD. The cipher relies on the iteration of a multivariate quadratic system of equations in < unknowns over a finite field. The security of the keystream generation of QUAD is provably reducible to the conjectured intractability of the MQ problem, namely solving a multivariate system of quadratic equations. Our recommended version of QUAD uses a 80-bit key, 80-bit IV and an internal state of = 160 bits. It outputs 160 keystream bits ( = 320) at each iteration until 2 bits of keystream have been produced.

Sequence compression is one of the most promising tools for strengthening pseudo-random generators used in stream ciphers. Indeed, adding compression components can thwart algebraic attacks aimed at LFSR-based stream ciphers. Among such components are the Shrinking Generator and the Self-Shrinking Generator, as well as recent variations on Bit-Search-based decimation. We propose a general model for compression used to strengthen pseudo-random sequences. We show that there is a unique (up to length-preserving permutations) construction that reaches an optimal trade-off between output rate and security against several attacks.