我們對 KEA1 假設的信任程度如何？
讓
$$ (g,h=g^s,q) $$是一個元組，使得 $ g $ 是一個組的生成器 $ \mathbb{G} $ 順理成章的 $ q $ 和 $ s $ 是均勻隨機的 $ \mathbb{Z}_q $ . 指數知識（ KEA1 ）假設表明，對於任何對手 $ \mathcal{A}(g,h,q) $ 輸出一個值 $ (C,Y) $ 這樣 $ C^s \equiv Y $ 那麼存在一個提取器 $ \mathcal{B} $ 在同一輸入上輸出一個值 $ x $ 這樣 $ g^x \equiv C $ .
粗略地說，這個假設說計算元組的唯一方法 $ (C,Y) $ 實際上，通過知道指數 $ x $ .
這個假設首先由 Ivan Damgård 在 91 年的論文*“Towards Practical Public Key Systems Secure against Chosen Ciphertext Attacks”*中提出。
我的問題是，我們在多大程度上相信這個假設？它可以還原為其他東西嗎？
我不確定如何回答假設中有關“信任”的問題。我認為這是個人信仰問題，而不是科學問題。我們不知道任何密碼學假設的真實性，儘管顯然有些人比其他人受到了更多的審查。我想說的是，KEA 假設受到的關注相對較少，因此應盡可能避免。但是，我懷疑如果您要問這個問題，那麼就無法避免它。
至於可還原性問題，它不能還原為任何人們可能稱之為“標準”假設的東西。這實際上是設計使然。標准假設，例如 RSA 假設或 DDH 假設，在某種意義上是“可證偽的”，即如果假設為假，那麼（原則上）很容易舉出反例。在 RSA 或 DDH 的情況下，反例將是成功解決難題的算法 A。即使您不知道 A 是如何工作的，也很容易通過隨機抽樣 RSA 複合/DDH 元組並查看 A 成功的頻率來驗證 A 實際上是一個有效的攻擊者。
相比之下，指數假設的知識是密碼學家使用的少數不可證偽的假設之一。（最常見的不可證偽的“假設”是隨機預言的概念，儘管這本身並不是一個真正的假設。）KEA1 可能是錯誤的，但我不可能向你證明它是錯誤的通過向您展示這一主張的一些簡單見證。