Paper 2020/233

Key-Homomorphic Pseudorandom Functions from LWE with a Small Modulus

Sam Kim

Abstract

Pseudorandom functions (PRFs) are fundamental objects in cryptography that play a central role in symmetric-key cryptography. Although PRFs can be constructed from one-way functions generically, these black-box constructions are usually inefficient and require deep circuits to evaluate compared to direct PRF constructions that rely on specific algebraic assumptions. From lattices, one can directly construct PRFs from the Learning with Errors (LWE) assumption (or its ring variant) using the result of Banerjee, Peikert, and Rosen (Eurocrypt 2012) and its subsequent works. However, all existing PRFs in this line of work rely on the hardness of the LWE problem where the associated modulus is super-polynomial in the security parameter. In this work, we provide two new PRF constructions from the LWE problem that each focuses on either minimizing the depth of its evaluation circuit or providing key-homomorphism while relying on the hardness of the LWE problem with either a polynomial modulus or nearly polynomial modulus. Along the way, we introduce a new variant of the LWE problem called the Learning with Rounding and Errors (LWRE) problem. We show that for certain settings of parameters, the LWRE problem is as hard as the LWE problem. We then show that the hardness of the LWRE problem naturally induces a pseudorandom synthesizer that can be used to construct a low-depth PRF. The techniques that we introduce to study the LWRE problem can then be used to derive variants of existing key-homomorphic PRFs whose security can be reduced from the hardness of the LWE problem with a much smaller modulus.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in EUROCRYPT 2020
Keywords
pseudorandom functionslattices
Contact author(s)
skim13 @ cs stanford edu
History
2020-02-24: revised
2020-02-24: received
See all versions
Short URL
https://ia.cr/2020/233
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/233,
      author = {Sam Kim},
      title = {Key-Homomorphic Pseudorandom Functions from {LWE} with a Small Modulus},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/233},
      year = {2020},
      url = {https://eprint.iacr.org/2020/233}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.