一个抗隐蔽敌手的n选t不经意传输框架

摘要

不经意传输(oblivious transfer,OT)可能是密码学中最重要的原语。从理论的角度看,它是一个基础性的原语,因为如果可以安全地实现OT协议,那么就可以安全地实现其它一切密码学协议。从应用的角度看,它本身就是安全数据库查找和电子商务领域中的重要工具。
　　通常密码学假定敌手是恶意的。恶意敌手是个一有机会就作弊的狂徒,不会在乎利害得失。这样的假设太过悲观,设计出的协议往往开销高昂。本文采纳Aumann和Lindell的观点,假定敌手是隐蔽的。隐蔽敌手会顾虑抓捕后的惩罚而不敢肆意作弊。抗隐蔽敌手的安全并不能去除敌手所有成功的作弊。尽管如此,但是它可以保证,一旦敌手作弊了,诚实用户可以以某个满意的概率检测到这一点。
　　n选t不经意传输(t-out-of-n oblivious transfer,OTnt)可描述如下。发送者拥有n个私有值m1、m2、……、mn。接收者拥有t个私有的索引i1、i2、……、it。接收者希望得到值mi1、mi2、……、mit且不向敌手泄露它得到了哪些值;发送者希望接收者最多只能获取t个值,而不是超过t个值。
　　我们提出了一个新的光滑投影哈希(smooth projective hashing,SPH)变种来构造OTnt框架。新的SPH变种与现有SPH及其变种的最大区别是,它既给光滑实例提供见证,又给投影实例提供见证。它解决了两个问题。其一,它使得SPH得以处理通用的OTnt问题而不只是OT21问题。其二,它能够为使用SPH的OTnt框架带来遵循理想世界/现实世界仿真范式的安全性证明。
　　在我们之前,学术界有个传说,在有错学习难假设下实现SPH存在着技术上的困难。我们的解决思路是,将负责计算哈希值的算法视为一个公钥加密算法,而负责计算投影值的算法被视为一个解密算法。自然而然,我们可以将(公钥,私钥)对视为(实例,见证)对。在有错学习难假设下实现SPH新变种,意味着我们为SPH开创了一个新的实例。此外,像现有的SPH可以在判定Diffie-Hellman假设,判定N阶剩余假设,判定平方剩余假设实现那样,我们也在这些难题假设下一一实现了新的SPH变种。
　　使用新的SPH变种,我们构造了一个抗隐蔽敌手的、安全性证明遵循理想世界/现实世界仿真范式的OTnt框架。我们的框架很实用,它有如下特点。
　　它可以在广泛的数学难题假设下实例化。我们证明框架可以在判定Diffie-Hellman假设,判定N阶剩余假设,判定平方剩余假设和有错学习假设下分别实现。
　　它可以在现实生活中广泛使用。这是因为它工作在平凡模型中,不需要可信的初始装置。
　　它非常高效。它只需要4轮通信。其主要的计算开销是发送者的n个公钥加密运算和接收者的(K g)t个公钥解密运算。与现在已知抵抗隐蔽敌手的,或者抵抗恶意敌手的协议相比,我们的框架,通常更高效。其中,K,g是满足K>g的正整数。
　　当敌手成功贿赂发送者时,敌手的作弊能以100％的概率被诚实的接收者检测到。当敌手成功贿赂接收者时,敌手的作弊能以1-1/(K K-g)的概率被诚实的发送者检测到。
　　框架只使用了一个密码学原语,即SPH新变种,这意味着我们将OTnt规约到了SPH。在我们之前,唯一已知的规约就是Halevi和Tauman Kalai所给出的OT21到SPH的规约。然而,该规约的安全性证明无法遵循理想世界/现实世界仿真范式。
　　安全性证明是件极为复杂的事情。为了简化证明,我们给出了几个基于多次取样的计算不可区分的引理。这些引理大大简化了我们的安全性证明。我们相信它们在其它场合中的安全性证明中也会这样有用。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 研究背景及其意义

1.2 国内外研究概况

1.3 研究内容

1.4 本文组织结构

2 技术基础

2.1 基本记号和定义

2.2 n选t不经意传输的功能

2.3 隐蔽敌手

2.4 理想/现实世界范式

2.5 安全定义

2.6 小结

3 抽象工具：一种新的光滑可投影哈希

3.1 背景

3.2 新光滑可投影哈希的定义

3.3 一个光滑可投影哈希实例

3.4 新旧光滑可投影哈希的不同

3.5 小结

4 框架的构造

4.1 框架描述

4.2 正确性验证

4.3 小结

5 框架的安全性证明

5.1 直觉的视角

5.2 形式化的安全证明

5.3 小结

6 框架的效率及其与相关工作的比较

6.1 框架的效率

6.2 与国内外相关工作的比较

6.3 小结

7 实例化框架的第一步：简化光滑可投影哈希家族的

7.1 基础哈希家族

7.2 规约到基础哈希家族

7.3 小结

8 实例化框架的第二步：实例化基础哈希家族

8.1 在判定Diffie-Hellman假设下的实例化

8.2 在有错学习假设下的实例化

8.3 在判定平方剩余假设下的实例化

8.4 在判定N阶剩余假设下的实例化

8.5 小结

9 总结与展望

9.1 全文总结

9.2 工作展望

致谢

参考文献

附录1 攻读学位期间发表的学术论文

附录2 攻读博士期间参加的科研项目、学术活动及获奖情况

附录3 密码学家推荐信