什麼是標準加密假設？
我正在努力理解*“標準密碼假設”*的含義。
維基百科關於 Goldwasser-Micali 系統 (GM) 的文章寫道：“GM 的區別在於它是第一個在標準加密假設下可證明是安全的機率公鑰加密方案。”
但是什麼是標準的密碼學假設？我想
- FACTORING：給定一個正整數 $ n $ ，求其素因數分解。
- 二次剩餘問題（QRP）：給定一個奇數複合整數 $ n $ 和 $ a $ 帶有雅可比符號 $ (a|n) = +1 $ 決定是否 $ a $ 是二次餘數或偽平方模 $ n $ .
通常認為是困難的，因此是“標準密碼假設”。為什麼通用汽車可以證明是安全的？但是 RSA 問題 (RSAP) 呢？
給定一個正整數 $ n $ 這是兩個不同奇數素數的乘積 $ p $ 和 $ q $ , 一個正整數 $ e $ 和 $ \gcd(e, (p-1)(q-1)) = 1 $ 和一個整數 $ c $ . 找一個整數 $ m $ 這樣 $ m^e \equiv c \pmod n $ .
RSAP 通常也應該很難嗎？因此 RSA 是否可以證明是安全的？
我正在努力理解*“標準密碼假設”*的含義。
“標准假設”廣義上是指一個長期經受住了許多聰明的密碼分析家審查的假設。例子：
- 我們認為，對於均勻隨機 1024 位素數 $ p $ 和 $ q $ , 求解 $ y = x^3 \bmod pq $ 對於均勻隨機 $ x $ 很難給予 $ pq $ 和 $ y $ .
為什麼？任何人都能夠弄清楚如何做到這一點的最好方法是分解 $ n $ 恢復 $ p $ 和 $ q $ ，而最著名的方法——ECM 和 NFS——成本比任何人的預算都要高。
- 我們認為解決 $ y = \operatorname{AES}_k(x) $ 對於均勻隨機 $ k $ 很難給予 $ x $ 和 $ y $ .
為什麼？任何人能夠弄清楚如何做到這一點的最好方法基本上是通過通用搜尋，而最著名的方法——平行彩虹表、平行區分點——成本比任何人的預算都要高。
半例：
- 基於配對的密碼學。配對在會議上的學術密碼學中非常流行，但在現實世界中很少使用，除了異國情調的加密貨幣應用程序。對於更傳統的 DLOG 應用程序（如 Diffie-Hellman 密鑰協議和 Schnorr 簽名），配對友好橢圓曲線的安全故事遠不如橢圓曲線的安全故事穩定。
- SVP、LWE 和其他晶格問題。格是後量子密碼學的一個有前途的領域，但是有一個龐大的設計空間，其中包含一個尚未穩定下來的複雜安全故事——無論 Chris Peikert 和 Dan Bernstein 關於平均情況/最壞情況有多少完全無法理解的論點推特上的減價。
非範例：
- 辮群中的共軛搜尋。辮狀密碼學並未被密碼學家廣泛研究，並且大多數現有的提議都被證明是錯誤的。
- 西蒙和斯派克。這些分組密碼在試圖進入國際標準化的幽靈中很受歡迎，但事實證明，這些天標準機構不再樂於接受沒有技術理由的幽靈的話，而且小於 128 位的塊大小也是愚蠢的。
維基百科關於 Goldwasser-Micali 系統 (GM) 的文章寫道：“GM 的區別在於它是第一個在標準加密假設下可證明是安全的機率公鑰加密方案。”
這是學術混淆的一個例子，並且證明維基百科是學習密碼學的糟糕資源。它的意思是：
- 我們證明了一個定理，1，這個定理涉及漂亮的數論2和漸近增長曲線！3
1這就是可證明的安全性的意思。這並不意味著該定理對現實世界有任何影響。
2這就是“標准假設”的含義*：*不允許出現像反相 DES 這樣的醜陋問題，但允許出現像分解均勻隨機素數乘積這樣的漂亮問題。
3未正式聲明：我們只對一系列問題的攻擊成本的漸近增長曲線感興趣*，因此 DES 被雙重取消資格，因為它很醜，而且因為只有一個 DES，而您可以將因式分解問題視為因素的大小。（“可證明的安全性”處理在 Bellare 和 Rogaway 的幫助下，具體的參數選擇*，有時被稱為“精確的安全性”，直到十年後才出現。）
公平地說，GM 論文有助於製定一些形式化，例如公鑰加密的語義安全性，這基本上等同於我們今天使用的現代密文不可區分性標準。但是GM加密方案呢？完全沒用，即使有定理。
這種混淆——以及對數論美的迷戀——導致人們走上令人遺憾的道路，比如採用 Dual_EC_DRBG，它承認“基於數論的安全性”的證明，作為主要的國家密碼標準，僅僅憑藉數論，推動由像丹布朗這樣的高級數字專家，他們的主要專業領域是在大量的分析散文中混淆打開的後門，沒有人可以通過。
RSAP 通常也應該很難嗎？因此 RSA 是否可以證明是安全的？
RSA 問題——計算 $ e^{\mathit{th}} $ 以大秘密素數的乘積為模的根——通常被認為是困難的。有一些由 RSA 建構的公鑰加密方案和公鑰簽名方案，它們具有一定的定理——例如，RSAES-OAEP、RSA-KEM、RSASSA-PSS、RSA-FDH——它們在關聯破解難度方面甚至有些用處密碼系統的安全性（區分密文、偽造簽名）對計算的難度 $ e^{\mathit{th}} $ 根模數是大秘密素數的乘積。
但我建議您遠離不誠實的藝術術語“可證明的安全性”，因為它混淆了您的實際意思——尤其是“X 可證明安全”的形式。
一個方案是否具有“可證明的安全性”與使用者或工程師對建構系統的決策無關——密碼分析家關於什麼密碼學能夠承受攻擊的結論與他們相關。“可證明的安全性”實際上是指導密碼分析者集中精力。 將 AES-CTR 與 AES 分開分析是沒有意義的，因為任何破壞 AES-CTR 的方法都是（a）取決於對 CTR 的濫用，（b）基於 AES 作為排列而不是任意函式的性質，或者（c ) 意味著對 AES 的攻擊。這是因為有一個有用的定理將對 AES-CTR 的任何攻擊與對 AES 本身的攻擊聯繫起來。
同樣，在不嘗試計算的情況下嘗試偽造 RSA-FDH 簽名也沒有多大意義 $ e^{\mathit{th}} $ 根，因為——多虧了一個有用的定理——我們知道對一個問題所做的任何工作都會立即轉化為另一個問題，只要散列函式不以任何有趣的方式與 RSA 互動（這將是非常令人驚訝的）。所以密碼分析者可以忽略 RSA-FDH 的細節而專注於計算 $ e^{\mathit{th}} $ 根讓我們對 RSA-FDH 的安全性充滿信心。