C3 seminár

A (k,l)-robust combiner for collision resistant hash functions is a construction, which takes l hash functions and combines them so that if at least k of the components are collision resistant, then so is the resulting combination. A black-box (k,l)-robust combiner is robust combiner, which takes its components as black-boxes. A trivial black-box combiner is concatenation of any (l-k+1) of the hash functions. Boneh and Boyen followed by Pietrzak proved, that for collision resistance we cannot do much better that concatenation, i.e. there does not exist black box (k,l)-robust combiner for collision resistance, whose output is significantly shorter that the output of the trivial combiner. We discuss the proof of this result.

V prezentácii predstavíme myšlienku inkrementálneho hašovanie, vrátane konštrukcií XORHASH a AdHASH (a jej modifikácií). Ukážeme útoku na konštrukciu XORHASH. V ďalšom prezentujeme zovšeobecnený narodeninový útok a jeho aplikáciu na útoky na inkrementálne hašovanie. Prezentácia vychádza z prác: M. Bellare, D. Micciancio: A New Paradigm for collision-free hashing: Incrementality at reduced cost (1997) a práce D. Wagner A generalized birthday problem (2002)

Standard cryptographic definitions and constructions do not guarantee any security even if a tiny fraction of the secret entity is compromised. We'll demonstrate a few ways of building cryptographic primitives that remain provably secure even when an adversary is able to learn almost the entire secret.

Recent attacks on collision resistant hash functions have shown, that creating collision resistant hash function (CRHF) is a hard task. Very important application of CRHF are digital signatures. In 2007, Halevi and Krawczyk proposed a randomized mode of operation for hash functions, which frees digital signatures from dependency on full collision resistance. They presented two schemes, which are easy to implement in current signature schemes, and proved they security under second-preimage-like assumption for compression function. In the presentation we discuss this result.