离散对数问题

Discrete Logarithm Problem.

Fix a cyclic group $\mathbb{G}$ of order $q$ , and generator $g\in\mathbb{G}$ . We know that $\{g^0,g^1,...,g^{q-1}\}=\mathbb{G}$ .

Equilently, for every $h\in\mathbb{G}$ , there is a unique $x\in \mathbb{Z}_q$ , such that $g^x=h$ . We define $\log_g{h}$ to be this $x$ . This is the discrete logarithm of $h$ with respect to $g$ in the group $\mathbb{G}$ .

Discrete Logarithm problem in $\mathbb{G}$ : Given $g\in \mathbb{G}$ and uniform $h\in \mathbb{G}$ , compute $\log_g{h}$ .

Discrete-Logarithm Experiment

Similarly, we have the discrete-logarithm experiment $\mathtt{DLog}_{\mathscr{A}, \mathscr{G}} (n)$ where $\mathscr{G}$ is an efficient group-generation algorithm that, on input $1^n$ , outputs a cyclic group $\mathbb{G}$ , its order $q$ , and a generator $g$ .

Adversary $\mathscr{A}$ with $\mathbb{G},q,g$ and a uniform $h\in\mathbb{G}$ needs to efficiently compute correponding $x$ .

Definition. RSA problem is hard relative to $\mathscr{G}$ if for all probabilistic polynomial time algorithm $\mathscr{A}$ , there exists a negligible $\varepsilon(n)$ that $\Pr[\mathtt{DLog}_{\mathscr{A}, \mathscr{G}}(n)=1]\leq \varepsilon(n)$ .

The Discrete Logarithm Assumption is the assumption that there exists a group-generation algorithm $\mathscr{G}$ relative to which the Discrete Logarithm problem is hard.

Eureka moment!

离散对数问题本质上是模意义下的对数运算。另外还需要注意一点，无论是 RSA 实验还是离散对数实验，对敌手的挑战 (challenge) 都是均匀随机 (uniform) 的。

其实，RSA 问题 (模意义下的开次方运算) 与离散问题 (模意义下的对数运算) 均可以视为幂运算 $h=g^x$ 的逆运算：RSA 问题给出指数 $x$ ，要求由 $h$ 计算底数 $g=h^{1/x}$ ；而离散对数问题给出底数 $g$ ，要求由 $h$ 计算指数 $x=\log_g h$ 。