*09:17* [Pub][ePrint]
Indistinguishability Obfuscation versus Point Obfuscation with Auxiliary Input, by Christina Brzuska and Arno Mittelbach
In a recent celebrated breakthrough, Garg et al. (FOCS 2013) gave the first candidate for so-called indistinguishability obfuscation (iO) thereby reviving the interest in obfuscation for a general purpose. Since then, iO has been used to advance numerous sub-areas of cryptography. While indistinguishability obfuscation is a general purpose obfuscation scheme, several obfuscators for specific functionalities have been considered. In particular, special attention has been given to the obfuscation of so-called \\emph{point functions} that return zero everywhere, except for a single point $\\alpha$. A strong variant is point obfuscation with auxiliary input (AIPO), which allows an adversary to learn some non-trivial auxiliary information about the obfuscated point $\\alpha$ (Goldwasser, Tauman-Kalai; FOCS, 2005). Multi-bit point functions are a strengthening of point functions, where on $\\alpha$, the point function returns a string $\\beta$ instead of $1$. Multi-bit point functions with auxiliary input (MB-AIPO) have been constructed by Canetti and Bitansky (Crypto 2010) and have been used by Matsuda and Hanaoka (TCC 2014) to construct CCA-secure public-key encryption schemes and by and Bitansky and Paneth (TCC 2012) to construct three-round weak zero-knowledge protocols for NP.

In this paper we present both positive and negative results. We show that if indistinguishability obfuscation exists, then MB-AIPO does not. Towards this goal, we build on techniques by Brzuska, Farshim and Mittelbach (Crypto 2014) who use indistinguishability obfuscation as a means of attacking a large class of assumptions from the Universal Computational Extractor framework (Bellare et al; Crypto 2013). On the positive side we introduce a weak version of MB-AIPO which we deem to be outside the reach of our impossibility result. We prove that this weak version of MB-AIPO suffices to construct a public-key encryption scheme that is secure even if the adversary can learn an arbitrary leakage function of the secret key, as long as the secret key remains computationally hidden. Thereby, we strengthen a result by Canetti et al. (TCC 2010) that showed a similar connection in the symmetric-key setting.

*09:17* [Pub][ePrint]
New Generic Attacks Against Hash-based MACs, by Gaëtan Leurent and Thomas Peyrin and Lei Wang
In this paper we study the security of hash-based MAC algorithms (such as HMAC and NMAC) above the birthday bound. Up to the birthday bound, HMAC and NMAC are proven to be secure under reasonable assumptions on the hash function. On the other hand, if an $n$-bit MAC is built from a hash function with a $l$-bit state ($l \\ge n$), there is a well-known existential forgery attack with complexity $2^{l/2}$. However, the remaining security after $2^{l/2}$ computations is not well understood. In particular it is widely assumed that if the underlying hash function is sound, then a generic universal forgery attack should still require $2^{n}$ computations and some distinguishing (e.g. distinguishing-H but not distinguishing-R) and state-recovery attacks should still require $2^{l}$ (or $2^k$ if $k < l$) computations.In this work, we show that above the birthday bound, hash-based MACs offer significantly less security than previously believed. Our main result is a generic distinguishing-H and state-recovery attack against hash-based MACs with a complexity of only $\\tilde O(2^{l/2})$. In addition, we show a key-recovery attack with complexity $\\tilde O(2^{3l/4})$ against HMAC used with a hash functions with an internal checksum, such as GOST. This surprising result shows that the use of a checksum might actually weaken a hash function when used in a MAC. We stress that our attacks are generic, and they are in fact more efficient than some previous attacks proposed on MACs instantiated with concrete hash functions.

We use techniques similar to the cycle-detection technique proposed by Peyrin et al. at Asiacrypt 2012 to attack HMAC in the related-key model. However, our attacks works in the single-key model for both HMAC and NMAC, and without restriction on the key size.

*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.