[ Last changed: 27th January 1997 ]
A number of digital signature schemes have been proposed (Fiat-Shamir, Micali-Shamir and Bos-Chaum) which work by using a hash function of the message to key a combinatorial subset product. We find that such schemes need to incorporate a certain amount of freshness if they are to be secure, and we explain and quantify this.
When we consider the properties that a hash function must possess in order to be useful in this kind of application, we find that, contrary to previous belief, collision freedom is not a sufficient condition for hash functions. In fact, given any collision free hash function, we construct a derived function which is also collision free but cryptographically useless. In the process, we settle an outstanding conjecture of Okamoto that correlation freedom is a strictly stronger property than collision freedom.