機率多項式時間算法和單向函式

我一直在閱讀機率多項式時間算法和單向函式，我希望能獲得有關該主題的一些指導。

我正在閱讀的一本教科書說明了單向函式的條件之一：

**難以反演：**對於每個機率多項式時間反演算法 A，存在一個可忽略的函式 negl 使得

$$ Pr[A(f(x))\in f^{-1}(f(x))] \leq negl(n) $$ 其中機率被接管 x 的統一選擇 $ {0,1}^n $ 和 A 的隨機拋硬幣。 “A 的隨機拋硬幣”到底是什麼意思？是不是說“反演函式”是由這樣一個過程隨機生成的？

機率算法使用隨機數來定義它應該執行的下一步（Google例如“蒙地卡羅算法”）。

“隨機拋硬幣”只是說隨機數是均勻分佈的。

算法 A 將僅在內部使用隨機數，它不會輸出任何隨機數。但是 A 的輸出將取決於這些隨機數。

因此，它只會以一定的機率輸出正確的原像。

（對於該定義，還需要 $ \hspace{.04 in}f\hspace{.02 in} $ 的輸出不會比 $ \hspace{.04 in}f\hspace{.02 in} $ 的輸入。）

它的意思是“A生成的隨機位”。 $ : $ 例如，A 可能是

flip 7 coins
if exactly 5 of those come up heads:
   output 011101
else:
   output 100010

.

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