Catálogo de publicaciones - libros

We present a novel, automated way to find differential paths for MD5. As an application we have shown how, at an approximate expected cost of 2 calls to the MD5 compression function, for any two chosen message prefixes and ′, suffixes and ′ can be constructed such that the concatenated values || and ′||′ collide under MD5. Although the practical attack potential of this construction of is limited, it is of greater concern than random collisions for MD5. To illustrate the practicality of our method, we constructed two MD5 based X.509 certificates with identical signatures but different public keys different Distinguished Name fields, whereas our previous construction of colliding X.509 certificates required identical name fields. We speculate on other possibilities for abusing chosen-prefix collisions. More details than can be included here can be found on .

A (,ℓ)-robust combiner for collision-resistant hash-functions is a construction which from ℓ hash-functions constructs a hash-function which is collision-resistant if at least of the components are collision-resistant. One trivially gets a (,ℓ)-robust combiner by concatenating the output of any ℓ−  + 1 of the components, unfortunately this is not very practical as the length of the output of the combiner is quite large. We show that this is unavoidable as no black-box (,ℓ)-robust combiner whose output is significantly shorter than what can be achieved by concatenation exists. This answers a question of Boneh and Boyen (Crypto’06).

We provide the first proof of security for MDC-2, the most well-known construction for turning an -bit blockcipher into a 2-bit cryptographic hash function. Our result, which is in the ideal-cipher model, shows that MDC-2, when built from a blockcipher having blocklength and keylength , has security much better than that delivered by any hash function that has an -bit output. When the blocklength and keylength are  = 128 bits, as with MDC-2 based on AES-128, an adversary that asks fewer than 2 queries usually cannot find a collision.

We show an efficient secure two-party protocol, based on Yao’s construction, which provides security against malicious adversaries. Yao’s original protocol is only secure in the presence of semi-honest adversaries. Security against malicious adversaries can be obtained by applying the compiler of Goldreich, Micali and Wigderson (the “GMW compiler”). However, this approach does not seem to be very practical as it requires using generic zero-knowledge proofs.

Our construction is based on applying cut-and-choose techniques to the original circuit and inputs. Security is proved according to the ideal/real simulation paradigm, and the proof is in the standard model (with no random oracle model or common reference string assumptions). The resulting protocol is computationally efficient: the only usage of asymmetric cryptography is for running (1) oblivious transfers for each input bit (or for each bit of a statistical security parameter, whichever is larger). Our protocol combines techniques from folklore (like cut-and-choose) along with new techniques for efficiently proving consistency of inputs. We remark that a naive implementation of the cut-and-choose technique with Yao’s protocol does yield a secure protocol. This is the first paper to show how to properly implement these techniques, and to provide a full proof of security.

Our protocol can also be interpreted as a constant-round black-box reduction of secure two-party computation to oblivious transfer and perfectly-hiding commitments, or a black-box reduction of secure two-party computation to oblivious transfer alone, with a number of rounds which is linear in a statistical security parameter. These two reductions are comparable to Kilian’s reduction, which uses OT alone but incurs a number of rounds which is linear in the depth of the circuit [18].

In a recent paper Mohassel and Franklin study the efficiency of secure two-party computation in the presence of malicious behavior. Their aim is to make classical solutions to this problem, such as zero-knowledge compilation, more efficient. The authors provide several schemes which are the most efficient to date. We propose a modification to their main scheme using expanders. Our modification asymptotically improves at least one measure of efficiency of all known schemes. We also point out an error, and improve the analysis of one of their schemes.

We present an efficient construction of Yao’s “garbled circuits” protocol for securely computing any two-party circuit on committed inputs. The protocol is secure in a universally composable way in the presence of adversaries under the decisional composite residuosity (DCR) and strong RSA assumptions, in the common reference string model. The protocol requires a constant number of rounds (four-five in the standard model, two-three in the random oracle model, depending on whether both parties receive the output), (||) modular exponentiations per player, and a bandwidth of (||) group elements, where || is the size of the computed circuit.

Our technical tools are of independent interest. We propose a homomorphic, semantically secure variant of the Camenisch-Shoup verifiable cryptosystem, which uses shorter keys, is (it is infeasible to generate two keys which successfully decrypt the same ciphertext), and allows efficient proofs that a committed plaintext is encrypted under a .

Our second tool is a practical four-round (two-round in ROM) protocol for oblivious transfer on (string-COT) secure against malicious participants. The string-COT protocol takes a few exponentiations per player, and is UC-secure under the DCR assumption in the common reference string model. Previous protocols of comparable efficiency achieved either committed OT on , or standard (non-committed) OT on strings.

Protocols proven secure within the satisfy strong and desirable security properties. Unfortunately, it is known that within the “plain” model, secure computation of general functionalities without an honest majority is impossible. This has prompted researchers to propose various “setup assumptions” with which to augment the bare UC framework in order to bypass this severe negative result. Existing setup assumptions seem to inherently require trusted party (or parties) to initialize the setup in the real world.

We propose a new setup assumption — more along the lines of a assumption regarding the existence of tamper-proof hardware — which also suffices to circumvent the impossibility result mentioned above. We suggest this assumption as potentially leading to an approach that might alleviate the need for trusted parties, and compare our assumption to those proposed previously.

We present a generic construction for constant-round concurrsound resettable zero-knowledge (rZK-CS) arguments for in the bare public-key (BPK) model under any (sub-exponentially strong) one-way function (OWF), which is a traditional assumption in this area. The generic construction in turn allows round-optimal implementation for still under general assumptions, and can be converted into a highly practical instantiation (under specific number-theoretic assumptions) for any language admitting Σ-protocols. Further, the rZK-CS arguments developed in this work also satisfy a weak (black-box) concurrent knowledge-extractability property as proofs of knowledge, in which case some super-polynomial-time assumption is intrinsic.

We introduce a notion of (InstD-VRFs for short). Informally, an InstD-VRF is, in some sense, a verifiable random function [23] with a special public key, which is generated via a (possibly) protocol and contains an instance  ∈  ∩ {0,1} for a specific NP language , but the security requirements on such a function are relaxed: we only require the property when  ∈  and only require the property when  ∉ , instead of requiring both pseudorandomness and uniqueness to hold . We show that this notion can be realized under standard assumption.

Our motivation is the conjecture posed by Barak et al.[2], which states there exist resettably-sound resettable zero knowledge arguments for NP. The instance-dependent verifiable random functions is a powerful tool to tackle this problem. We first use them to obtain two interesting instance-dependent argument systems from the Barak’s public-coin bounded concurrent zero knowledge argument [1], and then, we

We study conditional computational entropy: the amount of randomness a distribution appears to have to a computationally bounded observer who is given some correlated information. By considering conditional versions of HILL entropy (based on indistinguishability from truly random distributions) and Yao entropy (based on incompressibility), we obtain: