是否有可能使用預言機實現完全安全的公鑰加密？
密碼學的一個基本定理是不可能有一個完全安全的公鑰加密方案。那是因為對手可以搜尋所有可能的私鑰。
但我想知道是否可以使用 oracles 來實現。我的問題是，是否存在自然數集 $ A $ 和 $ B $ 這樣，如果 Alice 可以訪問預言機 $ A $ Bob 可以訪問預言機 $ B $ ，那麼這些預言機可以用作完全安全的公鑰加密方案的私鑰嗎？
我認為在這種情況下可能會有完美的安全性，因為對手要搜尋的集合數不勝數。
是的，可以使用預言機獲得完全安全的公鑰密碼術（儘管我將展示的預言機似乎不能完全簡化為問題的預言機）。
正如問題中所指出的那樣，不可能有一個完全公開的加密程序有效（在某種意義上，可以使用適當的秘密進行解密）並且是完全安全的（從某種意義上說，任意強大的對手無法破譯）。
證明（不呼叫私鑰）：加密是一種算法，可以簡化為確定性算法，其中輸入要加密的明文和額外的位串，在正常使用中是隨機的。任意強大的對手可以嘗試通過增加最大長度排序的輸入，直到找到一個加密為密文的輸入。由於可以解密，所以只能有一個。
一個更簡單的推理表明，不可能有一個完全公開的簽名驗證程序有效（從某種意義上說，可以使用適當的秘密進行簽名）並且絕對安全。
如果我們將加密過程替換為進行加密的加密預言機，則可以解決該問題。
我將使用符號 $ \tilde x $ 對於位串編碼的整數 $ x $ 每個大端二進制。
讓一個加密預言機用於以下消息 $ b $ 位，可用 $ 2^t $ 次
包含
- $ 2^{t+b} $ 位串 $ s_{i,j} $ 的 $ m $ 每個位，與 $ i\in[0,2^t) $ , $ j\in[0,2^b) $ ，隨機選擇，除了 $ \forall i,j,j’ $ ， 它擁有 $ b_{i,j}=b_{i,j’}\implies j=j’ $ .
- 一個 $ t $ -bit 位串 $ n $ , 初始全零
並在輸入一個 $ b $ 位消息 $ m $
如果 $ n $ 不是萬能的
- 計算 $ c\gets n\mathbin|s_{\tilde n,\tilde m} $
- 更改其儲存 $ n $ 至 $ n’ $ 這樣 $ \tilde n’=\tilde n+1 $
- 輸出密文 $ c $
讓對應的解密預言機
包含
- 相同 $ 2^{t+b} $ 位串 $ s_{i,j} $
並在輸入一個 $ t+b $ 位密文 $ c $
- 分裂 $ c $ 進入 $ t $ -少量 $ n $ 的和 $ b $ -少量 $ x $
- 查找位串 $ m $ 這樣 $ s_{\tilde n,\tilde m}=x $
- 輸出密文 $ c $
以下易於驗證的屬性可以被認為是完全保密的：
- 解密預言機對加密預言機產生的密文進行正確解密；
- 任何可以訪問與合法使用者相同的加密預言機的對手在IND-CPA 遊戲中都沒有優勢，就像 OTP 一樣。
可以訪問合法使用者使用的加密預言（而不是原始加密預言）的單個副本的對手具有微小的、可量化的優勢（最好的策略是猜測明文，將其送出加密，如果密文匹配：輸出該猜測；否則輸出消息的另一個猜測）。可以通過將隨機位串附加到 $ n $ 在加密。
如果我們願意放棄更多的完全保密，我們可以假設攻擊者對加密預言機的查詢數量有限。在這種情況下，加密預言可以簡化為單個大的固定隨機排列，而解密預言可以簡化為逆排列。教科書 RSA 有時以這種方式建模（如果查詢是隨機的，那麼這是一個公平的模型，掩蓋了乘法屬性和一些特殊的輸入/輸出對）。