Paper 2018/1077
More Efficient Lattice PRFs from Keyed Pseudorandom Synthesizers
Hart Montgomery
Abstract
We develop new constructions of latticebased PRFs using keyed pseudorandom synthesizers. We generalize all of the known `basic' parallel latticebased PRFsthose of [BPR12], [BLMR13], and [BP14]to build highly parallel latticebased PRFs with smaller modulus (and thus better reductions from worstcase lattice problems) while still maintaining computational efficiency asymptotically equal to the fastest known latticebased PRFs at only the cost of larger key sizes. In particular, we build several parallel (in $NC^{2}$) latticebased PRFs with modulus independent of the number of PRF input bits based on both standard LWE and ring LWE. Our modulus for these PRFs is just $O \left(m^{ f \left(m \right)} \right)$ for lattice dimension $m$ and any function $f \left(m \right) \in \omega \left(1 \right)$. The only known parallel construction of a latticebased PRF with such a small modulus is a construction from Banerjee's thesis, and some of our parallel PRFs with equivalently small modulus have smaller key sizes and are very slightly faster (when using FFT multiplication). These PRFs also asymptotically match the computational efficiency of the most efficient PRFs built from any LWE or ring LWEbased assumptions known (potentially excluding some concurrent work), respectively, and concretely require less computation per output than any known parallel latticebased PRFs (again when using FFT multiplication). We additionally use our techniques to build other efficient PRFs with very low circuit complexity (but higher modulus) which improve known results on highly parallel lattice PRFs. For instance, for input length $\lambda$, we show that there exists a ring LWEbased PRF in $NC^{1}$ with modulus proportional to $m^{\lambda^{c}}$ for any $c \in \left(0, 1 \right)$. Constructions from lattices with this circuit depth were only previously known from larger moduli.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Published elsewhere. Major revision. Indocrypt 2018
 Keywords
 LatticesLearning with ErrorsPseudorandom Functions
 Contact author(s)
 hart montgomery @ gmail com
 History
 20181109: received
 Short URL
 https://ia.cr/2018/1077
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/1077, author = {Hart Montgomery}, title = {More Efficient Lattice {PRFs} from Keyed Pseudorandom Synthesizers}, howpublished = {Cryptology {ePrint} Archive, Paper 2018/1077}, year = {2018}, url = {https://eprint.iacr.org/2018/1077} }