陷門函數

有一个陷门的一类特殊单向函数,只有一个方向较容易计算

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

陷門函數的思想是:帶有陷門t的陷門函數f可以通過演算法Gen生成。f可以有效地在機率多項式時間內被計算。然而,f反方向的計算通常很困難,除非陷門t 是已知的。 [1]

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

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

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

截至2004年 (2004-Missing required parameter 1=month!),已知最好的陷門函數 (族) 候選函數是RSARabin函數族。兩者都是一個合數的冪取模,而且都跟質因數分解有關。

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

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

定義

陷門函數單向函數的集合 { fk : DkRk } ( kK ),其中K, Dk, Rk都是二進制字串 {0, 1}*的子集,滿足以下條件:

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

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

例子

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

RSA 假設

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

 

如果分解已知,可以計算出 ,那麼 的逆 可以通過 計算得出,然後給定 ,我們可以找到 。它的困難程度遵循 RSA 中的假設。 [7]

拉賓的二次剩餘假設

 是一個大的合數,使得 ,其中  是大質數,滿足 ,並且對攻擊者保密。問題是在給定 的情況下計算 使得 。這裡的陷門是 的因式分解。使用陷門, 的解可以給出為 , 其中 。有關詳細資訊,請參閱中國剩餘定理。請注意,給定質數   ,我們可以找到  。這裡的條件 保證了解  可以很好地定義。 [8]

參見

筆記

參考

  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