减少衰变SIS

Question

在Lyu12中，引理3.6如下。

引理3.6对于任何非负整数\alpha，如gcd(2\alpha+1, q)=1，从SIS_{q, n, m, d}分解问题到SIS_{q, n, m, (2\alpha+1)d+\alpha}决策问题都存在一个多项式时间约简。

证据。为了证明这个引理，我们将给出一个变换，将SIS_{q, n, m, d}分布映射到SIS_{q, n, m, (2\alpha+1)d+\alpha}分布，并将\mathbb{Z}^{n\times m}_{q}\times \mathbb{Z}^{n}_{q}上的均匀分布映射到它自己。给定(A, t)，创建一个随机向量r \stackrel{\$}{\leftarrow} \{-\alpha, \cdot\cdot\cdot, 0, \cdot\cdot\cdot, \alpha \}^{m}并输出(A, (2\alpha+1)t+Ar)。首先，由于2\alpha+1是相对于q的质数，所以我们的转换将均匀分布映射到自己。如果(A, t) canme形成SIS_{q, n, m, d}分布，那么(2\alpha+1)t+Ar=A((2\alpha+1)S+r)，由于s是从\{-d, \cdot\cdot\cdot, 0, \cdot\cdot\cdot, d \}^{m}随机一致选择的，所以不难看出(2\alpha+1)S+r)在\{-(2\alpha+1)d-\alpha, \cdot\cdot\cdot, 0, \cdot\cdot\cdot, (2\alpha+1)d+\alpha \}^{m}中是一致随机的。

我不知道gcd(2\alpha+1, q)=1在证据中的作用。为什么不创建一个问题SIS_{q, n, m, d+\alpha}并将SIS_{q, n, m, d}转换问题简化为SIS_{q, n, m, d+\alpha}决策问题？

Answer 1

关于gcd的假设告诉您，2\alpha +1不属于\mathbb{Z}/q\mathbb{Z}的理想。例如，2\alpha +1可以除以q，然后(2\alpha+1)t永远不会像\mathbb{Z}_q^n中的一致随机向量。如果您想修复思想，假设3将q和\alpha =1分开:那么(2\alpha+1)t的条目总是有一个3的倍数，这绝对不是统一向量的样子。Ar的新增贡献可能不足以将条目“模糊”到更均匀的随机向量中:很可能您可以观察到太多的情况，其中(2\alpha+1)t+Ar的条目是3的倍数。

一般来说，有了这个假设，证明就更容易了(如果没有它，甚至不可能得到一般的证明)，并且放松对\alpha的关注。它也没有太大的限制性。