What's the difference between UOWHF and CRHF and why are UOWHF useful?

As far as I understand, Universal One-Way Hash Functions are an alternative to CRHF. While for CRHF it is hard, given randomly chosen hash function parameters, to find any collision of the hash function; for UOWHF it's hard to find a collision where one preimage is chosen independently of the hash function parameters.

How does this difference affect the behaviour of the functions and why are UOWHF so relevant?


1 Answer 1


It's a combination of:

  1. UOWHF is a weaker primitive than CRHF (collision resistance implies universal one-wayness) and it turns out that it can be (black-box) constructed from one-way functions (OWFs) [NY,R]. While, CRHFs cannot be (black-box) constructed from OWFs [S].
  2. For some applications, (e.g., digital signatures [NY]) UOWHFs suffice instead of collision resistance.

[NY]: Naor and Yung, Universal One-Way Hash Functions and their Cryptographic Applications, STOC'89

[R]: Rompel, One-way functions are necessary and sufficent for secure signatures,STOC'90

[S]: Simon. Finding collisions on a one-way street: Can secure hash functions be based on general assumptions?, Eurocrypt'98.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.