Adaptively Single-Key Secure Constrained PRFs for NC1

Nuttapong Attrapadung; Takahiro Matsuda; Ryo Nishimaki; Shota Yamada; Takashi Yamakawa

Paper 2018/1000

Adaptively Single-Key Secure Constrained PRFs for NC1

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

Abstract

We present a construction of an adaptively single-key secure constrained PRF (CPRF) for ${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 based on IO and the subgroup hiding assumption over a (pairing-free) group. We finally prove that an adaptively single-key secure CPRF for can be obtained from a partitionable CPRF for and IO.

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

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A major revision of an IACR publication in PKC 2019
Keywords: constrained pseudorandom function adaptive security obfuscation
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
History: 2019-04-03: last of 2 revisions; 2018-10-22: received; See all versions
Short URL: https://ia.cr/2018/1000
License: CC BY

BibTeX

@misc{cryptoeprint:2018/1000,
      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},
      url = {https://eprint.iacr.org/2018/1000}
}