离散对数问题（有时也称 Diffie-Hellman 假设）是由 Diffie 和 Hellman 两人于1976年在一篇名为 “New Directions in Cryptography” 论文中提出的。
- 离散对数（Discrete-Logarithm）问题生成：$(\mathbb{G}, q, g) \gets GenDL(1^n)$
- $q$ 为 $n$-bit 的质数，以下所有的计算都基于 $\mathbb{Z}_q$ 即$\mod q$。
- 设 $\mathbb{G}$ 是阶为 $q$ 的循环群（cyclic group），生成元（generator）为 $g$；这意味着对 $\mathbb{G}$ 中任意一个元素 $h$，都存在唯一的一个 $x \in \mathbb{Z}_q$ 使得 $g^x = h$，这时我们说 $x$ 是 $h$ 关于 $g$ 的离散对数。
离散对数问题假设
- 现从群 $\mathbb{G}$ 中均匀随机抽取一个 $h$，并给定 $(\mathbb{G}, q, g, h)$，那么计算 $h$ 关于 $g$ 离散对数是困难的。也就是说虽然离散对数问题的生成条件保证了满足 $g^x = h$ 的 $x$ 一定存在，但很难计算。
Diffie-Hellman 假设与离散对数问题类似，但并不完全相同
- CDH（Computational Diffie-Hellman）：从 $\mathbb{G}$ 中均匀随机抽取两个元素，设为 $g^{x_1}$ 和 $g^{x_2}$，CDH 假设表示仅从 $(\mathbb{G}, q, g, g^{x_1}, g^{x_2})$ 计算 $g^{x_1 \cdot x_2}$ 是困难的，即使这个值是唯一确定的。
- DDH（Decisional Diffie-Hellman）：从 $\mathbb{G}$ 中均匀随机抽取两个元素，设为 $g^x$ 和 $g^y$，第三个元素或者为 $g^{xy}$，或者为另一个从 $\mathbb{G}$ 中均匀随机抽取的元素 $g^z$，区分这两种情况是困难的。