Provable-Security
計算安全性和可證明安全性之間有什麼關係？
我讀了《現代密碼學導論》這本書。它首先給出了私鑰加密的計算安全的概念，它來源於完美的安全性和統計的安全性。
讓 $ (E,D) $ 是一個加密方案，使用 $ n $ -bits 密鑰進行加密 $ l(n) $ 長度消息。 $ (E,D) $ 在計算上是安全的，如果 $$ E_{U_{n}}(x_{0}) \approx E_{U_{n}}(x_1) $$
然後它介紹了安全遊戲（例如CPA，CCA）？我認為這是可證明的安全性的一部分。
“無條件安全”（或“資訊論安全”或“完全保密”）和“計算安全”是兩個相反的安全類別。但我不認為“計算安全”和“可證明安全”是兩個獨立的安全類別。我知道計算安全強調攻擊者的力量是有界的（多項式時間算法）。可證明的強調數學假設或密碼學原語。但這也與計算能力有關。
“可證明的安全性”只是意味著有一個定理。 這是一個誤導性的藝術術語，如果使用的話，應該小心地限制在文獻中，因為它給人一種錯誤的信心：一個系統在存在定理的意義上可以具有“可證明的安全性”，並且可能是完全可破解的。有不同種類的定理，但讓我們關注是否存在定理，並通過一些可證明的與推測的安全性範例。
- 為什麼我們認為很難找到 $ x $ 給定 $ y = x^3 \bmod{pq} $ 什麼時候 $ p $ 和 $ q $ 是獨立的均勻隨機 1024 位素數和 $ x $ 是下面的均勻隨機非負整數 $ pq $ ?
- 近半個世紀以來，地球上一些最聰明的密碼分析家一直在努力解決這個問題，並且只有始終如一的失敗記錄。也許明天有人會找到一種方法來做到這一點：我們還沒有排除它。例如，如果他們找到了一種方法來分解 $ pq $ ，他們可以很容易地計算出 $ y^d \bmod{pq} $ 在哪裡 $ d $ 解決$$ 3d \equiv 1 \pmod{\operatorname{lcm}(p - 1, q - 1)}. $$ 事實上，只要有無限的預算或量子電腦，他們就可以輕鬆做到這一點。
- 這就是 RSA 問題，具有計算推測的安全性。當然，這個系統對應用程序沒有直接用處，因為大多數應用程序自然不會處理隨機 1024 位素數或統一隨機“消息”以 1024 位素數的乘積為模。它主要是實用密碼系統的建構塊。
- 為什麼我們認為很難找到 $ m $ 給定 $ m + p $ 為了 $ m, p \in \operatorname{GF}(2^t) $ , 當分佈在 $ p $ 有統計距離 $ \varepsilon $ 從制服和 $ m $ 有分佈嗎？
- 有一個定理表明任何決策算法的顯著優勢，即猜測均勻隨機的機率超過 1/2 $ b $ 給定 $ m_b + p $ 對於任何選擇 $ m_0, m_1 $ , 有界 $ \varepsilon $ . 密碼分析方面的任何突破都無法改變結果——任何安全失敗都保證是由於 pad 重用或 pad 生成不佳造成的。
- 這是一次性填充定理的公式，具有資訊論可證明的安全性。當然，這個系統對應用程序並不直接有用，因為你需要一個方法來選擇 $ p $ 從與您可能的消息空間一樣大的空間中，並為每條消息獨立完成。它主要是實用密碼系統的建構塊。
- 為什麼我們認為很難找到 $ m $ 給定 $ (x^3 \bmod{pq}, m + H(x)) $ 在哪裡 $ x $ 是一個統一的隨機秘密， $ p $ 和 $ q $ 是統一的隨機秘密 1024 位素數，並且 $ H $ 是統一隨機公共函式嗎？
- 有一個定理，使用（2）中的一次性填充定理作為引理，如果存在具有顯著優勢的決策算法 $ \varepsilon $ 針對這個系統，那麼有一個算法可以恢復 $ x $ 從 $ x^3 \bmod{pq} $ 機率很高；換句話說，如果(1) 的 RSA 問題很難，那麼解密 $ (x^3 \bmod{pq}, m + H(x)) $ 恢復 $ m $ 很難。如 (1) 所示，密碼分析的突破可能會導致因式分解 $ pq $ 打破這個；同樣，由於我們使用隨機預言模型突破了我們選擇的特定散列函式的密碼分析 $ H $ 可以打破這個。
- 這是 RSA-KEM/DEM 的較弱版本，具有計算可證明的安全性。該定理的if/then結構，使用一次性填充引理來證明它，使密碼分析者能夠將精力集中在 RSA 問題上，而不是在 $ (x^3 \bmod{pq}, m + H(x)) $ 問題、RSASSA-PSS 問題、RSA-KEM 問題等 。當然，這個系統實際上並不安全；你想要一個真正的 DEM，它 $ m + H(x) $ 不是——如果你使用這個系統，你會為自己設置EFAILure。如果有人解決了 RSA 問題，這仍然具有計算可證明的安全性；該定理將是空洞的！
- 為什麼我們認為這很困難，給定一個消息 $ m \in x\cdot\mathbb F_q \setminus {0} $ 及其驗證器 $ a = m(r) + s $ 對於均勻隨機 $ r, s \in \mathbb F_q $ 和 $ q $ 一個主要的力量，找到另一個消息/身份驗證器對 $ (m’, a’) $ 也很滿足 $ a’ = m’(r) + s $ ? （這裡我們將消息解釋為域上的多項式 $ \mathbb F_q $ 常數項為零，例如通過將其分解為 $ ({\leq}\log_2 q) $ -bit 塊並將它們注入 $ \mathbb F_q $ 作為係數。）
- 有一個定理$$ \Pr[a’ = m’(r) + s \mid a = m(r) + s] \leq \ell/q, $$在哪裡 $ \ell $ 是消息的最大長度。換句話說，一次性偽造機率為 $ \ell/q $ . 與（1）中的一次性填充定理一樣，密碼分析的任何突破都不會改變這一定理。
- 這是一種通用散列一次性身份驗證器，具有資訊論可證明的安全性。當然，這僅適用於單個消息，因此它主要用作實用密碼系統（如 crypto_secretbox_xsalsa20poly1305 或 AES-GCM）的建構塊。而且，當然，安全性取決於參數的選擇：當 $ q = 2 $ ，但是 1/2 的偽造機率界不是很安全！