【作者】 黄华伟；

【导师】 肖国镇；

【作者基本信息】 西安电子科技大学 ， 密码学， 2008， 博士

【摘要】 各种半群作用问题,如离散对数问题和共轭问题,在现代密码学中有着广泛应用。源于离散对数问题困难性的计算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提出的乘法噪音多项式插值算法进行了分析,提出了改进算法。分别降低了原算法中有限域阶的下界和乘法近似黑盒的询问初值。更多还原

【Abstract】 All kinds of semigroup action problems such as discrete logarithm problem and conjugacy problem play very significant role in modern cryptography. The decisional Diffie-Hellman assumption from discrete logarithm is the base of security of many modern cryptosystems. Recently, many scholars have designed some simple cryptosystems based on conjugacy problem on several non-abelian groups. However, DDH assumption does not hold in bilinear groups and most cryptosystems based on conjuacy problem are not secure. So it is a very important research direction to find other appropriate semigroup action problem. This paper dissertation investigates the several semigroup action problems exploringly and analyzes logarithm problem, matrix semigroup action problem, multiple conjugacy search problem on Clifford semigroup and their related problems. The main results are as follows:(1) The algebraic theory of semigroup action is discussed. Split integral Dubreil-Jacotin semigroup is defined and studied and the structure of a class of split Dubreil-Jacotin semigroup is described by some ordered group action on ordered monoid.(2) An extended computational Diffie-Hellman problem and an extended decisional Diffie-Hellman problem based on a class of vector space of finite field with respect to matrix semigroup action are proposed. The relationship of n -ECDH assumption, n -EDDH assumption, DL assumption, CDH assumption and DDH assumption is analyzed. It is proved that the n -EDDH problem satisfies the random self-reducibility property and 2-EDDH assumption is weaker than the classic DDH assumption in the generic bilinear groups in the generic group model.(3) A new extended ElGamal public key encryption scheme is proposed. The new encryption scheme is one-way if and only if ECDH assumption holds and it is semantically secure in the standard model if and only if the EDDH assumption holds.(4) Several new extended Cramer-Shoup public key encryption schemes is proposed and analyzed. These schemes are proved secure against adaptive chosen ciphertext attack under EDDH assumption.(5) Two new constructions of pseudo-random functions are presented. The proof of security on them is proposed under the EDDH assumption and GECDH assumption.(6) Two algebraic key establishment protocol models are presented. The new key establishment protocol models are based on the multiple conjugacy (idempotent) search problem on Clifford semigroup. Some finite presented Clifford semigroup maybe implement these protocol models and resist the length attack.(7) Two amended multiplicative noisy polynomial interpolation algorithms presented by von zur Gathen and Shparlinski are proposed and analyzed. The amended algorithms reduce respectively the lower bound of the order of finite field and the initial query value inputted to multiplicatively approximate multiplicative black box.更多还原