Name
Abstract | ||
|---|---|---|
We present a new construction of a compression function H {0,1}3n → {0,1}2n that uses two parallel calls to an ideal primitive (an ideal blockcipher or a public random function) from 2n to n bits. This is similar to the well-known MDC-2 or the recently proposed MJH by Lee and Stam (CT-RSA'11). However, unlike these constructions, we show already in the compression function that an adversary limited (asymptotically in n ) to O(22n (1-δ)/3) queries (for any δ0) has disappearing advantage to find collisions. A key component of our construction is the use of the Szemerédi---Trotter theorem over finite fields to bound the number of full compression function evaluations an adversary can make, in terms of the number of queries to the underlying primitives. Moveover, for the security proof we rely on a new abstraction that refines and strenghtens existing techniques. We believe that this framework elucidates existing proofs and we consider it of independent interest. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-28914-9_17 | TCC |
Keywords | Field | DocType |
full compression function evaluation,ideal blockcipher,finite field,independent interest,discrete geometry,public random function,compression function,compression function h,new construction,key component,new abstraction | Discrete geometry,Discrete mathematics,Finite field,Abstraction,Computer science,Collision resistance,Theoretical computer science,Mathematical proof,Hash function,Adversary,Random function | Conference |
Volume | ISSN | Citations |
7194 | 0302-9743 | 8 |
PageRank | References | Authors |
0.54 | 15 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dimitar Jetchev | 1 | 160 | 7.64 |
| Onur Özen | 2 | 236 | 8.61 |
| Martijn Stam | 3 | 1659 | 67.36 |