## Cryptology ePrint Archive: Report 2014/476

Simon's Circuit

Paul Baecher

Abstract: Simon mentions in his seminal result separating collision-resistant hash functions from one-way permutations (EUROCRYPT '98), that the wrong strategy to sample collisions can be exploited to invert the permutation. He, however, does not spell out a concrete circuit that demonstrates this. In this short note, we describe and analyze one such circuit.

Category / Keywords: foundations /