Private Constrained PRFs (and More) from LWE

In a constrained PRF, the owner of the PRF key K can generate constrained keys \(K_f\) that allow anyone to evaluate the PRF on inputs x that satisfy the predicate f (namely, where f(x) is “true”) but reveal no information about the PRF evaluation on the

  • PDF / 590,791 Bytes
  • 39 Pages / 439.37 x 666.142 pts Page_size
  • 72 Downloads / 201 Views

DOWNLOAD

REPORT


Weizmann Institute of Science, Rehovot, Israel 2 MIT, Cambridge, USA [email protected] 3 CNRS and ENS, Paris, France

Abstract. In a constrained PRF, the owner of the PRF key K can generate constrained keys Kf that allow anyone to evaluate the PRF on inputs x that satisfy the predicate f (namely, where f (x) is “true”) but reveal no information about the PRF evaluation on the other inputs. A private constrained PRF goes further by requiring that the constrained key Kf hides the predicate f . Boneh, Kim and Montgomery (EUROCRYPT 2017) recently presented a construction of private constrained PRF for point function constraints, and Canetti and Chen (EUROCRYPT 2017) presented a completely different construction for more general NC1 constraints. In this work, we show two constructions of LWE-based constraint-hiding constrained PRFs for general predicates described by polynomial-size circuits. The two constructions are based on two distinct techniques that we show have further applicability, by constructing weak attributehiding predicate encryption schemes. In a nutshell, the first construction imports the technique of modulus switching from the FHE world into the domain of trapdoor extension and homomorphism. The second construction shows how to use the duality between FHE secret-key/randomness and ABE randomness/secret-key to construct a scheme with dual use of the same values for both FHE and ABE purposes.

1

Introduction

Lattice-based cryptography, and in particular the construction of cryptographic primitives based on the learning with errors (LWE) assumption [Reg05], has seen Z. Brakerski and R. Tsabary—Supported by the Israel Science Foundation (Grant No. 468/14), Binational Science Foundation (Grants No. 2016726, 2014276) and ERC Project 756482 REACT. V. Vaikuntanathan—Research supported in part by NSF Grants CNS-1350619 and CNS-1414119, Alfred P. Sloan Research Fellowship, Microsoft Faculty Fellowship and by the Defense Advanced Research Projects Agency (DARPA) and the U.S. Army Research Office under contracts W911NF-15-C-0226 and W911NF-15-C-0236. H. Wee—Supported in part by ERC Project aSCEND (H2020 639554) and NSF Award CNS-1445424. c International Association for Cryptologic Research 2017  Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part I, LNCS 10677, pp. 264–302, 2017. https://doi.org/10.1007/978-3-319-70500-2_10

Private Constrained PRFs (and More) from LWE

265

a significant leap in recent years. Most notably, we now have a number of constructions of cryptographic primitives that “compute on encrypted data”. For example, fully homomorphic encryption (FHE) [Gen09,BV11,BGV12,GSW13], which enables arbitrary computation on encrypted data without knowledge of the secret key; attribute-based encryption (ABE) [SW05,GPSW06,GVW13, BGG+14], which supports fine-grained access control of encrypted data via the creation of restricted secret keys; new forms of pseudo-random functions (PRF) such as constrained PRFs [BW13,KPTZ13,BGI14]; and many more. In this paper, we continue this line of inquiry and develop two new construc