使用 DLOG lsb 的機率算法求解 DLOG
當給定一個給出 DLOG 的 LSB 的預言機時，那裡的答案給出了一個簡單的算法來解決離散對數問題。答案暗示這可能是可能的，但使用機率解決方案並不容易。所以我很自然地想跟進更難的問題。
我可以想到兩個這樣的機率設置（這實際上可能是兩個不同的問題，但我認為在這裡問兩個問題是合理的）：
- 給定一個算法/Oracle，它以不可忽略的機率 p 找到 LSB，並以機率 (1-p) 返回失敗。
- 給定一個算法/Oracle，它總是返回一些機率 p>0.5 是 LSB
在我看來，如果沒有對此獨立性的一些假設，兩者都不足夠，如果算法實際上僅在某些類型的輸入上始終成功，則可能很難利用通用解決方案，但我可能會離開這裡。
真的，因為我的問題是好奇心驅動而不是出於特定需求，所以它相當廣泛：找到 DLOG 的 LSB 的哪種類型的機率解決方案將導致解決 DLOG 問題。
我認為只要機率與離散對數的高位獨立/不相關，一切都應該是可能的。
考慮一個類型 1 算法預言機，其中成功的機率大約是百萬分之一。給定一個離散對數問題 $ y=g^x $ （給定 $ y $ 尋找 $ 0\le x<\ell $ ) 我們可以假設，比如說，底部的 4 位 $ x $ 通過重複 16 次。這將使我們的問題等同於解決 $ y’=g^{[x/16]} $ 和位 $ [x/16] $ 是位 $ x $ 向下移動 4。像往常一樣，我們按位恢復離散對數並移位。恢復低位 $ [x/16] $ 我們隨機選擇幾百萬 $ r $ 在範圍內 $ [0,\ell-\ell/16] $ 並執行我們的算法 $ y’g^r $ （具有離散對數 $ 0\le [x/16]+r<\ell $ . 我們希望至少成功一次 $ [x/16] $ 將是我們的算法 XOR 返回的位與最低有效位 $ r $ . 沖洗; 重複。
同樣，對於機率為 0.501 的類型 2 算法，我們構造相同的 $ y’ $ 再次採樣，比如 1 億個 $ r $ . 我們得到了 1 億個關於最低有效位的預測 $ [x/16] $ 其中大約 50,100,000 個是正確的，大約 49,900,000 個是不正確的，得到比正確預測更多的錯誤預測的機會非常小。沖洗; 重複。
在這兩種情況下，推定算法的輸入都是從大量元素（覆蓋我們組的大部分）中統一選擇的，這些元素的離散對數位於特定區間內。除非我們的算法的能力集中在這些集合之外的元素上，否則我們應該能夠恢復完整的離散對數。