International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Privately Constraining and Programming PRFs, the LWE Way

Chris Peikert
Sina Shiehian
DOI: 10.1007/978-3-319-76581-5_23
Search ePrint
Search Google
Conference: PKC 2018
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 })$$exp(nε) 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.
  title={Privately Constraining and Programming PRFs, the LWE Way},
  booktitle={Public-Key Cryptography – PKC 2018},
  series={Public-Key Cryptography – PKC 2018},
  author={Chris Peikert and Sina Shiehian},