3
$\begingroup$

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?

$\endgroup$

2 Answers 2

8
$\begingroup$

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.
$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – Hhan
    Dec 8, 2021 at 0:49
4
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.