Encryption
基於#P-完全問題的密碼學
是否有任何基於#P-complete 問題（平均情況形式）的密碼方案範例？
我們甚至不知道如何建立密碼學基礎 $ \mathbf{NP} $ - 完整性更不用說 $ #\mathbf{P} $ -完整性。此外，基於密碼學存在已知的障礙 $ \mathbf{NP} $ -完整性：
$$ AGGM,BT $$，並且$$ Chapter 7, B $$. 也就是說，它願意做出額外的假設 $ #\mathbf{P} $ -硬度可能有用：例如，在
$$ CHK+ $$，表明在隨機預言模型中，硬度為 $ #SAT $ （這是完整的 $ #\mathbf{P} $ ) 可以產生納什的硬分佈，即計算納什均衡的問題（例如，兩人遊戲）。 $$ AGGM $$: Akavia、Goldreich、Goldwasser 和 Moshkovitz，基於 NP 硬度的單向函式，STOC 2006 $$ B $$: Brzuszka，關於密鑰交換的基礎，博士論文，2013 $$ BT $$: Bogdanov 和 Trevisan，關於 NP 問題的最壞情況到平均情況減少，FOCS 2003 $$ CHK+ $$: Choudhuri 等人，找到納什均衡並不比打破 Fiat-Shamir 更容易，STOC 2019
更新：以下答案不涵蓋原始問題。這是混淆p-complete和#p-complete的結果。
第一個公鑰密碼算法是基於 p 完全問題。它今天被稱為Merkle Puzzle。粗略地說，接收方和發送方的密鑰交換複雜度為 $ \mathcal{O}(n) $ 而成功的攻擊複雜度是 $ \mathcal{O}(n^2) $ .
儘管在現代密碼學中，它不再被認為是安全的，但默克爾的想法改變了密碼學的一切。