陷门函数

在理论计算机科学和密码学中，陷门函数是一种在一个方向上很容易计算，但在没有特殊信息的情况下很难在相反方向上计算（寻找它的逆）的函数，称为“陷门”。陷门函数是单向函数的一种特殊情况，广泛用于公钥密码学中。 ^[2]

陷门函数的思想是：带有陷门t的陷门函数f可以通过算法Gen生成。f可以有效地在概率多项式时间内被计算。然而，f反方向的计算通常很困难，除非陷门t 是已知的。 ^[1]

用数学术语来说，如果f是陷门函数，则存在一些秘密信息t ，因此给定f ( x ) 和t ，很容易计算x 。考虑一把挂锁和它的钥匙。通过推动卸扣，无需使用钥匙即可将挂锁锁上。然而，想要轻松地开锁，则必需使用钥匙。这里的钥匙是陷门，而挂锁则是陷门函数。

一个简单的数学上的陷门示例是：“6895601 是两个素数的乘积。那两个素数是多少？”一个典型的“蛮力”解决方案是尝试将 6895601 不停除以一些素数，直到找到答案。但是如果已知 1931 是其中一个数字，你可以通过在任何计算器中输入“6895601 ÷ 1931”来找到答案。这个例子不是一个可靠的陷门函数——现代计算机可以在一秒钟内猜出所有可能的答案——但是这个例子可以通过使用两个更大的素数的乘积来改进。

随着Diffie 、Hellman和Merkle在 1970 年代中期发表了非对称（或公钥）加密技术后，陷门函数开始在密码学中崭露头角。事实上，Diffie & Hellman (1976)创造了这个术语。已经提出了几个函数类，很快就发现陷门函数比最初想象的更难找到。例如，早期的建议是使用基于子集和问题的方案，但事实很快证明这是不合适的。

截至2004年 (2004-Missing required parameter 1=month!)^[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的欧拉总函数，是陷门：

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

如果分解已知，可以计算出${\displaystyle \phi (n)}$，那么${\displaystyle e}$的逆${\displaystyle d}$可以通过${\displaystyle d=e^{-1}\mod {\phi (n)}}$计算得出，然后给定${\displaystyle y=f(x)}$，我们可以找到${\displaystyle x=y^{d}\mod n=x^{ed}\mod n=x\mod n}$。它的困难程度遵循 RSA 中的假设。 ^[7]

拉宾的二次剩余假设

设${\displaystyle n}$是一个大的合数，使得${\displaystyle n=pq}$，其中${\displaystyle p}$和${\displaystyle q}$是大素数，满足${\displaystyle p\equiv 3{\pmod {4}},q\equiv 3{\pmod {4}}}$，并且对攻击者保密。问题是在给定${\displaystyle a}$的情况下计算${\displaystyle z}$使得${\displaystyle a\equiv z^{2}{\pmod {n}}}$。这里的陷门是${\displaystyle n}$的因式分解。使用陷门，${\displaystyle z}$的解可以给出为${\displaystyle cx+dy,cx-dy,-cx+dy,-cx-dy}$， 其中${\displaystyle 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}}}$。有关详细信息，请参阅中国剩余定理。请注意，给定素数${\displaystyle p}$和${\displaystyle q}$ ，我们可以找到${\displaystyle x\equiv a^{\frac {p+1}{4}}{\pmod {p}}}$和${\displaystyle y\equiv a^{\frac {q+1}{4}}{\pmod {q}}}$。这里的条件${\displaystyle p\equiv 3{\pmod {4}},q\equiv 3{\pmod {4}}}$保证了解${\displaystyle x}$和${\displaystyle y}$可以很好地定义。 ^[8]

参見

• 单向函数
• 椭圆曲线密码学
• RSA加密演算法

笔记

参考

• 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）

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