如何證明隨機加密算法的安全性？
我在公鑰設置中設計了一個隨機加密。我對它的安全保證深信不疑，但我需要一種正式的方法來證明它的穩健性。如何證明這種隨機公鑰加密算法的安全性？任何證明方法，例如歸納法，矛盾法證明或其他任何證明方法？
我正在嘗試在期刊論文中發表該算法。這就是為什麼我需要一個正式的證明。
你想做的就是正確的方法。然而，這不是一件容易的事。
您真正想要做的是顯示以下含義：
$$ \newcommand{\hard}{\operatorname{hard}} \newcommand{\assumption}{\text{assumption}} \newcommand{\secure}{\operatorname{secure}} \hard(\assumption_1)\land\ldots\land\hard(\assumption_n) =\bigwedge_{i=1}^n\hard(\text{assumption}_i)\ \implies\secure(\text{cryptosystem}) $$ 對於（希望）少數已經充分研究的假設。
這種證明的通常直覺是歸約證明，這是一個邏輯對立：
$$ \neg\secure(\text{cryptosystem})\implies\bigvee_{i=1}^n\neg\hard(\assumption_i) $$ 這意味著您需要證明破壞密碼系統的安全性意味著您的任何假設都不難。 當然，你首先需要找出什麼“ $ \hard(\assumption_i) $ “ 和 ” $ \secure(\text{cryptosystem}) $ “實際上的意思。後者是一個（最好）強大的安全定義，很可能來自這個列表。前者在很大程度上取決於手頭的實際假設，您需要查看所述假設的實際、精確定義。例如這個部落格文章涵蓋了 RSA，這篇文章涵蓋了典型的 DH 假設。
現在是最後也是最困難的部分：如何實際製作證明。這個問題沒有簡單的答案。例如，您可以查看遊戲跳躍以及基於模擬的證明。您還可以查看證明/驗證工具是否可以一路幫助您，例如 Biv here和here所描述的。關於這一點沒有什麼可說的，除了：查看給出的參考資料，從那里通過他們給出的參考資料開始工作，繼續閱讀參考資料，直到您理解這些證明並能夠執行你需要的那個。這可能是一個艱難和/或漫長的旅程，但它會得到回報。