基于Clifford半群上共轭搜索问题的密钥建立协议

A Key Establishment Protocol Based on Conjugacy Search Problem in Clifford Semigroups

本文采用更广泛的半群作为平台,推广了Iris Anshel等提出的代数密钥建立协议模型。在定义了Clifford半群上的多重同时共轭搜索问题(MSCSP)后,给出了基于此问题的密钥建立协议。在理论上证明了若Clifford半群上的多重同时共轭搜索问题(MSCSP)是困难的,那么可以利用MSCSP来构造密钥建立协议,从而说明利用半群作为平台构建密钥建立协议是可能的。本文也提供了一种新的利用辫群的思路,即考虑利用辫群上的强半格(许多辫群按照一定规则形成的无交并)构成的Clifford半群来构建密码协议,以弥补单个辫群可能存在的安全缺陷。

This paper improves on an algebraic key establishment protocol presented by Iris Anshel et al. In our protocol, semigroup instead of group is adopted. After defining the multiple simultaneous conjugacy search problem （MSCSP）in Clifford semigroups, we give a key establishment protocol based on MSCSP. It is proved that if the MSCSP in some Clifford semigroups is hard, we can use this class Clifford semigroups to construct key establishment protocols. Hence it is possible to make use of semigroups as a platform to construct key establishment protocols. This paper also suggests a method of using braid group. We may make use of the strong semilattiee of braid groups （the disjoint unions formed by many braid groups according to some rules）to construct cryptological protocol and remedy the possible secure bug of a simple braid group.