Hardness-Assumptions
互動假設的概念是什麼？
在這篇論文：Sequential Aggregate Signatures with Short Public Keys: Design, Analysis and Implementation Studies中，作者將這篇論文作為第一個提出沒有像 LRSW 那樣的互動假設但具有靜態假設的聚合簽名的論文。是什麼使假設具有互動性？不是標準的事實：DDH、CDH、DL、QR、RSA 等眾所周知的假設？
您可以根據與對手玩的遊戲來定義大多數難度假設。有關詳細資訊，請參見 Shoup & Bellare-Rogaway。
**範例：**您可以根據以下游戲定義 DDH 假設：
- 挑戰者隨機選擇一個位 $ \beta $ ; 並且隨機 $ a,b,c \gets \mathbb{Z}_p $ . 他計算 $ A = g^a; B=b^b $ 和 $ C = \begin{cases}g^{ab} & \mbox{if }\beta =0 \ g^c& \mbox{if } \beta=1\end{cases} $ 並發送 $ A,B,C $ 給對手。
- 對手試圖猜測 $ \beta $ .
**範例：**您可以根據以下游戲定義 CPA 安全（公鑰）加密：
- Challenger 生成密鑰對 $ (sk,pk) $ 並給出 $ pk $ 給對手。
- 對手選擇兩個明文 $ m_0, m_1 $ .
- 挑戰者選擇隨機位 $ \beta $ 並給出 $ \textsf{Enc}(pk,m_\beta) $ 給對手。
- 對手試圖猜測 $ \beta $ .
第一個遊戲是非互動式的，對手只是接收值（對手的最終猜測並未真正計算在內）。所以 DDH 是一個非互動式的假設。
第二個遊戲是互動式的，因為允許對手在看到公鑰後選擇他的明文。因此 CPA 安全性是一個互動式假設。
現在假設您正試圖證明您的某些互動式系統是安全的。您始終可以將“我的系統是安全的”作為假設，但在這種情況下您實際上並沒有做任何事情。另一方面，如果您將互動式系統的安全性建立在非互動式假設之上，那麼您實際上一定做了一些不平凡的事情。一般來說，我們希望將安全性建立在最簡單的假設之上，而互動是衡量假設“簡單性”的一種自然方式。
維克多·舒普。遊戲序列：一種用於控制安全證明復雜性的工具。密碼學 ePrint 檔案，報告 2004/332，2004。
米希爾·貝拉爾和菲利普·羅加威。*三重加密的安全性和基於程式碼的遊戲證明框架。*在 EUROCRYPT 2006，LNCS vol 4004，p409-426。