Paper 2018/1000

Adaptively Single-Key Secure Constrained PRFs for NC1

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


We present a construction of an adaptively single-key secure constrained PRF (CPRF) for $\mathbf{NC}^1$ assuming the existence of indistinguishability obfuscation (IO) and the subgroup hiding assumption over a (pairing-free) composite order group. This is the first construction of such a CPRF in the standard model without relying on a complexity leveraging argument. To achieve this, we first introduce the notion of partitionable CPRF, which is a CPRF accommodated with partitioning techniques and combine it with shadow copy techniques often used in the dual system encryption methodology. We present a construction of partitionable CPRF for $\mathrm{NC}^1$ based on IO and the subgroup hiding assumption over a (pairing-free) group. We finally prove that an adaptively single-key secure CPRF for $\mathbf{NC}^1$ can be obtained from a partitionable CPRF for $\mathbf{NC}^1$ and IO.

Note: Minor edit on the presentation (1/31/2019)

Available format(s)
Publication info
A major revision of an IACR publication in PKC 2019
constrained pseudorandom functionadaptive securityobfuscation
Contact author(s)
takashi yamakawa ga @ hco ntt co jp
ryo nishimaki zk @ hco ntt co jp
n attrapadung @ aist go jp
t-matsuda @ aist go jp
yamada-shota @ aist go jp
2019-04-03: last of 2 revisions
2018-10-22: 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 = {Adaptively Single-Key Secure Constrained PRFs for NC1},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1000},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.