*15:17* [Pub][ePrint]
Finding collisions for MD4 hash algorithm using hybrid algorithm, by Marko CariÄ‡
The modification of message that meets the sufficient conditions forcollision is found in the last step of differential attack proposed

by Wang et all. (2005) on MD4 hash algorithm. Here we show how this

attack phase, finding a collision starting from the list of

sufficient conditions for the collision, can be implemented using a

combination of two algorithms - evolutionary algorithm and hill

climbing. Hybridization of evolutionary algorithm and hill climbing

is a well-known technique for improving solutions, but it isn\'t

applied to this domain (at least by information that author has

collected).

*15:17* [Pub][ePrint]
Black-Box Non-Black-Box Zero Knowledge, by Vipul Goyal and Rafail Ostrovsky and Alessandra Scafuro and Ivan Visconti
Motivated by theoretical and practical interest, the challenging task of designing crypto- graphic protocols having only black-box access to primitives has generated various breakthroughs in the last decade. Despite such positive results, even though nowadays we know black-box constructions for secure two-party and multi-party computation even in constant rounds, there still are in Cryptography several constructions that critically require non-black-box use of primitives in order to securely realize some fundamental tasks. As such, the study of the gap between black-box and non-black-box constructions still includes major open questions.In this work we make progress towards filling the above gap. We consider the case of black- box constructions for computations requiring that even the size of the input of a player remains hidden. We show how to commit to a string of arbitrary size and to prove statements over the bits of the string. Both the commitment and the proof are succinct, hide the input size and use standard primitives in a black-box way. We achieve such a result by giving a black-box construction of an extendable Merkle tree that relies on a novel use of the \"MPC in the head\" paradigm of Ishai et al. [STOC 2007].

We show the power of our new techniques by giving the first black-box constant-round public-coin zero knowledge argument for NP.

To achieve this result we use the non-black-box simulation technique introduced by Barak [FOCS 2001], the PCP of Proximity introduced by Ben-Sasson et al. [STOC 2004], together with a black-box public-coin witness indistinguishable universal argument that we construct along the way.

Additionally we show the first black-box construction of a generalization of zero-knowledge sets introduced by Micali et al. [FOCS 2003]. The generalization that we propose is a strengthening that requires both the size of the set and the size of the elements of the set to remain private.

*15:17* [Pub][ePrint]
The Randomized Iterate Revisited - Almost Linear Seed Length PRGs from A Broader Class of One-way Functions, by Yu Yu and Dawu Gu and Xiangxue Li
We revisit ``the randomized iterate\'\' technique that was originally used by Goldreich, Krawczyk, and Luby (SICOMP 1993) and refined by Haitner, Harnik and Reingold (CRYPTO 2006) in constructing pseudorandom generators (PRGs) from regular one-way functions (OWFs). We abstract out a technical lemma with connections to several recent work on cryptography with imperfect randomness, which provides an arguably simpler and more modular proof for the Haitner-Harnik-Reingold PRGs from regular OWFs.We extend the approach to a more general construction of PRGs with seed length $O(n{\\log}n)$ from a broader class of OWFs. More specifically, consider an arbitrary one-way function $f$ whose range is divided into sets $\\Y_1$, $\\Y_2$, $\\ldots$, $\\Y_n$ where each $\\Y_i\\eqdef\\{y:2^{i-1}\\le|f^{-1}(y)|

*15:17* [Pub][ePrint]
(Almost) Optimal Constructions of UOWHFs from 1-to-1 and Known-Regular One-way Functions, by Yu Yu and Dawu Gu and Xiangxue Li and Jian Weng
A universal one-way hash function (UOWHF) is a compressing function for which finding a second preimage is infeasible. The seminal work of Rompel (STOC 1990) that one-way functions (OWFs) imply UOWHFs is one of the most important founding results of modern cryptography. The current best known UOWHF construction from any one-way function(on $n$-bit input) by Haitner et al. (Eurocrypt 2010) requires output and key length $\\tilO(n^7)$, which is far from practical.On the other hand, special structured OWFs typically give rise to much more efficient (and almost practical) UOWHFs. Naor and Yung (STOC 1989) gave an optimal construction of UOWHFs of key and output lengths both linear in $n$ by making a single call to any one-way permutation. De Santis and Yung (Eurocrypt 1990), Barhum and Maurer (Latincrypt 2012), and Ames, Gennaro, and Venkitasubramaniam (Asiacrypt 2012) further extended the work to more generalized settings, namely, 1-to-1 and regular one-way functions. However, the best known constructions still require key length $O(n\\cdot\\log{n})$ even for 1-to-1 one-way functions, and need to make $O(\\omega(1 {\\cdot}\\log{n})$ calls to any known regular one-way functions, or even $\\tilO(n)$ adaptive calls if one wants linear output length at the same time.

In this paper, we first introduce a technical lemma about universal hashing with nice symmetry to the leftover hash lemma, which might be of independent interest. That is, if one applies universal hash function $h:\\bit{n}\\rightarrow\\bit{a+d}$ to any random variable $X$ of min-entropy $a$, then $h$ will be 1-to-1 on $X$ except for a $2^{-d}$ fraction. We also generalize the construction of Naor and Yung (that was optimal only for one-way permutations) to 1-to-1 and almost regular one-way functions, and significantly extend their analysis. The above yields the following results.

\\begin{itemize}

\\item For any 1-to-1 one-way function, we give an optimal construction of UOWHFs with key and output length $\\Theta(n)$ by making a single call to the underlying OWF.

\\item For any known-(almost-)regular one-way function with known hardness, we give another optimal construction of UOWHFs with key and output length $\\Theta(n)$ and a single call to the one-way function.

\\item For any known-(almost-)regular one-way function, we give a construction of UOWHFs with key and output length $O(\\omega(1){\\cdot}n)$ and by making $\\omega(1)$ non-adaptive calls to the one-way function.

\\end{itemize}

where the first two constructions enjoy optimal parameters simultaneously and the third one is nearly optimal up to any(efficiently computable) super-constant factor $\\omega(1)$, e.g., $\\log\\log\\log{n}$ or even less. Furthermore, the constructions enjoy optimal shrinkages by matching the upper bound of Gennaro et al. (SICOMP 2005).