如何在指數知識假設中找到提取器？
來自 Mihir Bellare 的論文
讓 $ q $ 是一個素數，使得 $ 2q +1 $ 也是素數，讓 $ g $ 成為訂單的生成者 $ q $ 的子群 $ {Z^∗}_{2q+1} $ . 假設我們有輸入 $ q $ , $ g $ , $ g^a $ 並想輸出一對 $ (C, Y) $ 這樣 $ Y = C^a $ . 一種方法是選擇一些 $ c \in Z_q $ ， 讓 $ C = g^c $ ， 然後讓 $ Y = (g^a)^c $ . 直覺地說，KEA1 可以被視為說這是產生這樣一對的“唯一”方式。該假設通過說任何輸出這樣一對的對手必須“知道”一個指數來捕捉這一點 $ c $ 這樣 $ g^c = C $ . 形式化要求有一個可以返回的“提取器” $ c $ .
我了解如何找到一對 $ (C, Y) $ 這樣 $ Y = C^a $ 通過選擇任何 $ c \in Z_q $
但是，我對“提取器”在這裡的含義感到困惑。這是否意味著給定對 $ (C, Y) $ 必須找到 $ c $ 這是用來計算 $ C $ ? 如果是，我們如何找到 $ c $ 剛剛給出 $ (C, Y) $ ?
還是有別的意思？
在談到密碼學中的“知識”時，“提取器”的概念很常見。這是因為很難正式定義“知道”某事的含義。因此，我們將其定義為，如果有人可以創建有效的知識證明，我們可以以某種方式“查看”該過程並提取知識。
在這種特定情況下，我們有一個黑盒機器，它接受輸入 $ q, g, g^a $ , 並將輸出 $ (C, Y) $ 這樣 $ Y = C^a $ . 聲稱這個黑匣子必須“知道”指數 $ c $ （在哪裡 $ g^c = C $ ）。從形式上講，這意味著如果我們可以訪問這個黑匣子，我們應該能夠提取 $ c $ 出它（具有不可忽略的機率）。
但是，這只是一個假設（並且是不可證偽的假設），因此它可能會被證明是錯誤的。