UOWHF
Encyclopedia
In cryptography
a universal one-way hash function (UOWHF, often pronounced "woof"), is a type of universal hash function
of particular importance to cryptography
. UOWHF's are proposed as an alternative to collision-resistant hash functions
(CRHFs). CRHFs have a strong collision-resistance property: that it is hard, given randomly chosen hash function parameters, to find any collision of the hash function. In contrast, UOWHFs require that it be hard to find a collision where one preimage is chosen independently of the hash function parameters.
The UOWHF family contains a finite number of hash functions with each
having the same probability of being used.
be an algorithm that operates in two phases:
Then for all polynomial-time
the probability that 
succeeds is negligible.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
a universal one-way hash function (UOWHF, often pronounced "woof"), is a type of universal hash function
Universal hashing
Using universal hashing refers to selecting a hash function at random from a family of hash functions with a certain mathematical property . This guarantees a low number of collisions in expectation, even if the data is chosen by an adversary...
of particular importance to cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
. UOWHF's are proposed as an alternative to collision-resistant hash functions
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
(CRHFs). CRHFs have a strong collision-resistance property: that it is hard, given randomly chosen hash function parameters, to find any collision of the hash function. In contrast, UOWHFs require that it be hard to find a collision where one preimage is chosen independently of the hash function parameters.
The UOWHF family contains a finite number of hash functions with each
having the same probability of being used.
Definition
The security property of a UOWHF is as follows. Let be an algorithm that operates in two phases:- Initially,
receives no input (or, just a security parameter) and chooses a value 
. - A hash function
is chosen from the family. 
then receives 
and must output 
such that 
.
Then for all polynomial-time
the probability that succeeds is negligible.Applications
UOWHFs are thought to be less computationally expensive than CRHFs, and are most often used for efficiency purposes in schemes where the choice of the hash function happens at some stage of execution, rather than beforehand. For instance, the Cramer–Shoup cryptosystem uses a UOWHF as part of the validity check in its ciphertexts.External links
- Moni NaorMoni NaorMoni Naor is an Israeli computer scientist, currently a professor at the Weizmann Institute of Science. Naor received his Ph.D. in 1989 at the University of California, Berkeley. His adviser was Manuel Blum....
and Moti Yung, "Universal One-Way Hash Functions and their Cryptographic Applications", 1989.