Encryption
是否有任何算法無法生成任何零知識證明？
這與我之前的問題有關：
zkSNARK 或其他零知識證明可以在不洩露私鑰的情況下證明消息的真實性嗎？
是否有任何算法生成零知識證明的計算量如此之大，以至於主流設備（PC、智能手機）在任何實際時間都無法生成它們？
我主要對加密算法感興趣，但任何例子都會很棒。
以下是一個相當“無聊”的範例，但可能有效（我會指出我稍後做出的具體假設）。如果你也覺得它很無聊，它可能會幫助你完善你的問題，讓答案更有趣。
假設您有一些帶有安全參數的加密方案 $ n $ （我們不妨想想 $ n $ -bit RSA，任何範例都有效）。說加密需要 $ T_E = O(f(n)) $ 一些功能的時間 $ f(n) $ . 現在考慮一些你感興趣的陳述的 ZK 證明。假設它需要 $ T_P = O(g(n)) $ 是時候證明該陳述了，其中復雜性取決於為加密選擇的安全參數。
我將假設加密比證明生成更容易，或者正式 $ f(n) = o(g(n)) $ . 這似乎很自然，但我對細節不夠熟悉，無法知道它是否適用於所有加密方案/證明對（儘管如果不適用，則可以漸近地獲得特定加密方案的證明，這似乎很奇怪）。
然後我們可以考慮引入另一個參數 $ k $ （與 $ n $ )，並查看帶有安全參數的加密方案/證明系統 $ kn $ . 我聲稱以下兩件事應該成立：
- 如果 $ k $ 足夠小，使用安全參數加密 $ kn $ 在您想像的設備上仍然可行
- 作為 $ f(n) = o(g(n)) $ ，漸近證明生成將在加密之前變得不可行（因為證明生成的複雜性“嚴格地增長得更快”）。
所以如果我們採取 $ k $ 足夠大，我們預計加密和證明生成都變得不可行。但是由於兩者的漸近複雜度不同，我們預計證明生成首先變得不可行*，*所以應該有一些“中間值” $ k $ 這樣人們仍然可以加密，但不能生成證明。