Paper 2017/143

Constraint-hiding Constrained PRFs for NC1 from LWE

Ran Canetti and Yilei Chen


Constraint-hiding constrained PRFs (CHCPRFs), initially studied by Boneh, Lewi, and Wu [PKC 2017], are constrained PRFs where the constrained key hides the description of the constraint. Envisioned with powerful applications such as searchable encryption, private-detectable watermarking, and symmetric deniable encryption, the only known candidates of CHCPRFs are based on indistinguishability obfuscation or multilinear maps with strong security properties. In this paper, we construct CHCPRFs for all NC1 circuits from the Learning with Errors assumption. The construction draws heavily from the graph-induced multilinear maps by Gentry, Gorbunov, and Halevi [TCC 2015], as well as the existing lattice-based PRFs. Our construction gives an instance of the GGH15 applications with a security reduction from LWE. We also show how to build from CHCPRFs reusable garbled circuits (RGC), or equivalently private-key function-hiding functional encryptions with 1-key security. This provides a different approach to constructing RGC from that of Goldwasser et al. [STOC 2013].

Note: Dec 30, 2019: We add a comparison of the reusable garbled circuit construction of ours to the one of Goldwasser et al. [STOC 2013]. May 14, 2018: We withdraw the claim of achieving fully adaptive security for the CHCPRF. The corrected statements and other additional results/discussions can be found in footnotes 1 and 2, Section 1.4, Section 5.3 and Section 7.

Available format(s)
Publication info
A minor revision of an IACR publication in EUROCRYPT 2017
Graded encodingsconstraint-hiding PRFsfunctional encryption
Contact author(s)
canetti @ bu edu
chenyilei ra @ gmail com
2019-12-31: last of 3 revisions
2017-02-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ran Canetti and Yilei Chen},
      title = {Constraint-hiding Constrained PRFs for NC1 from LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2017/143},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.