Lattice-Crypto
證明這兩個分佈對於 LWE 減少是相同的
作為我試圖建構的縮減的一部分，我想證明底部描述的兩個術語是相同分佈的，但我不確定這是否正確，我似乎無法證明它是正式的。我試圖以類似於麻省理工學院在本pdf第5頁頂部的減少來製定我的減少。
表示 $ \in_R $ 從集合中隨機統一選擇，讓：
$ A\in_{R} \mathbb{Z}^{m\times n}_q $
$ r \in_{R} {0,1}^m $
$ l, s \in_{R} {0,1}^n $
$ k \in_R {0,1} $
那麼以下是同分佈的：
$$ (r^T A +\frac{q}{2} l, r^T As+r^Te+\frac{q}{2}k) $$ $$ (r^T A, r^T As+r^Te) $$
在哪裡 $ e $ 是 LWE 中使用的誤差項。
例如，我嘗試過計算， $ \Pr[r^TA+\frac{q}{2}l+r^Te=a] $ 為了一些價值 $ a $ 為了證明它等於 $ \Pr[r^TA+r^Te=a] $ ，但這並不富有成效。
我可以說兩者解密為相同的值。這有什麼幫助嗎？
我不完全清楚你在這裡想要做什麼。通常使用 LWE 構造，我們試圖證明事物在計算上是不可區分的，而不是相同分佈的。此外，試圖區分的人通常可以訪問 $ A $ 在這種情況下，很有可能，您的問題有一個非常簡單的區分器。我們計算 $ A^{-1} $ （很有可能存在），然後給出一個樣本 $ (x,y) $ 我們計算 $ xA^{-1} $ . 如果這僅由零和一組成，則以壓倒性的機率從第二組中採樣，如果不是全零和一，則肯定從第一組中採樣。