陷门函数

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

理论电脑科学密码学中,陷门函数一种在一个方向上很容易计算,但在没有特殊信息的情况下很难在相反方向上计算(寻找它的)的函数,称为“陷门”。陷门函数是单向函数的一种特殊情况,广泛用于公钥密码学中。 [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