半群作用問題在密碼學中的應用.pdf

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

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

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

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