偽隨機函式也是單向函式嗎？

我可以假設嗎？具體來說，我想知道以下兩種情況是否有效。認為 $ prf_k(m)=c $

1. 單向性：僅給定 $ c $ , 我們不能透露 $ m $ .
2. 無鑰匙 $ k $ ，即使給定 $ m $ ， 不能獲取 $ c $ .

They seem intuitive, but I want to be assured of their validity when I say that. Is a pseudorandom function also a one-way function?

(Note the OP’s clarification that even for 1, the adversary does not have the key k.)

Yes. $ : $ The way to show anything like those, is to use the fact that oracle access to prfk

is sufficient to efficiently determine the extent to which an adversary is violating those.

def straight-line_reduction_1_():
m = random_element_of_(domain(F))
query F on m
let c be the output of F on m
send c to inner_adversary_1
forward any queries and responses between inner_adversary_1 and the F oracle
let guess be the output of inner_adversary_1 on c
if guess == m:
 return True
else:
 return False

straight-line_reduction_1_ uses only a small amount of space and makes only one more oracle query than inner_adversary_1, and straight-line_reduction_1_’s runtime is dominated by forwarding queries/responses from/to inner_adversary_1. ​ (So, straight-line_reduction_1_

is efficient.) ​ For all F, the probability of straight-line_reduction_1_ outputting True is equal

to the probability of inner_adversary_1 correctly guessing m given c. ​ However, if F is a

truly random function and inner_adversary_1 makes at most q queries, then the probability

of inner_adversary_1 correctly guessing m given c is at most (q+1)/(cardinality(domain(F))).

(That should be proven, but I’ll only bother doing so if you ask.)

鑑於該結果（我沒有提供證明），然後通過最多 q 次查詢，inner_adversary_1 正確猜測給定 c 的 m 的機率最多為 (q+1)/(基數(domain(F) )) 再加上 inner_adversary_1

與 straight-line_reduction_1_ 的組合將函式族與隨機區分開來的程度。

特別是，如果函式族是偽隨機的，那麼 1 成立。

可以類似地繼續證明，

如果函式族是偽隨機的，那麼 2 也成立。

1. 給定 c 不能揭示 m。

因此，該陳述應該是，給定 $ c $ , 任何多項式類型的對手 $ A $ 可以確定 $ m $ 以不可忽略的機率。

之所以如此，是因為 - 任何人都可以暴力破解 $ m $ 併申請 $ PRF_k(m) $ 並檢查它是否等於 $ c $ . 這在計算上可能是不可能的（並非不可能，因為對手 $ A $ 可以猜測並獲得幸運）。

這裡也有幾點需要注意。考慮到某些問題難以解決（或無法在多項式時間內有效解決）的基本假設，PR 函式可證明是安全的。例如。離散對數問題，2 n 位素數乘積的因式分解，子集問題。（這不是一個具體的證明，因為難以解決只是假設，需要證明 $ N != NP $ 做一個具體的陳述）

還要注意，如果安全參數（大小[Math Processing Error] $ m $ 和[Math Processing Error] $ c $ ) 低，他們的蠻力攻擊是可行的。

只要您有足夠大的安全參數、任何多項式時間對手和可證明安全的 PRF（在困難問題的假設下），您就可以說給定 c，以高機率找不到 m。

2. 沒有[Math Processing Error] $ k $ , 給定[Math Processing Error] $ m $ 一個找不到[Math Processing Error] $ c $

由於它是一個 $ PRF_k $ ，你可以說只有不可忽略的機率，給一個消息 $ m $ , 任何多項式對手 $ A $ 可以猜到 $ c $ .

一個可忽略機率的例子是 O( $ 2^{-n} $ ) 其中 n > 60

這應該足夠正式地說（儘管總是可以添加更多細節）。

引用自：https://crypto.stackexchange.com/questions/29966