论文部分内容阅读
各种半群作用问题,如离散对数问题和共轭问题,在现代密码学中有着广泛应用。源于离散对数问题困难性的计算Diffie-Hellman假设和判定Diffie-Hellman假设是众多现代密码体制安全性的基石。近几年,许多学者基于某些非交换群上共轭问题及其相关问题的困难性也设计了较为简单的公钥密码体制。然而,DDH假设在双线性群上并不成立,大多数基于共轭问题的的密码体制也并不安全。寻找其他合适的半群作用问题是一个重要的研究方向。本文对几类半群作用问题做了探索性研究。研究了离散对数问题、矩阵半群作用问题及其相关问题、Clifford半群上的多重共轭搜索问题及其相关的问题,得到如下主要结果:(1)研究了半群作用的抽象代数理论。定义并研究了可分整Dubreil-Jacotin半群,利用序群对序幺半群的作用刻画了一类可分整Dubreil-Jacotin半群的结构。(2)基于一类关于矩阵半群作用的有限域上向量空间,提出了广义计算Diffie-Hellman( n -ECDH)问题和广义判定Diffie-Hellman( n -EDDH)问题。分析了n -ECDH问题和n -EDDH问题与离散对数问题、CDH问题和DDH问题之间的关系。证明了n -EDDH问题满足随机自归约性,DDH问题可多项式时间归约为n -EDDH问题。在一般群模型下,双线性群上2-EDDH假设要弱于DDH假设。(3)构造了新的广义ElGamal公钥加密方案,它是单向的当且仅当ECDH假设成立,它是语义安全的当且仅当EDDH假设成立。(4)构造了几个新的广义Cramer-Shoup公钥加密方案,在EDDH假设下,它们是标准模型下IND-CCA2安全的。(5)构造了两类新的伪随机函数。在EDDH假设和GECDH假设下,分别证明了它们的安全性。(6)提出基于Clifford半群上的多重共轭搜索问题和多重幂等元搜索问题的密钥建立协议代数模型。利用某些有限表达的Clifford半群有可能实现这种协议并能抵抗长度攻击。(7)对von zur Gathen和Shparlinski提出的乘法噪音多项式插值算法进行了分析,提出了改进算法。分别降低了原算法中有限域阶的下界和乘法近似黑盒的询问初值。