随机预言机模型下可证明安全性关键问题研究

论文摘要

随着电子商务、政务等网络应用的蓬勃开展,设计安全并且高效的密码学方案成为密码学的一个重要课题。可证明安全理论（Provable Security）是在预先精确设定的安全模型下,用来验证一个设计好的密码学方案是否能抵御现实中自适应攻击者的形式化分析方法。早期的可证明安全体制一般是基于标准模型（StandardModel）下,将攻击者成功破解方案的概率可转化为攻破某已知困难问题的优势。但基于标准模型的密码学方案往往需要大量的计算,难以实用。随机预言机模型（Random Oracle Model）一经提出,便成为了平衡密码学方案的可证安全性和实用性的重要途径。在随机预言机模型当中,基于一个公共可访问的随机预言机,攻击者的能力仍然可以规约到某个困难问题,同时方案的计算开销也会因为随机预言机模型下许多紧规约技巧而大大降低。实际中,广泛使用的密码学方案和标准大都是基于随机预言机模型下可证安全的。虽然基于随机预言机模型设计方案具有高效率优势,该模型自身的安全性问题也不容忽视,许多负面例子说明现有广泛使用的伪随机函数、散列函数等并不能替换方案证明中所使用的随机预言机,甚至有研究结果表明替换后的方案会失去可证安全性。如何设计一个实际的,安全的散列函数,来替换模型中所使用的随机预言机,成为了近年来该领域的研究热点问题。我们对随机预言机模型的已有成果及其存在的安全性问题进行了总结和分析。首先我们针对基于分组密码的散列函数给出了相应的与随机预言机的白盒不可区分性（Indifferentiability）。1.我们给出了对基于分组密码的散列函数的白盒不可区分性的进一步分析,并给出了一个更加精确的对应基于分组密码的散列函数的白盒不可区分性攻击者的形式化定义。白盒不可区分性的优势对应于散列函数是否keyed的情况加以了区分。我们指出了Chang等人对于4种PGV和PBGV方案给出可区分性攻击存在缺陷,而且给出对应的形式化证明来表明4种PGV和PBGV构造实际上在使用Prefix-Free Padding、HMAC/NMAC和Chop Construction等改进型MD构造后,并同样基于压缩函数满足限定长度的随机预言机的性质,那么这些散列函数与随机预言机是满足白盒不可区分性的。2.基于密钥长度是分组长度两倍情况的分组密码,我们更进一步地对速率（Rate）为1的双倍分组长度散列函数的构造方法和安全性加以研究。研究工作可分为以下三个方面:首先,我们给出了针对Hirose提出的两个作为公开问题的例子的攻击,该攻击证实Hirose给出的例子并不能达到最优化抵抗原像和二次原像攻击,同时给出三个反例证明Hirose给出的最优化抗碰撞的两个必要条件并不完善。其次,基于上述攻击和反例,我们形式化的分析了由Satoh等人在文献中定义的速率为1的双倍分组长度散列函数,来找寻是否存在速率为1并且达到最优化安全的双倍分组长度散列函数。在上述分析之后,我们进一步给出了该类型下速率为1的双倍分组长度散列函数达到最优化安全的必要条件。特别地是,我们针对两个基于新的必要条件下的有代表性的例子给出了白盒不可区分性的形式化证明。其次,对于随机预言机模型下的可证明安全性,选择合适的紧致规约证明技巧来达到安全性与效率的平衡,在方案设计中也是十分重要的。将协议中使用的散列函数理想化为随机预言机,同时基于若干实用性签名方案的设计与规约证明,我们通过这些签名方案的可证明安全来介绍随机预言机模型下最有效的几种证明技巧。这些技巧都具有推广性和启发性,因而被广泛用在其他协议的设计、证明过程中。1.我们首先介绍了部分盲签名的基本概念及其安全性定义,随后基于离散对数问题给出了一种高效率的部分盲签名的方案（DLP-PBS）的设计与安全性分析,与以往若干方案相比,DLP-PBS方案的计算和存储开销均有降低。由于LFSR序列在替换表示有限域元素上的优势,我们基于n阶LFSR序列和DLP-PBS方案给出了另一种高效率的部分盲签名方案。我们所给出的两种部分盲签名方案均是在随机预言机模型下证明了其安全性。与有限域上的方案相比,基于LFSR的部分盲签名长度有所减少。特别的是,两种方案证明中都使用分叉引理作为安全性规约方法。2.我们给出了两种无证书公钥体制下的聚集签名方案。两种方案具有不同的优势,我们能根据实际应用场景的不同加以选择合适的方案。在随机预言机模型下,两种无证书聚集签名方案都通过全域散列规约方法将方案的安全性规约到了椭圆曲线上的计算Diffie-Hellman困难问题之上,没有使用分叉引理规约方法。

论文目录

• 中文摘要
• 英文摘要
• 目录
• 主要符号对照表
• 第一章 绪论
• 1.1 基于随机预言机模型的可证明安全研究现状
• 1.1.1 随机预言机模型的定义
• 1.1.2 随机预言机模型下可证明安全过程
• 1.1.3 随机预言机的类型
• 1.2 随机预言机模型下可证明安全规约方法
• 1.2.1 分叉引理规约方法
• 1.2.2 Heavy-Row规约方法
• 1.2.3 Full Domain Hash方案规约方法
• 1.3 随机预言机模型的不足之处
• 1.3.1 密码学散列函数与随机预言机的区别
• 1.3.2 随机预言机与实际散列函数的黑盒不可区分性
• 1.3.3 随机预言机与现有迭代结构设计的散列函数的白盒不可区分性
• 1.4 论文选题及内容安排
• 第二章 基于分组密码的散列函数与随机预言机不可区分性研究
• 2.1 散列函数与随机预言机不可区分性研究的背景介绍
• 2.2 分组密码散列函数和白盒不可区分性的定义
• 2.2.1 理想化分组密码模型的定义
• 2.2.2 白盒不可区分性的定义
• 2.2.3 基于分组密码的散列函数下的白盒不可区分攻击者
• 2.3 若干基于分组密码的散列函数的白盒不可区分性分析
• 2.3.1 白盒不可区分性的攻击优势分析
• 2.3.2 四种PGV构造散列函数的白盒不可区分性
• 2.3.3 PBGV散列函数的白盒不可区分性
• 2.4 本章小结
• 第三章 双倍分组长度散列函数与随机预言机不可区分性研究
• 3.1 双倍分组长度散列函数及其安全性研究的背景介绍
• 3.2 高效率双倍分组长度散列函数的相关定义和分析结果
• 3.2.1 基于分组密码的双倍分组长度散列函数的相关定义
• 3.2.2 散列函数安全性相关定义
• 3.2.3 以往高效率双倍分组长度散列函数的安全性结论
• 3.3 FDBL-II类型散列函数安全性的进一步分析
• 3.3.1 Yi-FDBL-II与随机预言机的白盒可区分性
• 3.3.2 针对Hirose实例的原像、二次原像攻击及若干反例
• 3.3.3 更准确的FDBL-II安全性分析
• 3.4 新的一类高效率双倍分组长度散列函数
• 3.5 本章小结
• 第四章 两种部分盲签名方案的设计与可证明安全
• 4.1 盲签名方案的设计与可证明安全背景介绍
• 4.2 部分盲签名相关概念和可证明安全模型
• 4.3 一种基于离散对数困难问题的部分盲签名方案
• 4.3.1 部分盲签名方案描述
• 4.3.2 方案的安全性分析
• 4.3.3 方案的效率分析
• 4.4 一种基于LFSR的部分盲签名方案
• 4.4.1 LFSR序列的定义
• 4.4.2 LFSR序列运算和困难问题定义
• 4.4.3 基于LFSR的部分盲签名方案描述
• 4.4.4 方案的安全性分析
• 4.4.5 方案的效率分析
• 4.5 本章小结
• 第五章 两种无证书体制下聚集签名方案的设计与可证明安全
• 5.1 无证书体制聚集签名的应用背景
• 5.1.1 无证书公钥密码体制
• 5.1.2 聚集签名方案
• 5.2 无证书聚集签名方案的定义及其安全模型
• 5.2.1 双线性映射和CDH困难问题的定义
• 5.2.2 无证书聚集签名方案的形式化定义
• 5.2.3 无证书聚集签名方案的安全模型
• 5.3 两种无证书体制下的聚集签名方案的设计与安全性分析
• 5.3.1 第一种无证书聚集签名方案的设计
• 5.3.2 第一种无证书聚集签名方案的安全性分析
• 5.3.3 第二种无证书聚集签名方案的设计
• 5.3.4 第二种无证书聚集签名方案的安全性分析
• 5.4 两种方案的效率分析
• 5.5 本章小结
• 第六章 总结与展望
• 6.1 全文工作总结
• 6.2 对下一步工作的展望
• 参考文献
• 致谢
• 攻读博士学位期间发表及完成的论文