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/s00145-024-09507-4
Search ePrint
Search Google
Abstract: AbstractTwo 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 (ASIACRYPT 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.
BibTeX
@article{jofc-2024-34428,
  title={Simple Constructions from (Almost) Regular One-Way Functions},
  journal={Journal of Cryptology},
  publisher={Springer},
  volume={37},
  pages={25},
  doi={10.1007/s00145-024-09507-4},
  author={Noam Mazor and Jiapeng Zhang},
  year=2024
}