Paper 2017/1094

Privately Constraining and Programming PRFs, the LWE Way

Chris Peikert and Sina Shiehian


*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.

Note: Improved exposition, simplified construction.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in PKC 2018
Contact author(s)
cpeikert @ alum mit edu
2018-01-10: last of 2 revisions
2017-11-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Chris Peikert and Sina Shiehian},
      title = {Privately Constraining and Programming PRFs, the LWE Way},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1094},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.