Catálogo de publicaciones - libros

Compartir en
redes sociales


Advances in Cryptology: CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, California, USA, August 14-18, 2005, Proceedings

Victor Shoup (eds.)

En conferencia: 25º Annual International Cryptology Conference (CRYPTO) . Santa Barbara, CA, USA . August 14, 2005 - August 18, 2005

Resumen/Descripción – provisto por la editorial

No disponible.

Palabras clave – provistas por la editorial

Coding and Information Theory; Data Encryption; Computer Communication Networks; Operating Systems; Discrete Mathematics in Computer Science; Computers and Society

Disponibilidad
Institución detectada Año de publicación Navegá Descargá Solicitá
No detectada 2005 SpringerLink

Información

Tipo de recurso:

libros

ISBN impreso

978-3-540-28114-6

ISBN electrónico

978-3-540-31870-5

Editor responsable

Springer Nature

País de edición

Reino Unido

Fecha de publicación

Información sobre derechos de publicación

© Springer-Verlag Berlin Heidelberg 2005

Tabla de contenidos

Efficient Collision Search Attacks on SHA-0

Xiaoyun Wang; Hongbo Yu; Yiqun Lisa Yin

In this paper, we present new techniques for collision search in the hash function SHA-0. Using the new techniques, we can find collisions of the full 80-step SHA-0 with complexity less than 2^39 hash operations.

Palabras clave: Hash functions; Collision search attacks; SHA-0; SHA-1.

Pp. 1-16

Finding Collisions in the Full SHA-1

Xiaoyun Wang; Yiqun Lisa Yin; Hongbo Yu

In this paper, we present new collision search attacks on the hash function SHA-1. We show that collisions of SHA-1 can be found with complexity less than 2^69 hash operations. This is the first attack on the full 80-step SHA-1 with complexity less than the 2^80 theoretical bound.

Palabras clave: Hash functions; collision search attacks; SHA-1; SHA-0.

Pp. 17-36

Pebbling and Proofs of Work

Cynthia Dwork; Moni Naor; Hoeteck Wee

We investigate methods for providing easy-to-check proofs of computational effort. Originally intended for discouraging spam, the concept has wide applicability as a method for controlling denial of service attacks. Dwork, Goldberg, and Naor proposed a specific memory-bound function for this purpose and proved an asymptotically tight amortized lower bound on the number of memory accesses any polynomial time bounded adversary must make. Their function requires a large random table which, crucially, cannot be compressed. We answer an open question of Dwork et al. by designing a compact representation for the table. The paradox, compressing an incompressible table, is resolved by embedding a time/space tradeoff into the process for constructing the table from its representation.

Palabras clave: Hash Function; Memory Access; Main Memory; Random Oracle; Cache Size.

Pp. 37-54

Composition Does Not Imply Adaptive Security

Krzysztof Pietrzak

We study the question whether the sequential or parallel composition of two functions, each indistinguishable from a random function by non-adaptive distinguishers is secure against adaptive distinguishers. The sequential composition of F $(\centerdot)$ and G $(\centerdot)$ is the function G ( F ( $\centerdot$ )), the parallel composition is F $(\centerdot) \bigstar$ G $(\centerdot)$ where ⋆ is some group operation. It has been shown that composition indeed gives adaptive security in the information theoretic setting, but unfortunately the proof does not translate into the more interesting computational case. In this work we show that in the computational setting composition does not imply adaptive security: If there is a prime order cyclic group where the decisional Diffie-Hellman assumption holds, then there are functions F and G which are indistinguishable by non-adaptive polynomially time-bounded adversaries, but whose parallel composition can be completely broken (i.e. we recover the key) with only three adaptive queries. We give a similar result for sequential composition. Interestingly, we need a standard assumption from the asymmetric (aka. public-key) world to prove a negative result for symmetric (aka. private-key) systems.

Palabras clave: Sequential Composition; Parallel Composition; Pseudorandom Function; Adaptive Query; Adaptive Security.

Pp. 55-65

On the Discrete Logarithm Problem on Algebraic Tori

R. Granger; F. Vercauteren

Using a recent idea of Gaudry and exploiting rational representations of algebraic tori, we present an index calculus type algorithm for solving the discrete logarithm problem that works directly in these groups. Using a prototype implementation, we obtain practical upper bounds for the difficulty of solving the DLP in the tori $T_2(\mathbb{F}_{p^m})$ and $T_6(\mathbb{F}_{p^m})$ for various p and m . Our results do not affect the security of the cryptosystems LUC, XTR, or CEILIDH over prime fields. However, the practical efficiency of our method against other methods needs further examining, for certain choices of p and m in regions of cryptographic interest.

Palabras clave: Discrete Logarithm; Discrete Logarithm Problem; Compression Factor; Cyclotomic Polynomial; Cryptology ePrint Archive.

Pp. 66-85

A Practical Attack on a Braid Group Based Cryptographic Protocol

Alexei Myasnikov; Vladimir Shpilrain; Alexander Ushakov

In this paper we present a practical heuristic attack on the Ko, Lee et al. key exchange protocol introduced at Crypto 2000 [11]. Using this attack, we were able to break the protocol in about 150 minutes with over 95% success rate for typical parameters. One of the ideas behind our attack is using Dehornoy’s handle reduction method as a counter measure to diffusion provided by the Garside normal form, and as a tool for simplifying braid words. Another idea employed in our attack is solving the decomposition problem in a braid group rather than the conjugacy search problem .

Pp. 86-96

The Conditional Correlation Attack: A Practical Attack on Bluetooth Encryption

Yi Lu; Willi Meier; Serge Vaudenay

Motivated by the security of the nonlinear filter generator, the concept of correlation was previously extended to the conditional correlation, that studied the linear correlation of the inputs conditioned on a given (short) output pattern of some specific nonlinear function. Based on the conditional correlations, conditional correlation attacks were shown to be successful and efficient against the nonlinear filter generator. In this paper, we further generalize the concept of conditional correlations by assigning it with a different meaning, i.e. the correlation of the output of an arbitrary function conditioned on the unknown (partial) input which is uniformly distributed. Based on this generalized conditional correlation, a general statistical model is studied for dedicated key-recovery distinguishers. It is shown that the generalized conditional correlation is no smaller than the unconditional correlation. Consequently, our distinguisher improves on the traditional one (in the worst case it degrades into the traditional one). In particular, the distinguisher may be successful even if no ordinary correlation exists. As an application, a conditional correlation attack is developed and optimized against Bluetooth two-level E0. The attack is based on a recently detected flaw in the resynchronization of E0, as well as the investigation of conditional correlations in the Finite State Machine (FSM) governing the keystream output of E0. Our best attack finds the original encryption key for two-level E0 using the first 24 bits of 2^23.8 frames and with 2^38 computations. This is clearly the fastest and only practical known-plaintext attack on Bluetooth encryption compared with all existing attacks. Current experiments confirm our analysis.

Palabras clave: Stream Ciphers; Correlation; Bluetooth; E0.

Pp. 97-117

Unconditional Characterizations of Non-interactive Zero-Knowledge

Rafael Pass; abhi shelat

Non-interactive zero-knowledge (NIZK) proofs have been investigated in two models: the Public Parameter model and the Secret Parameter model . In the former, a public string is “ideally” chosen according to some efficiently samplable distribution and made available to both the Prover and Verifier. In the latter, the parties instead obtain correlated (possibly different) private strings. To add further choice, the definition of zero-knowledge in these settings can either be non-adaptive or adaptive . In this paper, we obtain several unconditional characterizations of computational, statistical and perfect NIZK for all combinations of these settings. Specifically, we show: In the secret parameter model, NIZK = NISZK = NIPZK = AM . In the public parameter model, – for the non-adaptive definition, NISZK ⊆ AM ∩ coAM , – for the adaptive one, it also holds that NISZK ⊂ BPP , – for computational NIZK for “hard” languages, one-way functions are both necessary and sufficient . From our last result, we arrive at the following unconditional characterization of computational NIZK in the public parameter model (which complements well-known results for interactive zero-knowledge): Either NIZK proofs exist only for “easy” languages (i.e., languages that are not hard-on-average), or they exist for all of AM (i.e., all languages which admit non-interactive proofs).

Palabras clave: Proof System; Oblivious Transfer; Public Parameter; Prover Algorithm; Proof String.

Pp. 118-134

Impossibility and Feasibility Results for Zero Knowledge with Public Keys

Joël Alwen; Giuseppe Persiano; Ivan Visconti

In this paper, we continue the study of the round complexity of black-box zero knowledge in the bare public-key ( BPK , for short) model previously started by Micali and Reyzin in [11]. Specifically we show the impossibility of 3-round concurrent (and thus resettable) black-box zero-knowledge argument systems with sequential soundness for non-trivial languages. In light of the previous state-of-the-art, our result completes the analysis of the round complexity of black-box zero knowledge in the BPK model with respect to the notions of soundness and black-box zero knowledge. Further we give sufficient conditions for the existence of a 3-round resettable zero-knowledge proof (in contrast to argument) system with concurrent soundness for $\mathcal{NP}$ in the upperbounded public-key model introduced in [14].

Palabras clave: False Statement; Feasibility Result; Argument System; Input Tape; Overwhelming Probability.

Pp. 135-151

Communication-Efficient Non-interactive Proofs of Knowledge with Online Extractors

Marc Fischlin

We show how to turn three-move proofs of knowledge into non-interactive ones in the random oracle model. Unlike the classical Fiat-Shamir transformation our solution supports an online extractor which outputs the witness from such a non-interactive proof instantaneously, without having to rewind or fork. Additionally, the communication complexity of our solution is significantly lower than for previous proofs with online extractors. We furthermore give a superlogarithmic lower bound on the number of hash function evaluations for such online extractable proofs, matching the number in our construction, and we also show how to enhance security of the group signature scheme suggested recently by Boneh, Boyen and Shacham with our construction.

Palabras clave: Hash Function; Signature Scheme; Random Oracle; Random Oracle Model; Group Signature Scheme.

Pp. 152-168