SIS与LWE问题

Question

Ajtai单向函数由

f_A(x)= Ax \; mod\; q ，其中x- \in \{0,1\}^m和A- \in \mathbb{Z_q}^{n \times m}.f_A(x)是单向函数( Ajtai 96)

而Regev单向函数(Regev 05)是在x \in \mathbb{Z_q}^k和e \in \mathscr{E}^m上定义的，\in \mathbb{Z_q}^{m \times k} .The单向函数定义为

g_A(x,e) =Ax +e \; mod\; q \; (LWE)

g_A(x,e)是一个单向函数.我的问题是，在设计新的加密方案方面，Regev的单向函数是否比Ajtai单向函数提供了优势，或者它们是否与它们的用例等效？它们在硬度方面也是等同的吗？

Answer 1

Ajtai函数的参数中存在着重要的约束，这使得它具有高度的满射性(每一幅图像都有许多预图像)。我们不知道如何从这得到一个加密方案。

相反，Regev的函数通常用于内射域。我们知道如何从它建立和加密方案。

在硬度方面，在A^t上求解SIS相当直接地允许在A上求解LWE。在另一个方向，也有一个还原，这是量子的。因此，至少对于量子计算机来说，这些问题是等价的。

这一点应该有所把握:这种减少造成了巨大的损失。特别是，LWE具有一些较大的参数，比某些参数更合理的SIS具有更高的量化难度。