離散對數中的隨機自約化
我了解 Random Self-reducibility 的含義以及它在離散日誌中的使用方式。不清楚的是
- 它如何表明 DL 在一般情況下很難。
一個不完美的深度學習黑盒的成功機率是 $ p(n) $ （為 $ n $ -位字元串，和 $ p $ 是多項式）。因此，為了獲得正確的 DL 輸入 $ y $ 是 $ 1/p(n) $ .
- 這是否意味著找到單個的 DL $ y $ 可以在多項式時間內完成嗎？（只需執行算法 $ n*poly(n) $ 這仍然是一個多項式！）
之後，教授在一次講座中復述了每次成功的機率是$$ \left(1-\frac{1}{p(n)}\right)^np(n) $$這小於 $ e^{-n} $ .
- 他們是如何得出這個結論的？
- 如果結論是正確的，這是否意味著機器每次成功的機率都可以忽略不計（所以找到每個的 DL 可以忽略不計？）
我了解 Random Self-reducibility 的含義以及它在離散日誌中的使用方式。尚不清楚的是它如何表明 DL 在一般情況下很難。
實際上，隨機自約化並不表明 DL 在任何情況下都很難。它確實表明，如果存在硬 DL 實例，那麼隨機 DL 實例是困難的。
請記住，“隨機自約化”屬性是我們可以採用問題的任意實例 $ g^x = h $ ， 尋找 $ x $ ，並將其變成一個隨機實例 $ r_1^y = r_2 $ ， 尋找 $ y $ ，如果我們能解決隨機實例，我們就可以回去解決我們原來的問題。
它如何表明平均實例是困難的，是通過顯示相反的；如果隨機實例具有非平凡的簡單機率，那麼我們可以解決任何任意實例（通過多次隨機變換我們的任意實例，並且如果我們碰巧遇到一個簡單實例，我們很有可能這樣做，我們得到解決原來的問題）。
所有這些形式主義（這就是讓你絆倒的原因）只是用數學術語表達這個概念（與我使用的口頭描述相反）。
當然，如果您嘗試進行形式主義，那麼正確地使用公式很重要。
一個不完美的深度學習黑盒的成功機率是 $ p(n) $ （為 $ n $ -位字元串，和 $ p $ 是多項式）。因此，為了獲得正確的 DL 輸入 $ y $ 是 $ 1/p(n) $ .
其實機率是 $ 1/p(n) $ ; 請記住，機率限制在範圍內 $ [0,1] $
之後，教授在一次講座中復述了每次成功的機率是
實際上，如果攻擊者試圖這樣做，他並不是每次都成功；他需要做的就是成功一次。一次成功（即隨機減少到允許他解決 DL 問題的實例）將告訴時間他真正感興趣的 DL 問題的答案。
$ \left(1-\frac{1}{p(n)}\right)^np(n) $
這可能是攻擊者需要精確執行的機率 $ n+1 $ 在找到答案之前隨機減少，但如果是這樣，我很確定你把那個公式弄亂了（以及顯然使用 $ n $ 有兩個不同的含義，DL 問題的大小和攻擊者嘗試的隨機減少次數）
**1.**它如何表明 DL 在一般情況下很難。
我們可以通過以下簡化來證明這一點；
假設我們有一個算法 $ A $ 解決了一半輸入的 DL $ y $ . 那是， $ A(y) $ 返回 $ x $ 作為 $ y = g^x $ 僅對一半可能的輸入值 $ y $ .
現在解決一般情況 $ y $ , 隨機選擇 $ r $ 看看 $ A $ 可以找到的DL $ g^rh $ .
很明顯， $ A $ 有 $ 1/2 $ 返回正確值的機會。如果你在多項式時間內嘗試，它可能會至少工作一次 $ r $ .
一旦我們得到 $ A(g^rh)=y $ ，那麼我們可以推斷出 $ h = g^{y-r} $ ，因此這解決了 DLOG $ y $ .
這是從一般情況到一般情況的減少。反之亦然，這意味著深度學習在一般情況下很難。
**2.**這是否意味著找到單個 y 的 DL 可以在多項式時間內完成？
不，這是機率多項式時間。
**3.**他們是如何得出這個結論的？
雨披糾正了你的結果，我會走另一條路。
讓我們重複這個過程 $ 1/p(n) $ -times 然後，在任何輸入上 $ y’ $ , A 將無法反轉 $ y’ $ 在所有這些獨立試驗中，最多
$$ (1-p(n))^{p(n)} \leq e^{-1} \leq \frac{1}{2} $$
因此，經過 $ 1/p(n) $ 的試驗 $ r $ 它會成功反轉一些 $ y’ $ .
**4.**如果結論是正確的，這是否意味著機器每次成功的機率都可以忽略不計（所以找到每個的DL可以忽略不計？）
是的，否則不完美的 DL 黑盒將是多項式時間縮減。