International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Simple Constructions from (Almost) Regular One-Way Functions

Authors:
Noam Mazor
Jiapeng Zhang
Download:
DOI: 10.1007/978-3-030-90453-1_16
Search ePrint
Search Google
Abstract: Two of the most useful cryptographic primitives that can be constructed from one-way functions are pseudorandom generators (PRGs) and universal one-way hash functions (UOWHFs). In order to implement them in practice, the efficiency of such constructions must be considered. The three major efficiency measures are: the seed length, the call complexity to the one-way function, and the adaptivity of these calls. Still, the optimal efficiency of these constructions is not yet fully understood: there exist gaps between the known upper bound and the known lower bound for black-box constructions. A special class of one-way functions called unknown-regular one-way functions is much better understood. Haitner, Harnik and Reingold (CRYPTO 2006) presented a PRG construction with semi-linear seed length and linear number of calls based on a method called randomized iterate. Ames, Gennaro and Venkitasubramaniam (TCC 2012) then gave a construction of UOWHF with similar parameters and using similar ideas. On the other hand, Holenstein and Sinha (FOCS 2012) and Barhum and Holenstein (TCC 2013) showed an almost linear call-complexity lower bound for black-box constructions of PRGs and UOWHFs from one-way functions. Hence Haitner et al. and Ames et al. reached tight constructions (in terms of seed length and the number of calls) of PRGs and UOWHFs from regular one-way functions. These constructions, however, are adaptive. In this work, we present non-adaptive constructions for both primitives which match the optimal call-complexity given by Holenstein and Sinha and Barhum and Holenstein. Our constructions, besides being simple and non-adaptive, are robust also for almost-regular one-way functions.
Video from TCC 2021
BibTeX
@article{tcc-2021-31516,
  title={Simple Constructions from (Almost) Regular One-Way Functions},
  booktitle={Theory of Cryptography;19th International Conference},
  publisher={Springer},
  doi={10.1007/978-3-030-90453-1_16},
  author={Noam Mazor and Jiapeng Zhang},
  year=2021
}