Cryptology ePrint Archive: Report 2018/154

Constrained PRFs for NC1 in Traditional Groups

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

Abstract: 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.

Category / Keywords: foundations / pseudo-randomness, constrained PRF, pairing free group, correlated-input hash

Original Publication (with major differences): IACR-CRYPTO-2018

Date: received 8 Feb 2018, last revised 3 Jun 2018

Contact author: yamakawa takashi at lab ntt co jp,ryo nishimaki@gmail com,n attrapadung@aist go jp,t-matsuda@aist go jp,yamada-shota@aist go jp

Available format(s): PDF | BibTeX Citation

Version: 20180604:051613 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]