Paper 2021/1192

Simple Constructions from (Almost) Regular One-Way Functions

Noam Mazor and Jiapeng Zhang

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in Tcc 2021
Keywords
pseudorandom generatoruniversal one-way hash function
Contact author(s)
noammaz @ gmail com
jiapengz @ usc edu
History
2021-09-17: received
Short URL
https://ia.cr/2021/1192
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1192,
      author = {Noam Mazor and Jiapeng Zhang},
      title = {Simple Constructions from (Almost) Regular One-Way Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1192},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1192}},
      url = {https://eprint.iacr.org/2021/1192}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.