Paper 2022/1770

Cryptographic Primitives with Hinting Property

Navid Alamati, VISA Research
Sikhar Patranabis, IBM Research India

A hinting pseudorandom generator (PRG) is a potentially stronger variant of PRG with a ``deterministic'' form of circular security with respect to the seed of the PRG (Koppula and Waters, CRYPTO 2019). Hinting PRGs enable many cryptographic applications, most notably CCA-secure public-key encryption and trapdoor functions. In this paper, we study cryptographic primitives with the hinting property, yielding the following results: We present a novel and conceptually simpler approach for designing hinting PRGs from certain decisional assumptions over cyclic groups or isogeny-based group actions, which enables simpler security proofs as compared to the existing approaches for designing such primitives. We introduce hinting weak pseudorandom functions (wPRFs), a natural extension of the hinting property to wPRFs, and show how to realize circular/KDM-secure symmetric-key encryption from any hinting wPRF. We demonstrate that our simple approach for building hinting PRGs can be extended to realize hinting wPRFs from the same set of decisional assumptions. We propose a stronger version of the hinting property, which we call the functional hinting property, that guarantees security even in the presence of hints about functions of the secret seed/key. We show how to instantiate functional hinting PRGs/wPRFs for certain (families of) functions by building upon our simple techniques for realizing plain hinting PRGs/wPRFs. We also demonstrate the applicability of a functional hinting wPRF with certain algebraic properties in realizing KDM-secure public-key encryption in a black-box manner. We show the first black-box separation between hinting wPRFs (and hinting PRGs) from public-key encryption using simple realizations of these primitives given only a random oracle.

Available format(s)
Publication info
A minor revision of an IACR publication in ASIACRYPT 2022
Contact author(s)
alamati @ umich edu
sikharpatranabis @ gmail com
2022-12-27: approved
2022-12-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Navid Alamati and Sikhar Patranabis},
      title = {Cryptographic Primitives with Hinting Property},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1770},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.