證明：如果存在強 OWF，則存在不強的弱 OWF
請幫助我理解以下索賠的證明：
假設存在強OWF，則存在弱函式 $ \frac{2}{3} $ - 單向函式，但不是強大的單向函式
證明
讓 $ f $ 做一個強大的OWF。定義 $ g(x) = \begin{cases} (1, f(x)) & x_1 = 1 \ 0 & else \end{cases} $
我只是不明白如果 $ x_1 $ 這裡是 x 的第一位嗎？如果是這樣，可能性在哪裡 $ \leq \frac{2}{3} $ 從？
資料來源： “密碼學基礎 (0368-4162-01)，第 1 課：單向函式，Iftach Haitner，特拉維夫大學，2011 年 11 月 1-8 日”
兩件事情：
- 是的， $ x_1 $ 是第一位。這個想法是，如果 $ x_1 = 0 $ （發生機率為 1/2），很容易找到 $ g(x) = 0 $ — 任何字元串 $ x’ $ 和 $ x’_1 = 0 $ 就足夠了。這表明 $ g $ 不能是 $ \alpha $ -OWF 適用於任何 $ \alpha <1/2 $ . 為了表明它是一個 $ \alpha $ -OWF 為 $ \alpha \leq 2/3 $ ，您需要降低到強大的 OWF 安全性 $ f $ ，我將留給你做。
- 的選擇 $ 2/3 $ 只是“合適的常數”的社會慣例。有許多複雜度類 $ \mathcal{C} $ 這取決於一些參數 $ \alpha $ （我將表示 $ \mathcal{C}(\alpha) $ ) 在這裡您可以顯示表單的一些結果
對於任何 $ \alpha $ 遠離* $ 1/2 $ 和 $ 1 $ , 複雜度類 $ \mathcal{C}(\alpha) $ 是等價的。
這裡，“有界”的意思是 $ \frac{1}{2}+\frac{1}{n^c} \leq \alpha \leq 1 - \frac{1}{n^d} $ 對於常數 $ c, d $ - - 尤其是， $ \alpha $ 不能忽略地接近（作為輸入大小的函式）到 1/2 或 1。對於這樣的類，選擇的社會約定 $ \mathcal{C}(2/3) $ 因為將事物聯繫起來的“標準”範例很常見。
上述現像有很多例子，例如大多數隨機複雜性類別，但也許 $ BPP $ 尤其是最著名的例子。的重要性 $ \alpha $ 通過類之間的差異可以看出遠離 1/2 和 1 $ BPP $ （有這個限制）和類 $ PP $ （它沒有，而且更強大）。
無論如何，連結註釋的這一部分本質上表明單向函式是類似於類似的類 $ BPP $ （就它們對參數的依賴而言 $ \alpha $ ).