Cryptology ePrint Archive: Report 2017/1094

Privately Constraining and Programming PRFs, the LWE Way

Chris Peikert and Sina Shiehian

Abstract: *Constrained* pseudorandom functions allow for delegating ``constrained'' secret keys that let one compute the function at certain authorized inputs---as specified by a constraining predicate---while keeping the function value at unauthorized inputs pseudorandom. In the *constraint-hiding* variant, the constrained key hides the predicate. On top of this, *programmable* variants allow the delegator to explicitly set the output values yielded by the delegated key for a particular set of unauthorized inputs.

Recent years have seen rapid progress on applications and constructions of these objects for progressively richer constraint classes, resulting most recently in constraint-hiding constrained PRFs for arbitrary polynomial-time constraints from Learning With Errors~(LWE) [Brakerski, Tsabary, Vaikuntanathan, and Wee, TCC'17], and privately programmable PRFs from indistinguishability obfuscation (iO) [Boneh, Lewi, and Wu, PKC'17].

In this work we give a unified approach for constructing both of the above kinds of PRFs from LWE with subexponential $\exp(n^{\varepsilon})$ approximation factors. Our constructions follow straightforwardly from a new notion we call a *shift-hiding shiftable function*, which allows for deriving a key for the sum of the original function and any desired hidden shift function. In particular, we obtain the first privately programmable PRFs from non-iO assumptions.

Category / Keywords: public-key cryptography /

Original Publication (with minor differences): IACR-PKC-2018

Date: received 9 Nov 2017, last revised 10 Jan 2018

Contact author: cpeikert at alum mit edu

Available format(s): PDF | BibTeX Citation

Note: Improved exposition, simplified construction.

Version: 20180110:162943 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]