承诺和零知识的非延展属性研究

摘要

密码协议是指应用密码学方法的通讯协议，它是构建安全信息系统的一个基本要素。随着计算机网络应用的不断深化，对密码协议的安全性进行分析和研究，已成为一个十分重要的研究方向。密码协议运行在计算机网络或分布式系统中，在这种环境中，敌手对于协议可以有多种攻击手段，包括截取、修改和删除消息，假冒和控制实体等。其中中间人攻击是一类最常见的攻击方法，它涵盖了现有多种的攻击手段。在各种密码协议中，承诺方案和零知识协议是两个非常基本的密码学原语，它们在其它密码学协议和更高级的安全系统有着广泛的应用，比如抛币协议、安全两方计算、安全多方计算、加密方案、签名方案、身份识别方案、密钥交换协议、秘密分享方案和电子投票方案等。最近，针对承诺方案和零知识协议的一个研究热点，主要集中在抗中间人攻击方面，包括从改进方案效率、提高安全性、减弱困难问题假设等方面。如果承诺方案或者零知识协议抵抗中间人攻击，则我们一般称其具有非延展属性。
　　根据不同的应用安全需求，非延展承诺方案分为两类，一种是关于承诺的，另外一种是关于打开的。关于承诺的非延展承诺方案，是指敌手在截获对于一个秘密消息的承诺后，它也对某个消息进行承诺，但是敌手能够使得两个消息相关的能力，与敌手截获原承诺与否是无关的。关于打开的非延展承诺，是指敌手在看到原承诺打开后，它也能打开自己先前所作的承诺，但是敌手使得打开的两个消息产生关联的能力，与敌手截获原承诺及其打开信息是无关的。这两种非延展属性分别刻画了承诺方案在不同应用下应该满足的性质。我们研究的目标是从效率和困难性假设两方面着手，来分别考察上述两种延展性和承诺方案如何满足安全需求。一方面，我们希望基于较弱的假设来设计安全性高的方案;另外一方面，我们又希望基于较强的假设来设计效率高的方案。针对非延展零知识协议，我们希望在中间人攻击的情况下，尽可能保护验证者的利益，探讨如何在朴素模型下设计常数轮的零知识协议，其既能同时实现非延展性（即抵抗中间人攻击）又能实现无条件安全性（即协议是证明系统）。
　　此博士论文的主要结果包含以下部分:
　　1.抗中间人攻击的统计隐藏承诺方案的设计与分析。我们首次基于单向函数存在性假设，构造出了关于打开的非延展统计隐藏承诺方案。实际上，从另外一个角度来看，我们是将任意一个拥有非交互式打开阶段的统计隐藏承诺方案无条件转换成非延展统计隐藏承诺方案。根据Impagliazzo和Luby(FOCS'89)的结果，统计隐藏承诺方案可以推出单向函数存在性假设，因此我们的结果也是紧的，即困难问题假设是最弱的。另外我们的证明仅仅用到了黑盒技术。相比我们的工作，已有的研究成果或者基于更强的困难问题假设（比如抗碰撞哈希函数存在性），或者借助于非黑盒证明技术（通信效率较低）。
　　2.抗并发中间人攻击的统计隐藏承诺方案的设计与分析。我们给出了一种模块化的构造方法，来设计并发非延展统计隐藏承诺方案。我们的承诺方案基于一个一般的统计隐藏承诺方案，以及针对NP语言类的并发非延展零知识协议。此方法在朴素模型下有效，即不需要任何设置假设。另外，安全性证明仅用到黑盒证明技术。相比来说，现有的研究成果都需要借助于一些初始设置假设，比如共享字符串模型、公钥注册模型或者纯公钥模型等。这些模型均需要假设存在可信第三方或者存在全体参与方可访问的可信目录等，但是有时这些假设在实际中比较难得到满足，进而限制了其的应用范围。
　　3.抗中间人攻击的统计绑定承诺方案的设计与分析。我们在朴素模型下构造出了一个统计绑定承诺方案，此方案既是关于承诺并发非延展的，也是关于打开并发非延展的。我们的工作是对Ostrovsky、Persiano和Visconti(TCC'09)工作的补充，他们只能实现计算绑定性。针对一些应用场景，尤其是接收者的安全性更需要得到保障时，我们的方案更能满足安全需求。我们的方案困难问题假设是存在一族无爪置换函数，轮复杂度是常数。另外方案安全性证明用到了非黑盒证明技术，而且方案满足（更强安全性的）基于模拟的延展性定义。
　　4.抗中间人攻击的交互式证明协议的设计与分析。我们考察交互式证明协议在复杂环境下比如互联网中运行时，能否即抵抗中间人攻击又实现无条件可靠性，如此即使是拥有无穷能力的敌手也不能够向诚实验证者证明一个假的声明。根据以上两个需求，首先我们假设存在一族无爪置换函数，针对NP语言类构造出了常数轮的1-多并发非延展零知识证明（而非论证）系统。接着假设存在一族无爪置换函数，针对NP语言类构造出了常数轮的并发非延展证据不可区分证明系统。和此前的工作相比，我们的两个协议都是工作在朴素模型下，具有常数轮复杂度，而且能够同时抵抗非平凡的并发中间人攻击，以及抵抗拥有无穷能力的恶意证明者。

目录

声明

摘要

插图索引

主要术语中英文对照表

第一章 绪论

1．1 承诺方案

1．2 零知识协议

1．3 各种设置假设

1．4 承诺方案研究进展

1．4．1 统计绑定承诺

1．4．2 统计隐藏承诺

1．4．3 非延展承诺

1．5 非延展零知识研究进展

1．6 本文贡献

1．7 本文组织

第二章 预备知识

2．1 基本符号

2．2 基本密码学原语

2．3 承诺方案

2．3．1 统计隐藏承诺

2．3．2 统计绑定承诺

2．3．3 不同模型下承诺方案转换

2．3．4 为何会出现延展性问题

2．3．5 基于标签的非延展性定义

2．3．6 基于交互副本的非延展性定义

2．3．7 延展性定义比较

2．4 交互式协议

2．4．1 交互式证明系统

2．4．2 零知识协议

2．4．3 知识证明协议

2．4．4 证据不可区分

2．4．5 非延展零知识

2．5 黑盒与非黑盒证明技术

第三章 基于单向函数的非延展统计隐藏承诺方案

3．1 引言

3．1．1 相关工作

3．1．2 我们的结果

3．2 非延展统计隐藏承诺方案

3．2．1 基于标签证据不可区分证明

3．2．2 安全点

3．2．3 承诺方案构造

3．3 基于交互副本的非延展统计隐藏承诺方案

第四章 并发非延展统计隐藏承诺

4．1 引言

4．1．1 我们的结果

4．2 方案构造

4．3 总结

第五章 常数轮的并发非延展统计绑定承诺和解承诺

5．1 引言

5．1．1 我们的结果

5．2 常数轮并发非延展统计绑定承诺方案

5．2．1 并发非延展性

5．3 总结

第六章 关于常数轮并发非延展证明系统

6．1 引言

6．1．1 我们的结果

6．2 基本工具

6．2．1 并发非延展证据不可区分证明系统

6．3 常数轮1-多并发非延展零知识证明系统

6．4 常数轮并发非延展证据不可区分证明

第七章 全文总结和展望

参考文献

致谢

攻读博士学位期间论文目录

投稿中论文目录

参与项目