類似於 DLP 的問題
我正在研究一種協議，其安全性基於以下假設：給定 $ g_1, g_2, A, B \in \mathbb{F}_p ^* $ 和 $ g_1, g_2, A \neq 1 $ 和 $ g_1 \neq g_2 $ ，很難找到指數 $ r_1,r_2, d $ st 以下等式成立：
$$ g_1^{r_1}g_2^{r_2} \equiv A^dB \ \ (\mbox{mod} \ p) $$ 我正在閱讀的論文指出“這是一種離散對數問題，因此假設它很難解決”。我不確定為什麼最後一句話是真的：最初我認為我可以通過說“如果我能解決這個問題給定 $ g_1, g_2, A, B $ ，特別是我可以解決它 $ g_2 = A = 1 $ ，所以我可以解決 $ g_1^{r_1}=B $ ，這是一個 DLP”。但我的論點是錯誤的 $ g_2 $ 和 $ A $ 不同於 $ 1 $ 通過假設。我真的很想有一些像我試圖展示的那樣的證據，這樣我就可以把這個問題帶回到 DLP 硬度假設，不要再假設了。如果有人知道similar-discrete-log-problem 或看到任何顯示此問題的方法比DLP 更難，請幫助我！先感謝您
證明這個問題的標準方法至少和 DLP 問題一樣難，就是證明，有了可以解決這個問題的 Oracle，你就可以解決 DLP 問題。
以下是如何做到這一點（我們假設 Oracle 將解決具有非平凡機率的隨機實例）：
鑑於DH問題 $ G^x = H $ ， 尋找 $ x $ ，我們選擇隨機值 $ s_1, s_2, s_3, s_4 $ ，並形成問題：
$$ (G^{s_1})^{r_1} \cdot (G^{s_2})^{r_2} = (G^{s_3})^d \cdot (H^{s_4}) $$ 這是一個隨機實例，因此 Oracle 以非平凡的機率為我們提供了值 $ r_1, r_2, d $ ，所以我們知道：
$$ s_1r_1 + s_2r_2 \equiv s_3d + xs_4 \pmod{p-1} $$ 我們知道除了 $ x $ 在上面的方程中，我們解決它，我們的工作就完成了