Reading the Crypto Classics: Simon: “Finding Collisions on a One-Way Street: Can Secure Hash Functions Be Based on General Assumptions?”

Organizer: Patrick Harasser, TU Darmstadt, Cryptoplexity Group

Abstract

This is the third talk in the seminar series “Reading the Crypto Classics” for the summer term 2021. The idea of this seminar is to jointly read classical milestone papers in the area of cryptography, to discuss their impact and understand their relevance for current research areas. The seminar is running as an Oberseminar, but at the same time meant to be a joint reading group seminar of the CROSSING Special Interest Group on Advanced Cryptography with all interested CROSSING members being invited to participate.

This issue will cover the paper

Simon: “Finding Collisions on a One-Way Street: Can Secure Hash Functions Be Based on General Assumptions?” (EUROCRYPT'98); available at https://link.springer.com/content/pdf/10.1007%2FBFb0054137.pdf (opens in new tab)

with the following abstract:

“We prove the existence of an oracle relative to which there exist several well-known cryptographic primitives, including one-way permutations, but excluding (for a suitably strong definition) collision-intractible hash functions. Thus any proof that such functions can be derived from these weaker primitives is necessarily non-relativizing; in particular, no provable construction of a collision-intractable hash function can exist based solely on a ”black box“ one-way permutation. This result can be viewed as a partial justification for the common practice of treating the

collision-intractable hash function as a cryptographic primitive, rather than attempting to derive it from a weaker primitive (such as a one-way permutation).”

Further information about the virtual format

For participation the following Meeting Link is required:
https://bbb.cryptoplexity.informatik.tu-darmstadt.de/r/CX-Crypto-Classics

More information

CROSSING Wiki