公钥密码学已经发展了三十余年,许多优秀的公钥密码系统被不断地提出并逐渐完善。但是,量子计算的最新研究成果对许多基于数论难题假设的公钥密码系统形成了潜在威胁。于是,人们开始积极探索那些可以抵抗已知量子分析的公钥密码系统。基于辫群的公钥密码系统正是其中之一。自从Ko等人于2000年提出基于辫群的公钥密码系统以来,基于辫群的公钥密码系统的发展虽然经历了不少曲折,但目前仍然是公钥密码学研究领域中十分活跃的主题之一。近年来,算法研究方面的进展对辫群密码系统的基础假设—共轭搜索问题(CSP)困难性假设提出了质疑,但是并未形成任何定论。另外,已经发表的基于辫群的公钥密码方案,具有可证明安全模型者甚少;即使那些底层难题最终被证明是困难的,现有的基于辫群的密码方案也不具备人们所期望的安全属性。因此,本文研究的重点是:(1)分析目前已经发表的典型的求解CSP问题的方法的计算复杂度;(2)研究基于辫群的数字签名体制,设计可证明具有EUF-CMA安全性(即在自适应选择消息攻击下存在性不可伪造)的新的签名体制;(3)研究并设计基于自分配系统的密码方案。主要研究成果如下:1.为求解CSP问题的各个典型方法提供了具体的算法描述和详细的复杂性分析,指出了SSS集合、USS集合和U-轨道之间的关系,并对USS方法所宣称的高效性提出质疑。我们的结论是:目前发表的求解CSP问题的方法还没有一个能够被证明是可以在多项式时间内完成的。另外,澄清了一些人关于CSP难解性和群的小消去条件之间的关系的一个误解。2.基于CSP困难性假设,设计了两个基于辫群的比特承诺方案:一个是标准的比特承诺方案;另一个是推广的非平衡的比特承诺方案。基于辫群实现比特承诺协议有着计算效率和安全性级别两方面的优势。3.提出了辫群上的密码学新问题—“多一”匹配共轭问题,并且基于该问题的困难性假设,对Ko等人提出的基于辫群的签名体制给出了新的安全性规约。这是首次证明了一个基于辫群的签名体制具有EUF-CMA安全性。4.提出了辫群上的另外一个密码学新问题—共轭连接问题,并且基于该问题的困难性假设,设计了新的基于辫群的数字签名体制。新体制也被证明具有EUF-CMA安全性。5.设计了多个基于自分配系统的密码体制。这是首次系统地从密码设计的角度对自分配系统进行的考察,取得了较为丰富的结果:(a)设计了基于1-型左自分配系统(LD1)的数字签名方案。(b)设计了基于1-型中自分配系统(CD1)的数字签名方案和具有部分变色龙属性的哈希函数。(c)提出了其它14种形式的自分配系统。(d)设计了基于2-型中自分配系统(CD2)的数字签名方案。(e)设计了基于1-型右自分配系统(RD1)的数字签名方案和认证方案。