Finding Collisions on a Public Road, or
Do Secure Hash Functions Need Secret Coins?

by Chun-Yuan Hsiao and Leonid Reyzin
 
Abstract

Many cryptographic primitives begin with parameter generation, which picks a primitive from a family. Such generation can use public coins (e.g., in the discrete-logarithm-based case) or secret coins (e.g., in the factoring-based case). We study the relationship between public-coin and secret-coin collision-resistant hash function families (CRHFs). Specifically, we demonstrate that:

The last statement above is our main result, which states that there is no black-box reduction from public-coin CRHFs to secret-coin CRHFs. Our proof for this result, while employing oracle separations, uses a novel approach, which demonstrates that there is no black-box reduction without demonstrating that there is no relativizing reduction.

This work appears in Advances in Cryptology -- Crypto 2004, Matt Franklin, editor, Lecture Notes in Computer Science 3152, Springer-Verlag, 2004, pages 92-105. © IACR.