Organizer: Patrick Harasser, TU Darmstadt, Cryptoplexity Group
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 (wird in neuem Tab geöffnet)https://link.springer.com/content/pdf/10.1007%2FBFb0054137.pdf
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).“