Regev公鑰密碼體制的解密分析
Regev 的公鑰密碼系統定義如下：
我想證明正確性。為此，必須證明 0 被正確解碼，同樣 1 也被正確解碼。一旦我證明了，我會在這裡展示：
案例：0的加密
$$ b = \sum_{i \in S} b_i = \sum_{i \in S} ( \langle \mathbf{a_i},\mathbf{s} \rangle + e_i) = \langle \mathbf{a},\mathbf{s} \rangle + \sum_{i \in S} e_i \Rightarrow b - \langle \mathbf{a},\mathbf{s} \rangle = \sum_{i \in S} e_i $$ 我們從定義中知道 $ |e| < \frac{\lfloor \frac{p}{2} \rfloor}{2} $ 使用這個事實我們可以寫： $$ |b - \langle \mathbf{a},\mathbf{s} \rangle | = \left| \sum_{i \in S} e_i \right| < \frac{\lfloor \frac{p}{2} \rfloor}{2} $$ 這比 0 更接近於 $ \lfloor \frac{p}{2} \rfloor $ ，所以對a 0 的解密是正確的。
案例：加密1
$$ b = \lfloor \frac{p}{2} \rfloor + \sum_{i \in S} b_i = \lfloor \frac{p}{2} \rfloor + \sum_{i \in S} ( \langle \mathbf{a_i},\mathbf{s} \rangle + e_i) = \lfloor \frac{p}{2} \rfloor +\langle \mathbf{a},\mathbf{s} \rangle + \sum_{i \in S} e_i \Rightarrow b - \langle \mathbf{a},\mathbf{s} \rangle = \lfloor \frac{p}{2} \rfloor + \sum_{i \in S} e_i $$
使用三角不等式我們可以寫：
$$ | b - \langle \mathbf{a},\mathbf{s} \rangle | = \left| \lfloor \frac{p}{2} \rfloor + \sum_{i \in S} e_i \right| \geq -\left| \sum_{i \in S} e_i \right| + \left| \lfloor \frac{p}{2} \rfloor \right| $$
自從 $ -|e| > -\frac{\lfloor \frac{p}{2} \rfloor}{2} $ 我們可以寫：
$$ | b - \langle \mathbf{a},\mathbf{s} \rangle | = \left| \lfloor \frac{p}{2} \rfloor + \sum_{i \in S} e_i \right| \geq -\left| \sum_{i \in S} e_i \right| + \left| \lfloor \frac{p}{2} \rfloor \right| > -\frac{\lfloor \frac{p}{2} \rfloor}{2} + \left| \lfloor \frac{p}{2} \rfloor \right| $$
這更接近 $ \lfloor \frac{p}{2} \rfloor $ 而不是 0，所以 1 的解密是正確的。
我不確定我的證明的第二種情況，所以我希望更正或確認。另一個問題是關於解密的限制。如果我沒有誤導的話，那麼範圍內的一切 $ -\frac{\lfloor \frac{p}{2} \rfloor}{2} < x < \frac{\lfloor \frac{p}{2} \rfloor}{2} $ 被解釋為 0 和範圍內的所有內容 $ \frac{\lfloor \frac{p}{2} \rfloor}{2} < x < \frac{3 \lfloor \frac{p}{2} \rfloor}{2} $ 解釋為1，你能這麼說嗎？
這在很大程度上是正確的，儘管你的第二種情況也需要雙面約束 $$ \lfloor\frac p2\rfloor-\frac{\lfloor\frac p2\rfloor} 2<b-\langle\mathbf a,\mathbf s\rangle<\lfloor\frac p2\rfloor+\frac{\lfloor\frac p2\rfloor} 2 $$ 而您的論點僅涵蓋左手不等式。相反，如果我們只是注意到 $$ -\frac{\lfloor\frac p2\rfloor} 2<\sum e_i<\frac{\lfloor\frac p2\rfloor} 2 $$ 很有可能（我們是否可以肯定地說這取決於 $ \chi $ ) 然後注意 $ \lfloor\frac p2\rfloor+\sum e_i=b-\langle \mathbf a,\mathbf s\rangle $ 然後一切都井井有條。