陷門函數

在理論電腦科學和密碼學中，陷門函數是一種在一個方向上很容易計算，但在沒有特殊資訊的情況下很難在相反方向上計算（尋找它的逆）的函數，稱為「陷門」。陷門函數是單向函數的一種特殊情況，廣泛用於公鑰密碼學中。 ^[2]

用數學術語來說，如果f是陷門函數，則存在一些秘密資訊t ，因此給定f ( x ) 和t ，很容易計算x 。考慮一把掛鎖和它的鑰匙。通過推動卸扣，無需使用鑰匙即可將掛鎖鎖上。然而，想要輕鬆地開鎖，則必需使用鑰匙。這裡的鑰匙是陷門，而掛鎖則是陷門函數。

一個簡單的數學上的陷門範例是：「6895601 是兩個質數的乘積。那兩個質數是多少？」一個典型的「蠻力」解決方案是嘗試將 6895601 不停除以一些質數，直到找到答案。但是如果已知 1931 是其中一個數字，你可以通過在任何計算機中輸入「6895601 ÷ 1931」來找到答案。這個例子不是一個可靠的陷門函數——現代電腦可以在一秒鐘內猜出所有可能的答案——但是這個例子可以通過使用兩個更大的質數的乘積來改進。

隨著Diffie 、Hellman和Merkle在 1970 年代中期發表了非對稱（或公鑰）加密技術後，陷門函數開始在密碼學中嶄露頭角。事實上，Diffie & Hellman (1976)創造了這個術語。已經提出了幾個函數類，很快就發現陷門函數比最初想像的更難找到。例如，早期的建議是使用基於子集和問題的方案，但事實很快證明這是不合適的。

截至2004年^[update]，已知最好的陷門函數 (族) 候選函數是RSA和Rabin函數族。兩者都是一個合數的冪取模，而且都跟質因數分解有關。

與離散對數問題的難度相關的函數（模質數或在橢圓曲線上定義的群）不是已知的陷門函數，因為沒有關於這個群的已知「陷門」資訊可以實現高效地計算離散對數。

密碼學中的陷門具有上述非常具體的含義，不要與後門混淆（它們經常互換使用，這是不正確的）。後門是一種故意添加到密碼演算法（例如，金鑰對生成演算法、數位簽章演算法等）或作業系統中的機制，例如，它允許一個或多個未授權方以某種方式繞過或破壞系統。

定義

陷門函數是單向函數的集合 { f_k : D_k → R_k } ( k ∈ K )，其中K, D_k, R_k都是二進制字串 {0, 1}^*的子集，滿足以下條件：

存在機率多項式時間 (PPT)採樣演算法 Gen st Gen(1ⁿ ) = (k, t_k) 其中k ∈ K ∩ {0, 1}ⁿ並且t _k ∈ {0, 1}^*滿足 | t_k | < p(n)，其中p是某個多項式。每個t_k稱為對應於k的陷門。每個陷門都可以被有效地採樣。
給定輸入k ，也存在輸出x ∈ D_k的 PPT 演算法。也就是說，每個D_k都可以被有效地採樣。
對於任何k ∈ K ，都存在正確計算f_k的 PPT 演算法。
對於任意k ∈ K ，都存在一個 PPT 演算法A 滿足對於任意x ∈ D _k，令y = A(k, f_k (x), t_k)，那麼我們有f_k(y) = f_k(x)。也就是說，給定陷門，很容易反轉。
對於任何k ∈ K ，沒有陷門t_k ，對於任何 PPT 演算法，能夠正確反轉f_k的機率（即給定f_k(x)的情況下，找到一個x'使得f_k(x') = f_k(x)) 可以忽略不計。 ^[3] ^[4] ^[5]

如果上述集合中的每個函數都是單向排列，則該集合也稱為陷門排列。 ^[6]

例子

在下面的兩個例子中，我們假設分解一個大的合數是很困難的（參見整數分解）。

RSA 假設

在此範例中，具有e模 φ(n) 的逆，即n的歐拉總函數，是陷門：

f(x)=x^{e}\mod n

如果分解已知，可以計算出 $\phi (n)$ ，那麼 $e$ 的逆 $d$ 可以通過 $d=e^{-1}\mod {\phi (n)}$ 計算得出，然後給定 $y=f(x)$ ，我們可以找到 $x=y^{d}\mod n=x^{ed}\mod n=x\mod n$ 。它的困難程度遵循 RSA 中的假設。 ^[7]

拉賓的二次剩餘假設

設 $n$ 是一個大的合數，使得 $n=pq$ ，其中 $p$ 和 $q$ 是大質數，滿足 $p\equiv 3{\pmod {4}},q\equiv 3{\pmod {4}}$ ，並且對攻擊者保密。問題是在給定 $a$ 的情況下計算 $z$ 使得 $a\equiv z^{2}{\pmod {n}}$ 。這裡的陷門是 $n$ 的因式分解。使用陷門， $z$ 的解可以給出為 $cx+dy,cx-dy,-cx+dy,-cx-dy$ ，其中 $a\equiv x^{2}{\pmod {p}},a\equiv y^{2}{\pmod {q}},c\equiv 1{\pmod {p}},c\equiv 0{\pmod {q}},d\equiv 0{\pmod {p}},d\equiv 1{\pmod {q}}$ 。有關詳細資訊，請參閱中國剩餘定理。請注意，給定質數 $p$ 和 $q$ ，我們可以找到 $x\equiv a^{\frac {p+1}{4}}{\pmod {p}}$ 和 $y\equiv a^{\frac {q+1}{4}}{\pmod {q}}$ 。這裡的條件 $p\equiv 3{\pmod {4}},q\equiv 3{\pmod {4}}$ 保證了解 $x$ 和 $y$ 可以很好地定義。 ^[8]

參見

筆記

參考

Diffie, W.; Hellman, M., New directions in cryptography (PDF), IEEE Transactions on Information Theory, 1976, 22 (6): 644–654 [2022-03-21], CiteSeerX 10.1.1.37.9720  , doi:10.1109/TIT.1976.1055638, （原始內容存檔 (PDF)於2017-12-03）
Pass, Rafael, A Course in Cryptography (PDF), [27 November 2015], （原始內容 (PDF)存檔於2022-05-23）
Goldwasser, Shafi, Lecture Notes on Cryptography (PDF), [25 November 2015], （原始內容 (PDF)存檔於2022-04-20）
Ostrovsky, Rafail, Foundations of Cryptography (PDF), [27 November 2015], （原始內容 (PDF)存檔於2022-02-16）
Dodis, Yevgeniy, Introduction to Cryptography Lecture Notes (Fall 2008), [17 December 2015], （原始內容存檔於2017-11-05）
Lindell, Yehuda, Foundations of Cryptography (PDF), [17 December 2015], （原始內容 (PDF)存檔於2022-01-19）

^ Ostrovsky, pp. 6-9
^ Bellare, M. Many-to-one Trapdoor Functions and their Relation to Public-key Cryptosystems. Advances in Cryptology. June 1998.
^ Pass's Notes, def. 56.1
^ Goldwasser's lecture notes, def. 2.16
^ Ostrovsky, pp. 6-10, def. 11
^ Pass's notes, def 56.1; Dodis's def 7, lecture 1.
^ Goldwasser's lecture notes, 2.3.2; Lindell's notes, pp. 17, Ex. 1.
^ Goldwasser's lecture notes, 2.3.4

[1] Ostrovsky, pp. 6-9

[2] Bellare, M. Many-to-one Trapdoor Functions and their Relation to Public-key Cryptosystems. Advances in Cryptology. June 1998.

[3] Pass's Notes, def. 56.1

[4] Goldwasser's lecture notes, def. 2.16

[5] Ostrovsky, pp. 6-10, def. 11

[6] Pass's notes, def 56.1; Dodis's def 7, lecture 1.

[7] Goldwasser's lecture notes, 2.3.2; Lindell's notes, pp. 17, Ex. 1.

[8] Goldwasser's lecture notes, 2.3.4

[2]

[1]

[3]

[4]

[5]

[6]

[7]

[8]