Cryptology ePrint Archive: Report 2017/143

Constraint-hiding Constrained PRFs for NC1 from LWE

Ran Canetti and Yilei Chen

Abstract: 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 to 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 of constructing RGC from that of Goldwasser et al. [STOC 2013].

Category / Keywords: Graded encodings, constraint-hiding PRFs, functional encryption

Original Publication (in the same form): IACR-EUROCRYPT-2017

Date: received 15 Feb 2017, last revised 14 May 2018

Contact author: canetti at bu edu, chenyilei ra@gmail com

Available format(s): PDF | BibTeX Citation

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

Version: 20180514:212721 (All versions of this report)

Short URL: ia.cr/2017/143

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]