減少判定SIS
在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) $ 可以形成 $ 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} $ 決策問題？
關於 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 $ . 它也不是很嚴格。