密码学中的困难问题详解

密码学中的困难问题详解，许多密码方案的安全性建立在特定数学问题难解的假设上，通常不是已经证明这些问题无条件困难。下文的整数分解、离散对数等问题主要用于经典公钥密码，足够大的容错量子计算机可用 Shor 算法高效求解；格和纠错码等问题则是后量子密码研究的重要基础，不能把这些问题一概视为抗量子难题。以下是密码学中重要的困难问题分类及详解。

一、离散对数类问题

1. 离散对数问题 (Discrete Logarithm Problem, DLP)

描述为：
以有限域为例：选定 中阶为大素数 的循环子群 ，给定 ，求 ，使得 。群和参数必须随实例明确给出。

该问题是 Diffie-Hellman 密钥交换和 ElGamal 加密算法的基础。

2. 椭圆曲线离散对数问题 (Elliptic Curve Discrete Logarithm Problem, ECDLP)

描述为：
在椭圆曲线群 的指定大素数阶子群中，给定生成点 和点 ，求模该子群阶的标量 ，使得 。

ECDLP 是椭圆曲线密码（如 ECDH 和 ECDSA）的核心难题。

二、Diffie-Hellman 类问题

1. 计算性 Diffie-Hellman 问题 (Computational Diffie-Hellman Problem, CDH)

描述为：
在选定的素数阶循环群中，给定 ，其中 均匀随机选取，计算 。有限域实例中的运算按相应模数进行。
CDH 是构造许多密码协议的基础。

2. 决定性 Diffie-Hellman 问题 (Decisional Diffie-Hellman Problem, DDH)

描述为：
在相同群中，区分 与 两种分布，其中 独立均匀随机选取。也可把它理解为判断候选值是否为正确的 Diffie-Hellman 结果。
DDH 通常用于构造安全多方计算和伪随机数生成器。

3. 间隙 Diffie-Hellman 问题 (Gap Diffie-Hellman, Gap-CDH)

即使允许调用一个能够判定 DDH 元组的预言机，仍要求计算给定 CDH 实例的 。这一假设区分了“能判定候选答案是否正确”和“能算出答案”。

文献中 GDH 常用于 Gap Diffie-Hellman；多方乘积指数形式也有不同的广义定义，使用缩写时应给出具体输入、辅助信息和目标，不能混为一谈。

三、双线性映射相关问题

1. 双线性 Diffie-Hellman 问题 (Bilinear Diffie-Hellman Problem, BDH)

以对称双线性对为例， 与 为同一大素数阶的循环群， 可高效计算、满足双线性且非退化。给定 ，计算 。非对称配对需另外明确两个源群及输入分布。

这是基于双线性对的密码算法（如配对加密）的基础。

2. 决定性双线性 Diffie-Hellman 问题 (Decisional Bilinear Diffie-Hellman Problem, DBDH)

在相同对称配对设置下，区分 与均匀随机的 ；公开输入为 和 ，指数均随机选取。

3. 双线性假设的扩展

ABE 等方案还会使用随参数变化的 -型或并行双线性假设。扩展假设必须列出攻击者获得的全部群元素、缺失项、参数范围和目标分布，不能仅凭“BDH 的推广”就认为其定义和安全性已经确定。阅读具体方案时应以该方案的正式假设为准。

四、因子分解类问题

1. 整数分解问题 (Integer Factorization Problem, IFP)

描述为：
给定一个整数 ，其中 和 是大素数，求出 和 。
分解 RSA 模数可以求出私钥，因此整数分解是 RSA 的重要安全基础；一般 RSA 求逆问题与整数分解并未被证明完全等价。

2. 复合模数下的离散对数

若在 $\mathbb{Z}_n^\langle g\rangleghxh\equiv g^x\pmod n\mathbb{Z}_n^$ 本身未必循环。它不能仅因模数复合就被称作整数分解问题，也不能据此声称两者等价。

五、格密码相关问题

1. 最短向量问题 (Shortest Vector Problem, SVP)

描述为：
在格 中，找到长度最短的非零向量 ，使得 。
格密码通常涉及 SVP、GapSVP、SIVP 或其近似版本等问题。具体安全归约依赖参数与变体；不能把 NTRU、LWE 与精确 SVP 直接视为同一个问题。

2. 最近向量问题 (Closest Vector Problem, CVP)

描述为：
在格 中，给定任意点 ，找到格中距离 最近的点。

3. 学习带误差问题 (Learning with Errors, LWE)

描述为：
给定模数 ，均匀随机矩阵 与 ，其中秘密 ，误差向量 按指定的小误差分布采样。搜索型 LWE 要求恢复 ；判定型 LWE 要求将 与均匀随机分布区分。

模数、维数、样本数量、秘密及误差分布共同决定实例，不能省略模运算，也不能把无噪声线性方程组当作 LWE。特定参数下的 LWE 有到最坏情形近似格问题的安全归约。

六、后量子密码相关问题

1. 一般线性码译码与综合译码

给定二元线性码的生成矩阵 和 ，其中加法在 上进行、 是重量受限的未知错误向量，目标是恢复消息 或错误 。若没有错误项，满行秩 下可通过线性代数恢复消息，不能构成这里的译码难题。

对应的综合译码形式为：给定校验矩阵 、综合 和重量约束 ，寻找满足 且 的错误向量。McEliece、Niederreiter 使用带隐藏结构、可高效译码的码；其具体安全性还涉及公开码结构是否可被区分和恢复。

2. 同源性问题 (Isogeny Problem)

描述为：
在椭圆曲线同源图中，找到从曲线 到 的同源映射。
这类问题需进一步指定曲线族、同源度数和辅助信息。不同同源方案并不共享一个统一安全结论，不能由“寻找同源困难”直接推出某个具体方案安全。

七、困难问题间的关系

许多困难问题之间具有复杂的数学关系：

1. 在相同群和相容的输入分布下，能求解 DLP 就能计算 CDH；能计算 CDH 就能判定 DDH。反方向一般不能直接推出，因此 DDH 难假设通常比 CDH 难假设更强。
2. ECDLP 是 DLP 在椭圆曲线群中的实例。合适曲线在相同经典安全强度下通常使用更短的密钥，并不意味着任意椭圆曲线参数都更安全。
3. LWE 与近似 GapSVP/SIVP 等格问题存在带条件的安全归约，应明确参数、近似因子及归约是否使用量子计算。
4. IFP 与有限域/椭圆曲线 DLP 是不同问题；它们都可被足够大规模的容错量子计算机利用 Shor 算法求解。

参考资料

• Regev：The Learning with Errors Problem
• Classic McEliece：设计依据
• Boneh：The Decision Diffie-Hellman Problem