The paper introduces the concept of *Universal One-Way Hash Functions* (UOWHF), a new cryptographic primitive that enables the compression of elements in the function domain while maintaining computational hardness. The main property of UOWHF is that it is difficult to find a different domain element that collides with a given element. The authors prove constructively that UOWHF exist if any 1-1 one-way functions exist.
One of the key applications of UOWHF is a *One-Way based Secure Digital Signature Scheme*. This scheme is based on the existence of any 1-1 one-way functions and is secure against the most general attack known. Previously, all provably secure signature schemes were based on the stronger assumption that *trapdoor* one-way functions exist.
The paper also discusses the history and significance of digital signatures, highlighting the evolution from schemes based on trapdoor functions to those based on one-way functions. The authors present a detailed construction of the one-way based signature scheme, including its components, algorithms, and security proof. The scheme is based on a tagging system and extends it with the capability of "regenerating rows of windows," allowing for efficient and succinct compression of large files.
Additionally, the paper explores extensions and open problems, including the relationship between UOWHF and pseudorandom generators, and the potential for constructing collision intractable hash functions (CIHF) using UOWHF. The authors also discuss the implications of CIHF for zero-knowledge interactive proofs and the potential for more efficient constructions based on more restrictive assumptions.The paper introduces the concept of *Universal One-Way Hash Functions* (UOWHF), a new cryptographic primitive that enables the compression of elements in the function domain while maintaining computational hardness. The main property of UOWHF is that it is difficult to find a different domain element that collides with a given element. The authors prove constructively that UOWHF exist if any 1-1 one-way functions exist.
One of the key applications of UOWHF is a *One-Way based Secure Digital Signature Scheme*. This scheme is based on the existence of any 1-1 one-way functions and is secure against the most general attack known. Previously, all provably secure signature schemes were based on the stronger assumption that *trapdoor* one-way functions exist.
The paper also discusses the history and significance of digital signatures, highlighting the evolution from schemes based on trapdoor functions to those based on one-way functions. The authors present a detailed construction of the one-way based signature scheme, including its components, algorithms, and security proof. The scheme is based on a tagging system and extends it with the capability of "regenerating rows of windows," allowing for efficient and succinct compression of large files.
Additionally, the paper explores extensions and open problems, including the relationship between UOWHF and pseudorandom generators, and the potential for constructing collision intractable hash functions (CIHF) using UOWHF. The authors also discuss the implications of CIHF for zero-knowledge interactive proofs and the potential for more efficient constructions based on more restrictive assumptions.