Randomness
次指數硬OWF,PRF和iO
我目前正在閱讀 Canetti Lin Tessaro 和 Vaikuntanathan 2015 年的作品“機率電路和應用的混淆”。它說亞指數硬 OWF 意味著亞指數硬 PRF（可穿刺 PRF），後來再次證明亞指數硬 PRF（可穿刺 PRF） ) + 次指數難 iO $ \implies $ pIO（機率電路）。
我真的很困惑作者所說的“次指數困難”一詞的含義，當涉及到 OWF 或 iO 時，它是天氣還是更強的假設。
提前致謝
一個高效的可計算函式 $ f:{0,1}^\rightarrow{0,1}^ $ 據說是 $ (s,\epsilon) $ -one-way if 對於每個對手 $ \mathsf{A} $ 大小* 至多 $ s=s(|x|) $ 機率 $ \Pr\left[{\mathsf{A}(f(x))\in f^{-1}(x)}\right] $ 最多是 $ \epsilon=\epsilon(|x|) $ ，其中機率在域上的均勻分佈和隨機硬幣 $ \mathsf{A} $ .
標準的單向假設是 $ s=poly(|x|) $ 和 $ \epsilon=negl(|x|) $ . 如果對於固定常數，單向函式是次指數困難的 $ 0<c<1 $ ， 這是 $ (2^{{|x|}^c},2^{-{|x|}^c}) $ -單程。請注意，後者意味著前者，因此是一個更強的假設。
類似的定義也適用於其他原語。
*這裡，大小指的是執行時間，如果 $ \mathsf{A} $ 是機率圖靈機，或電路大小以防萬一 $ \mathsf{A} $ 是一個電路。