安全多方计算中秘密匹配问题的研究
文献类型：学位论文
| 作者 | 李荣花 |
| 学位类别 | 博士 |
| 答辩日期 | 2008-01-14 |
| 授予单位 | 中国科学院软件研究所 |
| 授予地点 | 软件研究所 |
| 关键词 | 安全多方计算 秘密匹配 秘密数值比较 秘密集合运算 |
| 其他题名 | Private Matching in Secure Multi-Party Computation |
| 中文摘要 | 安全多方计算是近年来发展起来的一个研究方向，是密码学的重要分支，许多基础的密码学问题比如认证、密钥交换、签名等都可以用安全多方计算协议来解决。而秘密匹配问题是安全多方计算中的一类具体问题，在电子交易、秘密数据挖掘等方面有着重要的应用价值，对该问题的研究也倍受重视。
本文主要研究秘密匹配问题中的数值比较问题和集合运算问题，设计解决这两类秘密匹配问题的安全计算协议。本文研究的数值比较问题包括相等比较和大小比较，本文研究的集合运算问题包括判定性集合包含关系问题和集合交集等问题，旨在设计有效的数值比较协议和集合运算协议。本文主要研究成果和创新点：
分析了Cachin提出的比较大小协议以及秦静等提出的两个数值比较协议，发现这些协议的安全性证明有不足之处，并给出了正确的安全性证明。
提出了联合秘密相等比较问题。两个成员各自有一个秘密输入，在第三方参与的情况下进行相等比较，两个成员和第三方都能获得比较结果。基于同态加密方案，提出了一个联合秘密相等比较协议，并证明了协议的安全性。协议需要3轮通信，其计算复杂度和通信复杂度是输入长度的线性函数。改造了联合秘密相等协议，构造了一个比较相等协议，协议与已有最高效的协议具有相同的效率。
借鉴公平相等比较协议的思想，在Lin和Tzeng提出的比较大小协议的基础上引入一个半可信第三方，构造了一个公平的比较大小协议，并证明了协议的安全性。协议需要4轮通信，其计算复杂度和消息复杂度是输入长度的线性函数。
改造了一个判断集合交集是否为空的协议使之适用于判断集合是否具有包含关系的问题，分别基于同态加密和叠加密，构造了两个具有不同效率的判断集合包含关系的协议。
将信息论模型中协议常用的可验证秘密分享技术与密码学模型中求集合交集的思想结合，构造了一个无条件安全的多方集合交集协议，并分析了协议的效率和安全性。
提出了一个新的集合秘密运算问题。$n$个成员$P_1$，...，
$P_n$，每人有一个秘密的集合，分别记作$S_1$，...，$S_n$。假设$P_n$是成员的领导者，$t < n-1$是一个阈值。对于每一个元素$w_j \in S_n$，如果$w_j$在$S_1$，...，$S_{n-1}$这$n-1$个集合中出现了$t'> t$次，那么$P_n$就得知$S_i$中是否包含$w_j$，否则，$P_n$不能得知任何信息，$i=1$，...，$n-1$。即除了计算结果和其秘密集合所隐含的信息外，领导者$P_n$不能获得任何关于其他成员秘密集合的有用信息。在半诚实模型中，对于阈值$\frac{2(n-1)}{3} < t |
| 语种 | 中文 |
| 公开日期 | 2011-03-17 |
| 页码 | 113 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/7584]  |
| 专题 | 软件研究所_中科院软件所_中科院软件所 |
| 推荐引用方式 GB/T 7714 | 李荣花. 安全多方计算中秘密匹配问题的研究[D]. 软件研究所. 中国科学院软件研究所. 2008. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。