半群作用问题在密码学中的应用

论文摘要

各种半群作用问题,如离散对数问题和共轭问题,在现代密码学中有着广泛应用。源于离散对数问题困难性的计算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
• 第一章 绪论
• 1.1 密码学简介
• 1.2 单向函数与半群作用问题
• 1.3 半群作用问题的研究内容与现状
• 1.3.1 离散对数问题及其相关问题的研究现状
• 1.3.2 共轭作用问题及其相关问题的研究现状
• 1.3.3 半群作用问题的理论研究现状
• 1.4 论文的内容安排和主要结果
• 第二章 半群作用与半群作用问题
• 2.1 半群作用与半直积
• 2.1.1 半群在集合上的作用
• 2.1.2 半群在半群上的作用
• 2.2 可分整DUBREIL-JACOTIN半群
• 2.2.1 强Dubreil-Jacotin 半群
• 2.2.2 可分整Dubreil-Jacotin 半群的性质
• 2.2.3 结构定理
• 2.3 半群作用问题
• 2.4 矩阵半群在交换群直积上的作用
• 2.5 本章小结
• 第三章 基于矩阵半群作用的广义DIFFIE-HELLMAN 假设
• 3.1 符号约定与预备知识
• 3.2 广义计算群方案
• 3.2.1 基于矩阵作用的有限域上的向量空间
• 3.2.2 广义计算群方案
• 3.3 广义离散对数假设
• 3.4 广义DIFFIE-HELLMAN假设
• 3.4.1 广义计算Diffie-Hellman 问题
• 3.4.2 广义判定Diffie-Hellman 问题
• 3.4.3 双线性群上的2-EDDH 问题
• 3.5 本章小结
• 第四章 基于矩阵半群作用的公钥加密方案
• 4.1 公钥加密方案及其可证明安全性
• 4.2 广义ELGAMAL 公钥加密方案
• 4.2.1 方案的描述
• 4.2.2 安全性证明
• 4.3 广义CRAMER-SHOUP 公钥加密方案
• 4.3.1 无目标碰撞hash 函数
• 4.3.2 方案的描述
• 4.3.3 安全性证明
• 4.3.4 GCS 加密方案的简化版本
• 4.3.5 无hash 函数的GCS 加密方案
• 4.4 本章小结
• 第五章 基于矩阵半群作用的伪随机函数
• 5.1 伪随机函数
• 5.2 基于EDDH 假设的伪随机函数
• 5.2.1 构造方案及主要结果
• 5.2.2 安全性证明
• 5.3 基于GECDH 假设的伪随机函数
• 5.4 本章小结
• 第六章 基于CLIFFORD 半群的密钥建立协议代数模型
• 6.1 IRIS ANSHEL 密钥建立协议模型
• 6.2 CLIFFORD 半群及其有关问题
• 6.3 基于CLIFFORD 半群的密钥建立协议
• 6.3.1 基于MSCSP 的密钥建立协议
• 6.3.2 基于MSISP 的密钥建立协议
• 6.4 有限表达的CLIFFORD 幺半群重写系统
• 6.4.1 自由Clifford 半群与重写系统
• 6.4.2 基于Clifford 半群重写系统的密钥建立协议
• 6.5 本章小结
• 第七章 格归约与乘法噪声多项式插值
• 7.1 格的相关知识
• 7.2 有限域上乘法噪声多项式插值算法的改进
• 7.2.1 有限域上GS 乘法噪声多项式插值算法
• 7.2.2 算法的改进
• 7.3 整数环上乘法噪声多项式插值算法的改进
• 7.3.1 整数环上GS 乘法噪声多项式算法
• 7.3.2 算法的改进
• 7.4 本章小结
• 结束语
• 致谢
• 参考文献
• 攻读博士学位期间的研究成果
• 参与的科研项目