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

Note: Improved exposition, simplified construction.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in PKC 2018
Contact author(s)
cpeikert @ alum mit edu
History
2018-01-10: last of 2 revisions
2017-11-10: received
See all versions
Short URL
https://ia.cr/2017/1094
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1094,
      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{https://eprint.iacr.org/2017/1094}},
      url = {https://eprint.iacr.org/2017/1094}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.