機率單向函式是否意味著確定性單向函式？
認為 $ f $ 是機率單向函式。那麼我的問題是，是否存在確定性單向函式的構造 $ g $ 基於 $ f $ ?
還是可能存在機率單向函式但確定性單向函式不存在？
編輯：機率單向函式在此處的定義 2.2.2 中定義。
讓我們看一下連結論文中的定義：
**定義 2.2.2（機率單向函式）。**一個機率函式， $ F $ （帶隨機域 $ R_n $ )，具有相應的確定性驗證器， $ V_F $ , 被稱為關於良好分佈的單向分佈， $ \mathbb{X} $ , 如果對於任何 PPT, $ A $ : $$ \Pr\bigl[x \gets X_n, r \gets R_n, V_F\bigl(A(F(x, r)), F(x, r)\bigr) = 1\bigr] < \mu(n).¹ $$ $ F $ 如果相對於均勻分佈是單向的，則稱為單向。
我會假設，因為你沒有指定任何關於分佈的東西，我們正在研究均勻分佈。
這個定義有點問題，因為它不包含任何對驗證者的正確性保證。特別是，採取任何功能 $ F $ 並定義 $ V_F $ 成為常數 $ 0 $ 功能。根據上面對的定義 $ (F,V_F) $ 是單向的。顯然這不是本意。
定義 2.5.1 定義了有效的可驗證性，儘管這個定義不太適合上面定義的單向函式，因為它討論的是鍵控函式的集合。然而，本著同樣的精神，我將假設定義 2.2.2 意味著需要以下內容 $ F $ :
定義（有效驗證）。一個函式， $ F $ 如果存在確定性多項式時間算法，則滿足有效驗證， $ V_F $ ，這樣： $$ \forall x \in X_n, r \in R_n, V_F(x, F(x, r)) = 1. $$
如果是這種情況，則以下情況成立。
定理讓 $ F : X_n \to Y_n $ 是具有隨機域的機率單向函式 $ R_n $ . 然後是確定性函式 $ G : X_n \times R_n \to Y_n $ 定義為 $ G(x,r)=F(x,r) $ 是確定性的單向函式。
**證明。**讓 $ A $ 表示任意 PPT 算法，使得$$ \Pr[(x,r) \gets X_n\times R_n, G(A(G(x,r))) = G(x,r)] =\epsilon(n). $$ 注意，由於分佈超過 $ X_n $ 是統一的 它認為 $$ \begin{align} \epsilon(n) = &\Pr[(x,r) \gets X_n\times R_n, G(A(G(x,r))) = G(x,r)]\ =&\Pr[x \gets X_n, r\gets R_n, G(A(G(x,r))) = G(x,r)]\ =&\Pr[x \gets X_n, r\gets R_n, F(A(F(x,r))) = F(x,r)] \end{align} $$ 其中最後一個等式遵循以下定義 $ G $ .
現在，考慮 PPT 算法 $ B $ 在輸入 $ y $ , 執行 $ (x’,r’)\gets A(y) $ 和輸出 $ x’ $ . 根據有效可驗證性的定義，對於所有 $ x,x’\in X_n $ , $ r’,r \in R_n $ 它必須認為$$ F(x’,r’) = F(x,r) \implies V_F(x’,F(x,r))=1. $$ 因此， $$ \begin{align} \epsilon(n) = &\Pr[x \gets X_n, r\gets R_n, F(A(F(x,r))) = F(x,r)]\ \leq & \Pr[x \gets X_n, r\gets R_n, V_F(B(F(x,r)),F(x,r))=1] \leq \mu(n), \end{align} $$ 其中最後一個不等式來自以下假設： $ F $ 是機率單向函式。
由於上述適用於任意PPT $ A $ ，定理陳述如下。 $ \quad\quad\Box $
¹在哪裡 $ \mu $ 表示未指定的可忽略函式。