Score:2

LWE and pseudorandom functions

sy flag

Consider the learning with errors problem. Assuming LWE (or a variant of LWE, like ring LWE) is hard for polynomial time algorithms, can we construct a family of pseudorandom functions from there?

Score:4
cg flag

This is my understanding so far, please correct if applicable.

  1. We can construct PRF from any one-way function. Inefficient and require deep circuits.
  2. We can construct PRF from LWR assumption (Banarjee, Peikert, Rosen, 2011) (as hard as the LWE assumption if the modulus is superpolynomial in the security parameter). With $NC^1$ circuit.
Score:4
ng flag

You can. There is a certain caveat that should be mentioned here --- the LWE problems hardness is controlled (in part) by the size of the modulus $q$. Two important parameter regimes are $q$ being polynomially large in the security parameter, and super-polynomially large. Smaller modulus is better for both efficiency and security. I think only recently we have polynomial modulus PRFs from LWE though, see for example this. Until that paper, this led to the funny situation where we could construct things like leveled FHE from a weaker lattice assumption than what we needed to construct a PRF.

For super-poly $q$ though, there are simple constructions. This paper is a good reference. The key idea is that an LWE sample $(a, \langle a,s\rangle + e)$ is pseudo-random, so is plausibly the basis for a PRF. If one tries to write down some natural candidate, such as:

$$F_s(a) = \langle a,s\rangle + e\bmod q$$

there are two obvious problems:

  • this is only pseudorandom if $a$ is random (so this is a "weak PRF" rather than a PRF --- just a slightly different cryptographic primitive)

  • $F_s(a)$ is a randomized function --- the error $e$ must be randomly chosen.

You can fix this second problem via rounding it to the nearest multiple of $p$, i.e. writing $F_s'(a) = \lfloor \langle a,s\rangle + e\rceil_p$. Provided that $q/p$ is large enough, the random choice of $e$ will only negligibly often impact the final result, so we may as well write the (deterministic) function $F_s'(a) = \lfloor \langle a,s\rangle\rceil_p$. Alternatively, this can be seen as a weak-PRF constructed from the Learning with Rounding assumption.

To "upgrade" the weak-PRF to a standard PRF, one can make the key be $(A, S_1, \dots, S_k)$, and define

$$F_{A, S_1,\dots, S_k}(x_1,\dots,x_k) = \left\lfloor A\prod_{i =1}^k S_i^{x_i}\right\rceil_p.$$

Where $x_i\in\{0,1\}$, and $A, S_1,\dots, S_k$ are either ring elements, or matrices with appropriate dimensions such that the expression makes sense. This is precisely the construction done in the second paper in section 5.

In summary:

  • Yes we can build PRFs from LWE/lattice problems
  • Doing it efficiently (from small modulus) was surprisingly hard, but is now known how to be done (see the first paper)
  • Doing it from the LWR problem is conceptually simple, but we can only base the security of the LWR problem on the LWE problem for large modulus.
Hhan avatar
jp flag
I think we can construct poly-modulus LWE-based PRF using GGM generic construction and it might be explicitly mentioned in the first paper. Of course, there are many advantages of PRFs in the first paper, e.g. have a better concrete parameter, low-depth in practice, and key-homomorphic.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.