RLWE 承諾問題
讓 $ (R , \chi $ ) 是一個標準的 RLWE 問題實例。IE $ R $ 是有限域上的有限次多項式環，並且 $ \chi $ 是 R 上的一些高斯分佈，變異數很小。
我想知道下面的承諾問題是否很難。
讓 $ a_0 $ 和 $ a_1 $ 是兩個隨機元素 $ R $
挑戰者選擇了一個布爾值 $ b $ 和兩個元素 $ s,e \in \chi $ , 併計算 $ c= a_b s + e $ .
那麼問題是：
給定 $ c, a_0, a_1 $ ， 計算 $ b $ 具有不可忽視的優勢。
動機：
如果這個 promise 問題變得很難，人們可以使用 PACE 的自然 PQ 替代，PACE是電子護照中使用的密碼認證密鑰協商協議。（見 國際民航組織文件 9303）
（看來證明可以挽救了。）
讓 $ \text{RLWE} $ 表示標準環 LWE 問題，其中秘密 $ s $ 均勻地從 $ R $ . 就這樣 $ \text{RLWE} $ 假設是：
$$ (a,as+e)\approx(a,r):a,r,s\leftarrow R, e\leftarrow\chi, $$ 在哪裡 $ \approx $ 表示計算不可區分性。 $ \text{RLWE} $ 假設意味著非標準LWE 假設$$ Lemma 2, ACPS09 $$, 表示 $ \text{RLWE’} $ , 秘密的來源 $ \chi $ : $$ (a,as+e)\approx(a,r):a,r\leftarrow R, s,e\leftarrow\chi. $$ 承諾問題的難度，表示為 $ \text{RLWE’’} $ , 後跟一個混合參數（見下文）假設 $ \text{RLWE’} $ 持有。因此，減少鍊是： $$ \text{RLWE}<\text{RLWE’}<\text{RLWE’’}. $$ *混合論證。*我們想證明這兩個分佈
$$ D_L:=(a_0,a_1,a_0s+e) \text{ and } D_R:=(a_0,a_1,a_1s+e) $$ 在計算上無法區分，因為 $ a_0,a_1\leftarrow R $ 和 $ s,e\leftarrow \chi $ . 考慮混合分佈 $$ D_H:=(a_0,a_1,r) $$ 在哪裡 $ a_0,a_1,r\leftarrow R $ . 我們表明 $ D_L\approx D_H $ 和 $ D_H\approx D_R $ , 並且它遵循傳遞性 $ D_L\approx D_R $ . 看到那個 $ D_L\approx D_H $ , 假設矛盾不是: 存在一個算法 $ \mathsf{A} $ 區分 $ D_L $ 從 $ D_H $ . 我們表明 $ \mathsf{A} $ 可以用來打破 $ \text{RLWE’} $ . 減少 $ \mathsf{R} $ 很簡單：給定一個 $ \text{RLWE’} $ 挑戰 $ (a,b) $ （在哪裡 $ a\leftarrow R $ 和 $ b $ 或者是 $ as+e $ 或者 $ r $ ), $ \mathsf{R} $ 樣品 $ a’\leftarrow R $ 並發送 $ (a,a’,b) $ 至 $ \mathsf{A} $ 並輸出給它的挑戰者 $ \mathsf{A} $ 輸出。如果 $ b=as+e $ 然後 $ \mathsf{A} $ 模擬 $ D_L $ ; 否則它模擬 $ D_H $ .
論證顯示 $ D_H\approx D_R $ 很相似。
參考。
$$ ACPS09 $$Applebaum、Cash、Peikert 和 Sahai。基於硬學習問題的快速密碼原語和循環安全加密。加密貨幣 2009。