Paper 2018/1077

More Efficient Lattice PRFs from Keyed Pseudorandom Synthesizers

Hart Montgomery

Abstract

We develop new constructions of lattice-based PRFs using keyed pseudorandom synthesizers. We generalize all of the known `basic' parallel lattice-based PRFs--those of [BPR12], [BLMR13], and [BP14]--to build highly parallel lattice-based PRFs with smaller modulus (and thus better reductions from worst-case lattice problems) while still maintaining computational efficiency asymptotically equal to the fastest known lattice-based PRFs at only the cost of larger key sizes. In particular, we build several parallel (in $NC^{2}$) lattice-based 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 lattice-based 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 LWE-based assumptions known (potentially excluding some concurrent work), respectively, and concretely require less computation per output than any known parallel lattice-based 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 LWE-based 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.