Paper 2019/962

New Constructions of Hinting PRGs, OWFs with Encryption, and more

Rishab Goyal, Satyanarayana Vusirikala, and Brent Waters


Over the last few years there has been a surge of new cryptographic results, including laconic oblivious transfer, (anonymous/ hierarchical) identity-based encryption, trapdoor functions, chosen-ciphertext security transformations, designated-verifier zero knowledge proofs, due to a beautiful framework recently introduced in the works of Cho et al. [Crypto 2017], and D{ö}ttling and Garg [Crypto 2017]. The primitive of one-way function with encryption (OWFE) and its relatives (chameleon encryption, one-time signatures with encryption, hinting PRGs, trapdoor hash encryption, batch encryption) have been a centerpiece in all these results. While there exist multiple realizations of OWFE (and its relatives) from a variety of assumptions such as CDH, Factoring, and LWE, all such constructions fall under the same general ``missing block" framework. Although this framework has been instrumental in opening up a new pathway towards various cryptographic functionalities via the abstraction of OWFE (and its relatives), it has been accompanied with undesirable inefficiencies that has inhibited a much wider adoption in many practical scenarios. Motivated by the surging importance of the OWFE abstraction (and its relatives), a natural question to ask is whether the existing approaches can be diversified to not only obtain more constructions from different assumptions, but also in developing newer frameworks. We believe answering this question will eventually lead to important and previously unexplored performance trade-offs in the overarching applications of this novel cryptographic paradigm. In this work, we propose a new ``accumulation-style" framework for building a new class of OWFE as well as hinting PRG constructions with a special focus on achieving shorter ciphertext size and shorter public parameter size (respectively). Such performance improvements parlay into shorter parameters in their corresponding applications. Briefly, we explore the following performance trade-offs --- (1) for OWFE, our constructions outperform in terms of ciphertext size as well as encryption time, but this comes at the cost of larger evaluation and setup times, (2) for hinting PRGs, our constructions provide a rather dramatic trade-off between evaluation time versus parameter size, with our construction leading to significantly shorter public parameter size. We also provide concrete performance measurements for our constructions and compare them with existing approaches. We believe highlighting such trade-offs will lead to a wider adoption of these abstractions in a practical sense.

Available format(s)
Publication info
A minor revision of an IACR publication in CRYPTO 2020
number theoryone-way functionsRSAimplementationfactoring
Contact author(s)
rgoyal @ cs utexas edu
satya @ cs utexas edu
bwaters @ cs utexas edu
2020-11-14: last of 3 revisions
2019-08-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Rishab Goyal and Satyanarayana Vusirikala and Brent Waters},
      title = {New Constructions of Hinting PRGs, OWFs with Encryption, and more},
      howpublished = {Cryptology ePrint Archive, Paper 2019/962},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.