### Adaptively Single-Key Secure Constrained PRFs for NC1

##### Abstract

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)
Category
Foundations
Publication info
A major revision of an IACR publication in PKC 2019
Keywords
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
History
2019-04-03: last of 2 revisions
See all versions
Short URL
https://ia.cr/2018/1000

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

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.