PRF 區分器可以呼叫函式的算法嗎？
函式的定義 $ F:\ {0,1}^n\times{0,1}^n\to{0,1}^n $ 作為一個偽隨機函式族 (PRF) 是它可以通過 PPT 算法實現 $ \mathcal F $ ，並且沒有PPT算法 $ \mathcal A $ 能夠分辨 $ x\mapsto F(k,x) $ 來自未知隨機的隨機函式 $ k $ 和非消失機率。
是算法 $ \mathcal A $ 允許呼叫算法 $ \mathcal F $ 實施 $ (k,x)\mapsto F(k,x) $ ? 或者更一般地說，它的一部分？
這似乎有必要決定以下是否 $ G $ 是否是 PRF。
- 讓 $ H:\ {0,1}^n\times{0,1}^n\to{0,1}^n $ 成為PRF。
- 讓 $ P_c:\ {0,1}^n\to{0,1}^n $ 是一個鍵固定為任意常數的 PRP $ c $ ， 既 $ P $ 和 $ {P_c}^{-1} $ 可通過 PPT 算法計算。
- 定義 $ G:\ {0,1}^n\times{0,1}^n\to{0,1}^n $ by （根據大端約定將位串同化為整數） $$ G(k,x)\underset{\text{def}}=\begin{cases} {P_c}(k\bmod2^{\lfloor n/2\rfloor})&\text{if }x=0^n\ 1^n&\text{if }x=1^n\text{ and }P_c^{-1}(k)<2^{\lfloor n/2\rfloor}\ H(k,x)&\text{otherwise} \end{cases} $$
本質上， $ G $ 是 PRF $ H $ , 除了它有一組弱鍵 $ k $ 大小的 $ 2^{\lfloor n/2\rfloor} $ , 這樣不管 $ k $ , $ G(k,0^n) $ 是弱鍵；什麼時候 $ k $ 是弱鍵， $ G(k,1^n) $ 是 $ 1^n $ .
我們可以為 $ G $ 那
- 送出 $ x=0^n $ , 得到 $ y $
- 將算法應用於 $ G $ 輸入 $ (y,1^n) $
- 測試結果是否為 $ 1^n $ ，對於 $ G $ ，並且只有隨機函式的消失機率。
但是，如果我們既不能將算法應用於 $ G $ , 也不分析提取 $ c $ .
動機是這個問題，它詢問是否 $ F_2(k,x)\underset{\text{def}}=F(F(k,0^n),x) $ 是一個 PRF，假設 $ F $ 是一個PRF。如果以上 $ G $ 是PRF， $ F=G $ 將是一個反例。
對手 $ \mathcal{A} $ 允許呼叫算法 $ \mathcal{F} $ （如果是 PPT）在我知道的任何 PRF 定義中。
我們通常對針對每一種可能的 PPT 算法的安全性感興趣 $ \mathcal{A} $ 並要求對於每個這樣的算法 $ \mathcal{A} $ 它認為 $ \mathcal{A} $ 只能與機率不可忽略的隨機函式區分開來。
如果 $ \mathcal{F} $ 是一個PPT算法，存在一個對手 $ \mathcal{A} $ 其中包括 $ \mathcal{F} $ 功能。這個對手能夠呼叫 $ \mathcal{F} $ 並且我們要求我們的 PRF 對那個對手也是安全的。相同的論點適用於算法的某些部分 $ \mathcal{F} $ .
據我了解，對於您的範例，重要的問題如下：
對手是否 $ \mathcal{A} $ 知道 $ c $ ?
同樣，我們需要與 PRF 中的所有對手不可區分，這意味著我們需要不可區分，即使是對知道這個固定的對手 $ c $ .