RLWE 搜尋決策：oracle 在所有自同構圖像上工作的機率
在觀看了這篇演講https://www.youtube.com/watch?v=Eg_pyyeT_Qc&feature=plcp之後，我試圖將提出的 Ring LWE 的搜尋到決策減少正式化，但在某一點上卡住了。
我了解我們如何構造一個找到秘密的第 k 個係數的算法（在“中文剩餘表示”中，所以真的 $ s(\zeta^k) $ 以團結為根 $ \zeta^k $ ) 對於給定的 k。為此，我們使用可以區分真實 RLWE 樣本和統一樣本的預言機。據我所知，這個“區分”意味著 $ Pr[O(f, fs + e)] - Pr[O(f, U)] $ 是不可忽略的，其中 $ f, U, s $ 是均勻分佈的隨機變數 $ R_q $ . 但這意味著，預言機和我們的算法*只能保證找到 $ s(\zeta^k) $ 對於所有輸入的不可忽略的一部分。使用從平均到最壞情況的減少，我們可以讓它適用於所有人 $ s $ ，但不一定適用於所有人 $ f $ ，所以我們的算法可能只適用於樣本 $ (f, fs + e) $ 在哪裡 $ f $ 在一些不太小的集合中 $ S $ .
我現在的問題是：到目前為止我的理解是否正確，如果是，自同構想法（找到其他係數）如何工作？如果 $ \sigma $ 是一個可以保持誤差分佈的域自同構，我們知道 $ (\sigma(f), \sigma(fs + e)) $ 也是一個有效的 RLWE 樣本，但不能保證該算法將在該樣本上正確工作（它只需要在所有樣本中的不可忽略的一小部分上工作） $ f $ s)。自從 $ (\sigma(f), \sigma(fs + e)) $ 和 $ (f, fs + e) $ 也不是獨立的，算法不必以相對較高的機率工作。
換句話說：為什麼假設的預言機不可能區分真實的 RLWE 樣本 $ (f, fs+e) $ 和均勻的樣品完美地為一半 $ f $ 並有可能接受 $ 0.5 $ 在其他情況下* 以這樣的方式，對於每個 $ f $ 存在自同構 $ \sigma $ （保留錯誤分佈）以便預言機無法執行 $ (\sigma(f), \sigma(fs + e)) $ ?
我還看了這篇論文（我認為證明最初已經在那裡發表）http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.400.7900&rep=rep1&type=pdf，但我做到了找不到有關此問題的詳細資訊。
(*當然，oracle 不會被呼叫 $ (f, fs + e) $ 而是在 $ (f + v, fs + e + vk) $ ，但這不應該從根本上改變事情）
如果我的問題不清楚或不夠正式，請告訴我。我沒有包括我完整的目前證明部分，因為這個問題已經很長了。
（論文的完整版在https://eprint.iacr.org/2012/230，我在下面的回答參考了它。）
您的問題的答案是減少的不同部分確保預言機與隨機樣本相比具有非常接近 1 的優勢 $ (a_i, a_i s + e_i + r_i) $ ，即預言機輸出幾乎所有選擇的正確答案 $ s, a_i, e_i, r_i $ . 有了這個保證，引理 5.5 和 5.9 給出了一個簡化，它使用自同構和“猜測和檢查”技術解決了搜尋問題。
我所指的減少的另一部分在第 5.2 節中描述，關於“最壞情況到平均情況的決策”（引理 5.12）。這使用了一種非常標準的“放大”技術來提高預言機的顯著優勢，通過在獨立樣本上反複呼叫它並測量它接受的頻率。