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
