辫群密码体制的设计与分析

第1章 绪论 1

1.1 公钥密码学 1

1.1.1 里程碑 1

1.1.2 安全模型 2

1.1.3 典型的方案构造技术和安全性证明方法 4

1.2 量子计算的发展及其对公钥密码学的启示 6

1.3 辫群密码系统简介 7

1.3.1 基于辫群的密码体制 8

1.3.2 基于辫群的密码方案的分析 9

1.3.3 有关辫群密码的其他问题 10

第2章 辫群密码系统的数学基础 13

2.1 辫群基础 13

2.1.1 辫群定义 13

2.1.2 辫子的唯一表示及其在计算机上的实现 15

2.2 辫群上的密码学难题 17

2.3 求解共轭问题的算法 19

2.3.1 Garside算法 20

2.3.2 EM算法 22

2.3.3 FM算法 26

2.3.4 USS算法 28

2.3.5 辫群的小消去条件与CSP难解性 32

第3章 基于辫群的比特承诺协议设计与分析 40

3.1 比特承诺协议 40

3.2 基于辫群的比特承诺协议 41

3.2.1 正确性 42

3.2.2 安全性分析 42

3.2.3 性能比较 43

3.3 非平衡的比特承诺协议 46

3.3.1 非平衡比特承诺协议的定义 47

3.3.2 基于辫群的非平衡比特承诺协议 47

3.3.3 正确性 48

3.3.4 安全性 49

3.3.5 与标准比特承诺、比特串承诺以及不经意传输的关系 50

3.3.6 非平衡比特承诺协议的几个应用 51

第4章 基于辫群的数字签名方案 53

4.1 基于辫群的数字签名的发展 53

4.2 准备工作 53

4.2.1 关于三个基于辫群的密码学问题的进一步讨论 54

4.2.2 辫子抽样、系统参数选择以及密钥生成问题 55

4.3 多一匹配共轭问题 56

4.4 基于辫群的签名体制的安全性 58

4.4.1 简单共轭签名方案及其改进 58

4.4.2 安全性概念及证明 60

4.4.3 基于辫群上三元组形式的匹配共轭问题的数字签名方案 63

4.5 基于辫群上共轭连接问题的数字签名体制 64

4.5.1 辫群上的共轭连接问题 64

4.5.2 基于共轭连接问题的新型数字签名方案 67

4.5.3 性能分析和对比 69

4.6 基于辫群的传递签名体制 70

4.7 基于辫群的盲签名体制 73

第5章 基于自分配系统的密码体制 76

5.1 问题的提出 76

5.2 左自分配系统的引入 78

5.2.1 左自分配系统的定义 78

5.2.2 左自分配系统上的密码学假设 78

5.2.3 基于左自分配系统的认证体制 79

5.3 基于左自分配系统的数字签名体制的设计 80

5.3.1 设计一 80

5.3.2 设计二 82

5.4 中自分配系统及签名设计 87

5.4.1 中自分配系统的定义及其单向性假设 87

5.4.2 基于中自分配系统的签名设计 87

5.4.3 考察另外一种类型的中自分配系统 88

5.4.4 关于中自分配系统的一个注记 89

5.5 右自分配系统及签名设计 90

5.5.1 右自分配系统的定义及单向性假设 90

5.5.2 基于右自分配系统的签名设计 90

5.6 其他自分配系统 91

5.7 基于自分配系统的其他密码方案的设计 92

5.7.1 基于中自分配系统CD1的哈希函数设计 92

5.7.2 基于右自分配系统RD1的认证方案 93

5.8 自分配系统的实现问题 93

5.8.1 一个平凡的左自分配系统 94

5.8.2 基于共轭搜索问题的左自分配系统 94

5.8.3 基于移位共轭搜索问题的左自分配系统 94

第6章 非交换密码展望 97

附录A 计算复杂性理论与随机预言机模型简介 99

A.1 计算复杂性理论简介 99

A.1.1 背景和基本定义 99

A.1.2 复杂性类 100

A.1.3 可忽略与多项式时间不可区分的概念 102

A.2 随机预言机模型简介 102

A.2.1 哈希函数 103

A.2.2 随机预言机模型 103

附录B 群中的判断型问题 105

B.1 群中基本判断型问题的定义 105

B.2 群中判断型问题的可解性 106

附录C 生成辫子图像的Maple代码 108

参考文献 117