半群作用問題在密碼學(xué)中的應(yīng)用.pdf

1、各種半群作用問題，如離散對數(shù)問題和共軛問題，在現(xiàn)代密碼學(xué)中有著廣泛應(yīng)用。源于離散對數(shù)問題困難性的計算Difile-Hellman假設(shè)和判定Diffie-I-tellman假設(shè)是眾多現(xiàn)代密碼體制安全性的基石。近幾年，許多學(xué)者基于某些非交換群上共軛問題及其相關(guān)問題的困難性也設(shè)計了較為簡單的公鑰密碼體制。然而，DDH假設(shè)在雙線性群上并不成立，大多數(shù)基于共軛問題的的密碼體制也并不安全。尋找其他合適的半群作用問題是一個重要的研究方向。本文對幾類半

2、群作用問題做了探索性研究。研究了離散對數(shù)問題、矩陣半群作用問題及其相關(guān)問題、Clifford半群上的多重共軛搜索問題及其相關(guān)的問題，得到如下主要結(jié)果： (1)研究了半群作用的抽象代數(shù)理論。定義并研究了可分整Dubreil-Jacotin半群，利用序群對序幺半群的作用刻畫了一類可分整Dubreil-Jacotin半群的結(jié)構(gòu)。 (2)基于一類關(guān)于矩陣半群作用的有限域上向量空間，提出了廣義計算Dime-Hellman(n-EC

3、DH)問題和廣義判定Diffie-Hellman(n-EDDH)問題。分析了n-ECDH問題和n-EDDH問題與離散對數(shù)問題、CDH問題和DDH問題之間的關(guān)系。證明了n-EDDH問題滿足隨機自歸約性，DDH問題可多項式時間歸約為n-EDDH問題。在一般群模型下，雙線性群上2-EDDh假設(shè)要弱于DDH假設(shè)。 (3)構(gòu)造了新的廣義E1Gamal公鑰加密方案，它是單向的當(dāng)且僅當(dāng)ECDH假設(shè)成立，它是語義安全的當(dāng)且僅當(dāng)EDDh假設(shè)成立。

4、 (4)構(gòu)造了幾個新的廣義Cramer-Shoup公鑰加密方案，在EDDH假設(shè)下，它們是標(biāo)準(zhǔn)模型下INI)-CCA2安全的。 (5)構(gòu)造了兩類新的偽隨機函數(shù)。在EDDH假設(shè)和GECDH假設(shè)下，分別證明了它們的安全性。 (6)提出基于Clifford半群上的多重共軛搜索問題和多重冪等元搜索問題的密鑰建立協(xié)議代數(shù)模型。利用某些有限表達的Clifiord半群有可能實現(xiàn)這種協(xié)議并能抵抗長度攻擊。 (7)對yon