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