DH问题汇总
本节内容主要转载于：弄清楚DL，D-H，CDH problem，CDH assumption，DDH，BDDH，BCDH。
DLP（Discrete Logarithm Problem）
在乘法群\((G,*)\)中：
离散对数问题：就是给出两个群元素\(P,Q\),求整数\(n\in Z_q^*\)是困难的，满足\(Q=P^n\)
DH密钥交换协议
具体请参考：计算困难假设（Computational hardness assumption），DH密钥交换
基于DLP（ 离散对数问题）的困难性。
DDHP（Decision Diffie-Hellman Problem）
给出任意\((a,b,c)\), 有多项式时间算法能将\((g^a,g^b,g^{ab})\) 和\((g^a,g^b,g^c)\)两者明显的区分开来。说白了就是区分\(ab\)和\(c\)，仍然是基于DLP。
BDDHP（bilinear decisional Diffie-Hellman Problem）
给出任意\(（a,b,c,d）\), 有多项式时间算法能\((g^a,g^b,g^c,g^{abc}))\)和\((g^a,g^b,g^c,g^d)\)两者区分开来是困难的。
CDHP（Computational Diffie-Hellman Problem）
给出任意的\(g^a,g^b\)，当数值较大时，求\(g^{ab}\)是困难的。
CDHP又分为两种：
Inv-CDHP（Inverse Computational Diffie-Hellman Problem）
求逆：对于\(a ∈ Z_q^*\), 给出\(P, P^a\)，计算\(P^{a^{-1}}\)是困难的.
Squ-CDHP（Square Computational Diffie-Hellman Problem）
求平方：对于\(a ∈ Z_q^*\), 给出\(P, P^a\)，计算\(P^{a^{2}}\)是困难的.
BCDHP（Bilinear Computational Diffie-Hellman problem ）
任意选取\((a,b,c)\)，在多项式时间内计算出\(g^{abc}\)是困难的
GHP群（Gap Diffie-Hellman group）
在一个群中，DDHP是容易的但CDHP很难的就被称为GDH。通过双线性对（bilinear pairing），我们可以得到GDH群，这种群在有限域上的supersingular 椭圆曲线或者hyperelliptic 椭圆曲线上可以找到，双线性对来自Weil 或者 Tate pairing。
可以看出BDDHP和BCDHP比DDHP和CDHP多了一个变量，为什么要多加一个变量？
因为，如果存在一个\(GxG\to G’\)（\(G，G’\)都是群）的双线性对的话， DDH问题是可以被快速解决的。所以就有了BDDH，故即使存在双线性对，BDDH问题仍然是难以计算的。
参考
1、An Efficient Signature Scheme from Bilinear Pairings and Its Applications
