Embedding a universal circuit for some class of functions allows us to produce constrained keys for functions in this class, which gives us the first standard-lattice-assumption-based constrained PRF (CPRF) for general bounded-description bounded-depth functions, for arbitrary polynomial bounds on the description size and the depth. (A constrained key w.r.t a circuit $C$ enables one to evaluate the PRF on all $x$ for which $C(x)=1$, but reveals nothing on the PRF values at other points.) We rely on the LWE assumption and on the one-dimensional SIS (Short Integer Solution) assumption, which are both related to the worst case hardness of general lattice problems. Previous constructions for similar function classes relied on such exotic assumptions as the existence of multilinear maps or secure program obfuscation. The main drawback of our construction is that it does not allow collusion (i.e. to provide more than a single constrained key to an adversary). Similarly to the aforementioned previous works, our PRF family is also key homomorphic.
Interestingly, our constrained keys are very short. Their length does not depend directly either on the size of the constraint circuit or on the input length. We are not aware of any prior construction achieving this property, even relying on strong assumptions such as indistinguishability obfuscation.Category / Keywords: Original Publication (with minor differences): IACR-TCC-2015 Date: received 14 Jan 2015, last revised 14 Jan 2015 Contact author: zvika brakerski at weizmann ac il Available format(s): PDF | BibTeX Citation Version: 20150114:211203 (All versions of this report) Short URL: ia.cr/2015/032 Discussion forum: Show discussion | Start new discussion