论文部分内容阅读
从1991年到1992年,Baumslag等人以及Epstein等人分别系统地对自动机群进行了研究.之后的十五年中,自动机群成为了组合群论的一个热门的研究方向.这类群之所以受到众多学者的关注,首先这是一类包含十分广泛的群(例如所有的有限群,有限生成的自由群,有限生成的Abel群,小消去群等);其次,这类群有着十分漂亮的几何性质;另外,这类群的定义基于形式语言和自动机,与自动推理有着密切的联系.一方面,在密码学研究中,人们注意到公钥密码体制如RSA,ECC(椭圆曲线加密算法)等的安全性被认为是等价于一些数学问题的计算复杂性(RSA的安全性被认为是等价于整数分解的困难度,ECC的安全性被认为是等价于求Abel群上的离散对数的困难度).然而,这些所谓的等价在理论上并没有得到证明.并且,由于可以预见的量子计算机的出现,也将使得这些在目前被认为是困难的问题变得容易.为此,人们试图应用自动机群的若干判定问题(如字问题、共轭问题及子群成员问题)的困难度来构建新的密码体制,希望能寻求构造字问题在多项式时间可解,而其共轭问题至少是指数时间才可解的(异步)自动机(半)群,使之能经受量子计算机的考验,理论上这样的群是存在的.在这个问题上,我们继续Campbell等人的工作,于论文的第二章给出异步自动机半群的定义以及若干基本性质,为进一步在此基础上构造具体的具有所希望性质的异步自动机半群提供了理论支持.
2000年,Ko等人在文献[14]中提出了一个基于辫群(一类自动机群)的密码体制,该系统的可操作性基于辫群的字问题是多项式时间可解,而其安全性则寄希望于辫群的共轭问题至少是指数时间可解的.可是不幸的是Cheon和Jun给出了一个算法使得上述共轭元素搜索问题在多项式时间内可解,从而Braid群似乎不再是理想的群.基于这些想法,本文于第四章提出了基于辫群成员问题的密码体制.我们证明此密码体制的安全性是基于辩群具有某些子群的成员搜索问题是不可解的.