LWE与伪随机函数

Question

考虑有错误的学习问题。假设LWE (或LWE的一个变体，类似于环LWE)对于多项式时间算法是困难的，那么我们能从这里构造一个伪随机函数族吗？

Answer 1

你可以的。这里有一个应该提到的警告-- LWE问题硬度是由模量q的大小(部分)控制的。两个重要的参数域是q在安全参数中多项式大和超多项式大.模数越小，效率越高，安全性越好。我想，直到最近，我们才从LWE得到多项式模PRF，例如这。在那篇论文之前，这导致了一种有趣的情况，我们可以用一个较弱的格子假设来构造像水平FHE这样的东西，而不是构造一个PRF。

然而，对于超级聚q，有一些简单的构造。本论文是一个很好的参考。它的关键思想是，一个LWE样本(a, \langle a,s\rangle + e)是伪随机的，因此它也是PRF的基础。如果一个人试图写下一些自然的候选人，比如：

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

有两个明显的问题：

• 只有当a是随机的时，这才是伪随机(所以这是一个“弱PRF”而不是PRF --只是一个稍微不同的密码原语)。
• F_s(a)是一个随机函数--误差e必须随机选择。

您可以通过将第二个问题舍入p的最近倍数，即编写F_s'(a) = \lfloor \langle a,s\rangle + e\rceil_p来解决它。如果q/p足够大，e的随机选择只会对最终结果产生负面影响，所以我们也可以编写(确定性)函数F_s'(a) = \lfloor \langle a,s\rangle\rceil_p。或者，这可以被看作是一个弱PRF构造的学习与四舍五入的假设。

要将弱PRF“升级”为标准PRF，可以将键设置为(A, S_1, \dots, S_k)，并定义

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.

其中，x_i\in\{0,1\}和A, S_1,\dots, S_k要么是环元素，要么是具有适当维数的矩阵，因此表达式是有意义的。这正是第五节第二份文件所作的建造。

总结如下：

• 是的，我们可以从LWE/晶格问题建立PRF。
• 有效地(从小模数)做它是令人惊讶的困难，但现在知道如何做(见第一篇论文)。
• 从LWR问题出发做这件事在概念上是简单的，但对于大模的LWE问题，我们只能将LWR问题的安全性建立在LWE问题上。

Answer 2

到目前为止，这是我的理解，如果适用的话，请改正。

1. 我们可以从任何单向函数构造PRF。效率低，需要很深的电路。
2. 我们可以从LWR假设(Banarjee，Peikert，Rosen，2011)构造PRF (如果模量是安全参数中的超多项式，则与LWE假设一样困难)。用NC^1电路。