计算困难假设（Computational hardness assumption）

以下内容翻译自：维基

介绍

在计算复杂性理论中，计算困难假设是一个特定问题无法得到有效解决的假设（有效通常指“在多项式时间内”）。目前还不知道如何证明其困难性。同时，我们可以将一个困难问题规约到（reductions）一个比较容易理解的问题上。

多项式时间
常见的时间复杂度从小到大：

\[O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!) \]

只要算法的复杂度不会是最后两个指数或者阶乘型，前面的\(O(1)\)到\(O(n^m)\)（\(m\)为常数）任意组合都算是多项式级的复杂度，它们的规模\(n\)都出现在底数位置；而\(O(2^n)，O(n!)\)型 复杂度，就是非多项式级的，问题规模较大时，计算机也很难算出结果。所以我们一般会选择多项式级复杂度的算法。

在密码学中，计算困难假设是非常重要的。可以这么说，"只要给出一个困难问题，就能构造一个公钥加密方案"。通常一个加密方案，需要具有信息论上的安全（information theoretic security），也就是满足一次一密（one-time pad），然而信息论上的安全一般是难以实现的。在这种情况下，我们一般会回到计算安全上（computational security），粗略的说，就是假设敌手的计算都是有限的，那么系统就是安全的。

常见困难问题 整数难分解问题（Integer factorization）

简单来说，就是对于一个复合数\(n\)，是两个大素数的乘积，即\(n=p*q\)。给定\(n\)，难以在多项式时间内求出其素因子\(p\)和\(q\)。更一般来说，是给出\(n=\prod_{i}p_i\)，难以找到这些素数\(p_1,...,p_k\)。

RSA问题

给出复合数\(n\),\(e,c=m^e(mod n)\)，难以找到\(m\)。所以在RSA密码中，\((n,e)\)作为公钥，\(m\)作为私钥。
更详细的RSA参考：RSA

剩余问题（Residuosity problems）

给出符合数\(n\)，\(y,d\)，找到\(x\)是困难的，对于\(x^d=y(mod n)\)。

特殊情况：二次剩余问题（Quadratic residuosity problem）、决策复合剩余问题（Decisional composite residuosity problem）

下面给出基于剩余问题的密码方案：

• Goldwasser–Micali cryptosystem (quadratic redisduosity problem)
• Blum Blum Shub generator (quadratic redisduosity problem)
• Paillier cryptosystem (decisional composite residuosity problem)
  更多Paillier请参考：Paillier
• Benaloh cryptosystem (higher residuosity problem)
• Naccache–Stern cryptosystem (higher residuosity problem)

隐藏假设（Phi-hiding assumption）

对于复合数\(m\)，难以计算出\(\phi(m)\)，即欧拉函数。

离散对数问题（Discrete log problem (DLP)）

给出乘法群\(G\)中的两个元素\(a,b\)，难以找到一个整数\(k\)，使其满足\(a=b^k\)。
离散对数问题和整数分解问题不同，但是其计算复杂度接近。

大多数的密码协议都基于更具体的DH假设。

DH假设（Diffie–Hellman assumption）

给出群中元素\(g,g^a,g^b\)，其中\(g\)是群\(G\)的生成元，\(a,b\)是随机整数，难以找到\(g^{a,b}\)。

例如：
在原始的DH密钥交换协议（Diffie–Hellman key exchange）中使用。详细见：DH-密钥交换协议
ElGamal算法基于的是Decisional Diffie–Hellman (DDH)问题的变体。了解更多ElGamal参考：ElGamal

多线性映射（Multilinear maps）

对于一个多线性映射函数\(e：G_1,...G_n\to G_T\)，其中\(G_1,..,G_n,G_T\)都是群，例如有任意的\(g_1,...,g_n\in G_1,...,G_n\)和\(a_1,...,a_n\)，则有\(e(g_1^{a_1},...,g_n^{a_n})=e(g_1,...,g_n)^{a_1...a_n}\)。

在设计密码方案时，我们需要构造一个群\(G_1,...G_n,G_T\)和一个映射函数\(e\)，使得在群上可以方便计算，而在\(G_1,...G_n\)上的离散对数是困难的。

当\(n=2\)时，就是双线性映射（bilinear maps），使用Weil pairing和Tate pairing构造的。

下面给出基于多线性映射的例子：

• Boneh-Franklin scheme (blinear Diffie-Hellman)
• Boneh–Lynn–Shacham (blinear Diffie-Hellman)

格上问题（Lattice problems）

更多请参考：格基础
对于量子计算机来说，可以破解整数分解问题和离散对数问题，但对格上的问题是安全的，所以使得一些基于格上的密码成为后量子力密码。

下面给出一些基于格上的密码方案：

• NTRU (加密和签名)
• 全同态加密，fully homomorphic encryption

最短向量问题，Shortest vector problem (SVP)）

一些变体：

• Shortest independent vectors problem (SIVP)
• GapSVP
• Unique-SVP

最近向量问题 ，Closest vector problem (CVP) LWE问题，Learning with errors

LWE问题可以规约到GapSVP问题。