Discrete-Logarithm
關於隨機基數的離散對數
假設 DL 很難 $ G=\langle g \rangle $ . 對於均勻隨機群元素 $ r \in G $ （認為 $ r=g^a $ ), 是不是很難找 $ s $ 給定 $ r^s $ 和 $ r $ ? 計算假設是否有一個公認的名稱？
我至少可以像 DDH 一樣難，因為如果 $ \mathcal{A} $ 可以找到 $ x $ 給定 $ g^y $ 和 $ g^{xy} $ , 她能分辨 $ (g^x,g^y,g^{xy}) $ 從 $ (g^x,g^y,z) $ 在哪裡 $ z $ 是一個隨機群元素。
你在問難不難找 $ s $ 給定 $ r^s $ ，但你沒有提到如果 $ r $ 也給出了。
如果 $ r $ 沒有給出，那麼問題是：給定一些值 $ y $ 尋找 $ r $ 和 $ s $ 這樣 $ r^s=y $ . 這是一個簡單的問題 - 只是輸出 $ r=y $ 和 $ s=1 $ .
如果 $ r $ 是給定的，那麼問題是：給定 $ (r,y) $ 尋找 $ s $ 這樣 $ r^s=y $ ， 在哪裡 $ r,s $ 是隨機選擇的。這是離散對數問題的一種形式，其中基數是隨機的。這使得它“更難”，因為對手無法進行預處理。我不知道它是否有比這更確定的東西。