2012 | OriginalPaper | Chapter
The Generalized Randomized Iterate and Its Application to New Efficient Constructions of UOWHFs from Regular One-Way Functions
Authors : Scott Ames, Rosario Gennaro, Muthuramakrishnan Venkitasubramaniam
Published in: Advances in Cryptology – ASIACRYPT 2012
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
This paper presents the
Generalized Randomized Iterate
of a (regular) one-way function
f
and show that it can be used to build Universal One-Way Hash Function (UOWHF) families with
O
(
n
2
) key length.
We then show that Shoup’s technique for UOWHF domain extension can be used to improve the efficiency of the previous construction. We present the
Reusable Generalized Randomized Iterate
which consists of
k
≥
n
+ 1 iterations of a regular one-way function composed at each iteration with a pairwise independent hash function, where we only use log
k
such hash functions, and we “schedule” them according to the same scheduling of Shoup’s domain extension technique. The end result is a UOWHF construction from regular one-way functions with an
O
(
n
log
n
) key. These are the first such efficient constructions of UOWHF from regular one-way functions of unknown regularity.
Finally we show that the Shoup’s domain extension technique can also be used in lieu of derandomization techniques to improve the efficiency of PRGs and of hardness amplification constructions for regular one-way functions.