Paper 2018/154

Constrained PRFs for NC1 in Traditional Groups

Nuttapong Attrapadung, Takahiro Matsuda, Ryo Nishimaki, Shota Yamada, and Takashi Yamakawa


We propose new constrained pseudorandom functions (CPRFs) in traditional groups. Traditional groups mean cyclic and multiplicative groups of prime order that were widely used in the 1980s and 1990s (sometimes called ``pairing free'' groups). Our main constructions are as follows. - We propose a selectively single-key secure CPRF for circuits with depth $O(\log n)$ (that is, $\textbf{NC}^1$ circuits) in traditional groups} where $n$ is the input size. It is secure under the $L$-decisional Diffie-Hellman inversion ($L$-DDHI) assumption in the group of quadratic residues $\mathbb{QR}_q$ and the decisional Diffie-Hellman (DDH) assumption in a traditional group of order $q$ in the standard model. - We propose a selectively single-key private bit-fixing CPRF in traditional groups. It is secure under the DDH assumption in any prime-order cyclic group in the standard model. - We propose adaptively single-key secure CPRF for $\textbf{NC}^1$ and private bit-fixing CPRF in the random oracle model. To achieve the security in the standard model, we develop a new technique using correlated-input secure hash functions.

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2018
pseudo-randomnessconstrained PRFpairing free groupcorrelated-input hash
Contact author(s)
yamakawa takashi @ lab ntt co jp
ryo nishimaki @ gmail com
n attrapadung @ aist go jp
t-matsuda @ aist go jp
yamada-shota @ aist go jp
2018-06-04: revised
2018-02-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nuttapong Attrapadung and Takahiro Matsuda and Ryo Nishimaki and Shota Yamada and Takashi Yamakawa},
      title = {Constrained PRFs for NC1 in Traditional Groups},
      howpublished = {Cryptology ePrint Archive, Paper 2018/154},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.