確定函式是否是單向的

我讀了一本關於單向函式的書。在這本書中，我看到了2個我看不懂也不知道如何解決的習題。誰能幫我解決這些問題？

1. 是 $ f(x,y)=x+y $ 單向功能？
2. 是 $ f(x)=x^2 $ 單向功能？

首先讓我們澄清一下單向函式是什麼。通俗地說，單向函式是一種易於計算但難以求逆的函式。

更正式的函式 $ f : {0,1}^* \to {0,1}^* $ 是單向的，如果

1. 存在多項式時間算法 $ M_f $ 計算 $ f $ ，即對所有人 $ x $ , $ M_f(x)=f(x) $ .
2. 對於每個機率多項式時間算法 $ \mathcal{A} $ , 存在一個可忽略的函式 $ \epsilon $ , 這樣 $$ \Pr\big[x\gets {0,1}^n,\ y:= f(x),\ x’\gets\mathcal{A}(1^n,y) : f(x’)=y\big] \leq \epsilon(n). $$

現在你要問的兩個函式是否符合這些定義？

首先，讓我指出，我們不能在不做假設的情況下對這個問題給出肯定的回答。原因是，是否存在單向函式是未知的。提出一個無條件的單向函式將解決著名的懸而未決的問題 $ \mathsf{P}=\mathsf{NP} $ .

另一個問題是，鑑於您提供給我們的資訊，我們並不真正知道函式是在哪個結構上定義的。如果我們假設函式是在整數上定義的，那麼這兩個函式都不是單向的。

兩者都很容易計算，但也很容易反演。

1. 讓我們首先考慮函式 $ f(x,y) = x+y $ . 給定 $ z := x+y $ , 一個算法 $ \mathcal{A} $ 可以簡單地輸出 $ (x’,y’)=(z,0) $ . 這顯然是多項式時間，並且根據正常整數算術 $ z+0 = z $ 因此 $ \mathcal{A} $ 成功的機率 $ 1 $ .

更一般地說，這種攻擊適用於任何具有加性身份的結構，無論是場、環、組，甚至是么半群。 2. 對於函式 $ f(x) = x^2 $ 事情有點不太清楚。在整數上， $ f $ 也很容易反轉。有一些有效的算法可以計算整數上完美平方的平方根。

然而，正如 Ella Rose 所暗示的那樣，這在某些結構上並不為人所知。具體來說，如果我們在整數模上定義函式 $ N $ ， 在哪裡 $ N $ 是一個大半素數，有兩個不同的、等長但未知的素因數，那麼求平方根就相當於分解 $ N $ ，一個被認為很難的問題。事實上，拉賓密碼系統就是基於這個問題的硬度。

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