UOWHF

From Wikipedia, the free encyclopedia

 All or part of this article may be confusing or unclear.
Please help clarify the article. Suggestions may be on the talk page. (August 2007)
Unsolved problems in Cryptography: ''How to construct UOWHF of higher orders efficiently?''

In cryptography a Universal One Way Hash Function (UOWHF), often pronounced "woof", is a cryptographic hash function. UOWHF's are proposed as an alternative to CRHF's. Collision Resistant Hash Functions (CRHF) are based on the stronger assumption that finding a collision in hash function is impossible. Any cryptographic system based on CRHF is considered to be less secure. To overcome this disadvantage, UOWHFs are proposed. UOWHFs are based on weaker assumption that finding a collision in t time units with probability ε is impossible, known as (t,ε)-UOWHF's.

Universal One Way Hash Function (UOWHF) Family contains finite number of hash functions with each having same probability of being used. And collision resistance is achieved by applying hash functions several time from this family. These functions need keys to operate on them.

Contents

[edit] Need and Intuition

In CRHF the adversary wins the game once he finds a collision pair. Assuming CRHF and designing hash functions based on that would be a costly mistake. UOWHF is an attractive alternative to CRHF. A UOWHF has the following advantages compared to a CRHF:

  • The security bound is 2n when the output length is n.
  • A UOWHF is weaker than a CRHF.
  • A UOWHF is easier to design than a CRHF.

The basic reason for this would be Ask less of a hash function and it is less likely to disappoint!, and design the system with this hash function.
In UOWHF the adversary does not win for any collision. He has to specify a state, say S, and then he gets the key K. He now has to find a collision for the specified S and hK.

[edit] Construction of UOWHFs

Informally, UOWHF is like re-hashing. The hash function family H contains finite number of hash functions. Based on the text that has to be hashed and block size, different hash functions will be chosen from H. In many cryptographic applications it is desirable to construct a hash function which is UOWHF of a certain degree. The challenges regarding this are

  • To construct UOWHF without wasting random materials, thus minimizing key length.
  • To achieve higher order UOWHF at the same time.
  • To find an efficient way to do all this.

UOWHF is used for achieving secure signatures.

[edit] External links

  • Moni Naor and Moti Yung, "Universal One-Way Hash Functions and their Cryptographic Applications.", 1986, , from [1]

[edit] Reference Book

  • Oded Goldreich, "Foundations of Cryptography" , Volume 2, Cambridge University Press, 2004, from [2]