前言

密碼學(xué)的安全本質(zhì)上依賴于數(shù)學(xué)問題中的未解“難題”。注意，這些“難題”到目前為止還未找到一種多項(xiàng)式的解決算法，至于這種算法是否存在，未來能否被找到則是無法證明的。既然目前不存在一種多項(xiàng)式算法來解決某一難題，那我們就可以假設(shè)這個(gè)問題很難，在多項(xiàng)式時(shí)間內(nèi)無法被解決。實(shí)際上，CDH DDH等假設(shè)正是基于這種考慮，就是在假設(shè)所對(duì)應(yīng)的CDH DDH問題很難不能在多項(xiàng)式時(shí)間內(nèi)解決。如果你不同意我的假設(shè)，你就需要提供存在一種多項(xiàng)式解法（很難的啦）。

為什么要強(qiáng)調(diào)多項(xiàng)式時(shí)間？因?yàn)槿魏巍半y題”都只是說沒有快速的解法，而非不可解。畢竟在不考慮時(shí)間成本時(shí)，暴力法是所有問題的通用解法。當(dāng)然，運(yùn)氣法也可以。

在安全性分析中，當(dāng)我們想通過某一假設(shè)來證明方案的安全性時(shí)，我們首先需要將方案的安全性問題歸約為對(duì)應(yīng)的問題上。之后，我們可以得出結(jié)論：如果假設(shè)A成立（引用別人的假設(shè)文獻(xiàn)作為定理），那么任何攻擊者都無法在多項(xiàng)式時(shí)間內(nèi)破解我們的方案，因?yàn)槿魏喂粽叨紵o法在多項(xiàng)式時(shí)間內(nèi)解決問題A。結(jié)論是基于假設(shè)的，而假設(shè)是具有時(shí)效性的。例如，如果某一天某個(gè)天才破解了問題A，那么上述的推斷就不成立了。因此，在未來的某一天，我們現(xiàn)在提出的假設(shè)都可能被推翻。

定義

DH假設(shè)

DH問題來自于1976年提出的Diffie-Hellman密鑰交換協(xié)議，其數(shù)學(xué)定義可以描述為：

給定$<g,p,g^a(modp),g^b(modp)>$，攻擊者能否在多項(xiàng)式時(shí)間內(nèi)計(jì)算出$g^{ab}(modp)$？

該問題依賴的數(shù)學(xué)難題是離散對(duì)數(shù)問題（Discrete Logarithm Problem，DLP）。DH假設(shè)的就是在說DLP問題很難，因此DH問題也很難。很明顯，這是成立的，因?yàn)殡x散對(duì)數(shù)問題至今仍未被解決。想要推翻這個(gè)假設(shè)你就得解決DLP問題，總不能拿不出證據(jù)又不承認(rèn)。

CDH假設(shè)和DDH假設(shè)

CDH假設(shè)（Computational Diffie-Hellman Assumption）和DDH假設(shè)（Decisional Diffie-Hellman Assumption）是DH假設(shè)的變體，將線性離散問題轉(zhuǎn)移到群論離散問題。我們說過，假設(shè)都是對(duì)應(yīng)問題的，兩者所對(duì)應(yīng)的問題分別為：

Computational Diffie-Hellman Problem（CDHP）：
對(duì)于循環(huán)群$G$和生成元$g$，給定$<G,g,g^a,g^b>$，攻擊者能否在多項(xiàng)式時(shí)間計(jì)算出$g^{ab}$?

Decisional Diffie-Hellman Problem（DDHP）：
對(duì)于循環(huán)群$G$和生成元$g$，給定$<G,g,g^a,g^b,g^c>$，攻擊者能否在多項(xiàng)式時(shí)間判斷出$g^c\stackrel{\text{?}}{=}{g}^{ab}$?

類似的，CDH假設(shè)就是認(rèn)為CDHP無多項(xiàng)式時(shí)間解，而DDH假設(shè)是認(rèn)為DDHP無多項(xiàng)式時(shí)間解。

問題1，CDHP和DDHP的差異在哪？哪個(gè)更難解決？從上面的問題定義中可以看出，兩者主要差異是對(duì)攻擊者的要求，前者要求攻擊者計(jì)算出結(jié)果，而后者要求攻擊者判斷一個(gè)結(jié)果對(duì)不對(duì)。那么哪個(gè)更難呢？答案是CDHP難于DDHP，因?yàn)槿绻隳芙鉀QCDHP，那你就能解決DDHP。試想，你都能算出$g^{ab}$了，還能不知道$g^c\stackrel{\text{?}}{=}{g}^{ab}$。但是反過來不行啊，你不能說我知道了$g^c\ne g^{ab}$我就知道了$g^{ab}$。DDHP可以看作是CDHP的放松版，簡(jiǎn)單點(diǎn)說就是，你算不出來不要緊，我給你個(gè)數(shù)，你驗(yàn)證一下是不是正確解就完事了。所以，我們得出：在問題難度方面，$CDHP\ge DDHP$。我們?cè)侔袲LP也算上。同樣的道理，解決了DLP就能解決CDHP，但是解決了CDHP不一定能解決DLP，因此我們可以得出結(jié)論：在問題難度方面，$DLP\ge CDHP\ge DDHP$。

問題2，是否問題越難，所對(duì)應(yīng)的假設(shè)越強(qiáng)？答案是否。假設(shè)的強(qiáng)度與問題的難度相反，問題越難，假設(shè)越弱。注意，這里的強(qiáng)弱是指安全等級(jí)，因?yàn)榧僭O(shè)是用在安全分析上的，不是說假設(shè)越弱越容易被推翻，因?yàn)樗械募僭O(shè)都是基于離散問題的，都是成立的，都是難解的“難題”，切勿誤解。試想一下，如果我們的系統(tǒng)A在數(shù)學(xué)上滿足DDH假設(shè)，也就是說沒有人能夠在多項(xiàng)式時(shí)間內(nèi)解決DDHP。你連最簡(jiǎn)單的DDHP都解決不了，就更不可能解決CDHP了。就好比你連加法都不會(huì)，還想學(xué)高等數(shù)學(xué)？反過來，如果我們的系統(tǒng)B在數(shù)學(xué)上只滿足CDH假設(shè)，也就意味著攻擊者能夠解決DDHP。對(duì)比而言，攻擊者在B上能做的計(jì)算更多，所以我們說A系統(tǒng)強(qiáng)于B系統(tǒng)。因?yàn)锳系統(tǒng)依賴于DDH假設(shè)，B系統(tǒng)依賴于CDH假設(shè)，所以，我們說在安全強(qiáng)弱方面：$DDH\ge CDH$。在一般的論文分析中，為了體現(xiàn)設(shè)計(jì)的方案足夠安全，普遍采用的是Decisonal版本的假設(shè)，即DDH假設(shè)，下面的BDH系列也是。

CBDH假設(shè)和DBDH假設(shè)

CBDH假設(shè)（Computational Bilinear Diffie-Hellman Assumption）和DBDH假設(shè)（Decisional Bilinear Diffie-Hellman Assumption）是CDH的變體。前面提CDH假設(shè)和DDH假設(shè)時(shí)說的是將DH中的線性離散問題轉(zhuǎn)移到群論離散問題，那么CBDH假設(shè)和DBDH假設(shè)就是將CDH和DDH中的群論離散問題轉(zhuǎn)移到雙線性映射中的橢圓曲線離散問題。

雙線性映射操作的也是循環(huán)群，但是是滿足特定屬性的循環(huán)群，通常會(huì)使用橢圓曲線理論來得到這樣的循環(huán)群。有趣的是，橢圓曲線理論最早用于橢圓曲線加密法（ECC）中，而雙線性映射是在破解ECC的過程中發(fā)現(xiàn)的，之后人們發(fā)現(xiàn)這個(gè)性質(zhì)太適合用于加密了。數(shù)學(xué)上計(jì)算出滿足這種性質(zhì)的循環(huán)群是比較難的，目前主流的庫包括python的pypbc（這玩意兒依賴于PBC庫，這個(gè)庫只支持Linux系統(tǒng)）和Java里面的jpbc（聽過沒用過）。

都是群論離散問題，為什么有CDH和DDH不用又要提出還要提出新的假設(shè)呢？因?yàn)檠h(huán)群的屬性增加了，之前的假設(shè)無法保證新增的屬性不會(huì)帶來安全問題。實(shí)際上，現(xiàn)存的假設(shè)遠(yuǎn)不止這些，比如，我還在其他論文中看到過一種名為$l$-DCBDH（Decisional $l$-Combined Bilinear Diffie-Hellman）的變體。只能說具體場(chǎng)景具體分析。

同樣，我們給出兩個(gè)假設(shè)對(duì)應(yīng)的問題

Computational Bilinear Diffie-Hellman Problem（CBDHP）：
對(duì)于循環(huán)群$G_1,G_2$，生成元$g$和映射函數(shù)$e$，給定$<G_1,G_2,e,g,g^a,g^b,g^c>$，攻擊者能否在多項(xiàng)式時(shí)間計(jì)算出$e(g,g{)}^{abc}$?

Decisional Bilinear Diffie-Hellman Problem（DBDHP）：
對(duì)于循環(huán)群$G_1,G_2$，生成元$g$和映射函數(shù)$e$，給定$<G_1,G_2,e,g,g^a,g^b,g^c,e(g,g{)}^d>$，攻擊者能否在多項(xiàng)式時(shí)間判斷出$e(g,g{)}^d\stackrel{\text{?}}{=}e(g,g{)}^{abc}$?

同樣，CBDH假設(shè)認(rèn)為CBDHP無多項(xiàng)式解，DBDH假設(shè)認(rèn)為DBDHP無多項(xiàng)式解。Computational版本和Decisional版本的差異和上面是一樣的，此處就不再重復(fù)。也是同樣的道理，在安全性分析中我們常用的是DBDH假設(shè)。文章來源地址http://www.zghlxwxcb.cn/news/detail-454639.html

到了這里，關(guān)于對(duì)安全性證明中DH BDH等相關(guān)假設(shè)的理解（安全）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！