三方不经意多项式求值协议的设计与分析

摘要

安全多方计算协议能够在没有可信第三方的情况下完成计算任务，并保护参与者的隐私，是近年来密码学研究的重要内容，有着重要的应用价值和研究意义。不经意传输协议是安全多方协议的一个基础工具，已经有了较为成熟和深入的研究，利用不经意传输协议能够构造功能更强大的更复杂的密码协议。本文针对多方计算中的隐私保护问题，在不经意传输协议的基础上，提出了三方不经意多项式求值协议。
　　协议拥有三个参与者，分别为一个发送者和两个接收者。发送者拥有一个二元多项式P(x，y），两个接收者分别拥有α和β。完成如下目标:接收者得到P(α，β)的值，但无法得到关于多项式P的任何信息，而发送者无法得到关于α和β的任何信息。本文首先提出了对半诚实参与者能够保证安全的三方多项式求值协议，然后在该协议的基础上进行改进，提出了对恶意参与者也能保证安全的协议。第一个协议拥有更好的效率，而第二个协议拥有更高的安全性。两个协议在实际应用中均有相应的应用场景。通过严格的理论分析，证明了协议的正确性和安全性。之后，给出了协议的应用场景，并举例说明了如何使用本文协议在保护隐私的条件下计算两方的Hamming距离。最后，详细分析了协议的效率，并通过实验证明了协议的正确性和可行性。
　　本文协议通过使用Diffie-Hellman密钥交换协议和任意一种安全的不经意传输协议来实现，具有较好的适应性，扩展了不经意传输协议的使用范围，具有较高的实用价值，并为安全多方计算的实现提供了一种新的途径。

目录

声明

摘要

第一章 绪论

1．1 研究背景

1．2 研究内容

1．3 论文组织结构

第二章 相关知识

2．1 安全多方计算

2．2 Diffie-Hellman密钥交换协议

2．2．1 离散对数

2．2．2 离散对数假设

2．2．3 计算Diffie-Hellman假设

2．2．4 选择目标计算Diffie-Hellman假设

2．3 不经意传输

2．4 不经意传输协议的具体实现

2．4．1 2取1OT协议

2．4．2 n取1OT协议

2．4．3 n取kOT协议

2．4．4 适应性n取kOT协议

2．5 有限域与多项式插值法

2．5．1 有限域相关定义

2．5．2 有限域中的多项式插值法

2．5．3 存在性和唯一性证明

2．5．4 有限域Lagrange插值法

2．5．5 有限域Newton插值法

第三章 协议的定义与模型

3．1 相关定义

3．1．1 三方OPE协议的定义

3．1．2 OT协议的定义

3．1．3 计算复杂性

3．1．4 难解性假设

3．1．5 协议的正确性

3．1．6 协议的安全性

3．2 协议模型

3．2．1 通信模型

3．2．2 模型范例

3．2．3 参与者模型

第四章 协议的实现与分析

4．1 对半诚实参与者安全的三方OPE协议

4．1．1 抵抗半诚实敌人协议的实现

4．1．2 协议的正确性

4．1．3 接收者的安全

4．1．4 发送者的安全

4．2 对恶意参与者安全的三方OPE协议

4．2．1 抵抗半诚实敌人协议的安全性改进

4．2．2 抵抗恶意敌人协议的实现

4．2．3 协议的正确性

4．2．4 接收者的安全

4．2．5 发送者的安全

4．2．6 共谋

4．3 协议的效率分析

4．3．1 协议的基本执行步骤分析

4．3．2 Diffie-Hellman协议的复杂度

4．3．3 OT协议的复杂度

4．3．4 伪随机数生成的复杂度

4．3．5 多项式插值的复杂度

4．3．6 模幂计算的复杂度

4．3．7 协议复杂度总结

4．4 安全参数对效率的影响

第五章 协议的应用与实验

5．1 应用场景

5．1．1 在多元多项式中的应用

5．1．2 保护隐私的两方Hamming距离计算

5．1．3 其他应用

5．2 实验

5．2．1 抵抗半诚实敌人的协议实验

5．2．2 抵抗恶意敌人的协议实验

5．2．3 Hamming距离计算协议实验

第六章 总结与展望

6．1 总结

6．2 展望

参考文献

发表论文和参加科研情况说明

致谢