Diffie-Hellman 问题

Diffie-Hellman Problem.

Fix cyclic group $\mathbb{G}$ of order $q$ , and generator $g\in\mathbb{G}$ .

Given elements $h_1,h_2\in \mathbb{G}$ , define Diiffie-Hellman function $DH_g(h_1,h_2)=g^{\log_g h_1\cdot\log_g h_2}$ . That is, if $h_1=g^{x_1}$ , $h_2=g^{x_2}$ , then $DH_g(h_1,h_2)=g^{x_1\cdot x_2}$ .

Computational Diffie-Hellman (CDH) in $\mathbb{G}$ : Given $g\in \mathbb{G}$ , and uniform $h_1,h_2\in\mathbb{G}$ , compute $DH_g(h_1,h_2)$ .

Decisional Diffie-Hellman (DDH) in $\mathbb{G}$ : Given $g\in\mathbb{G}$ , and uniform $h_1,h_2\in\mathbb{G}$ , distinguish $DH_g(h_1,h_2)$ from a uniform group element $h'\in \mathbb{G}$ .

CDH and DDH experiments could be constructed similarly so they are not covered here.

It is easy to see that if one could solve Discrete Logarithm problem, he could also solve CDH problem; and if one could solve CDH problem, he could also solve DDH problem.

**So DLog $\to$ CDH $\to$ DDH, the assumption is getting stronger and stronger, ** which is to say, if one could NOT solve DDH problem, it would be impossible for him to solve CDH or DLog problem.

Eureka moment!

Diffie-Hellman 问题的困难性是由离散对数问题的困难性保证的。至于为什么要定义这样一个函数，是由于 Diffie-Hellman 问题定义了两个可以暴露的量 $h_1,h_2$ 。当 Alice 与 Bob 之间需要进行多次信息传输时，利用 Diffie-Hellman 问题的困难性可以很好的隐藏秘密信息。

以著名的 Diffie-Hellman Key-exchange Protocol (密钥交换协议) 为例：Alice 选择某个 $x_1$ ，并向 Bob 发送 $h_1=g^{x_1}$ ；而 Bob 选择某个 $x_2$ ，并向 Alice 发送 $h_2=g^{x_2}$ 。这样，Bob 与 Alice 双方都可以计算出密钥 $k=g^{x_1x_2}=h_1^{x_2}=h_2^{x_1}$ ，密钥交换成功。而 Diffie-Hellman 问题的困难性保证窃听到 transcript $h_1,h_2$ 的敌手无法据此求出 $k=DH_g(h_1,h_2)$ .