中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 中科院软件所  > 中科院软件所
题名:
安全多方计算中秘密匹配问题的研究
作者: 李荣花
答辩日期: 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
英文摘要: Secure multiparty computation is a research field developed in the recent years, which is an important branch research field of cryptography. Many fundamental tasks in cryptography, like authentication, key exchange, signature, etc. can be resolved by use of secure protocols for multiparty computation. Private matching problem is a special sort of secure multiparty computation problem, which can be applied in electronic commerce, privacy-preserving data mining. The main problems considered in this paper include integer comparison problems and private set perations, which are all called private matching problem. We aim to design secure and efficient protocols to solve these problems. Specially, we consider the millionaires' problem (also known as the greater than problem), the socialist millionaires' problem (also known as private equality test), the decisional set inclusion problem and multiparty set intersection etc. problems. The main contributions are the following. Three protocols for integer comparison are analyzed, including Cachin's protocol for greater than problem and Qin et al.'s protocols for integer comparison. A flaw is found in the security proofs of these protocols, and a correct proof is given. A new problem is proposed, called co-operative private equality test, where two parties each with a secret input, compare their secrets under the help of a third party, such that only the comparison results is known to the three parties. Based on homomorphic encryption scheme, a protocol is proposed for the new problem. The security of the protocol is proved. The protocol needs 3 rounds of communication, and the computation and communication costs are linear in the length of the inputs. Based on this protocol a protocol for the equality test problem is constructed, which has the same efficiency as the most efficient protocol for the problem. Based on Lin and Tzeng's protocol for the millionaires' problem, a fair protocol for the same problem is constructed by introducing a (malicious) third party. The security of the protocol is proved. The protocol needs 4 rounds of communication, the computation and communication costs are linear in the length of the inputs. Modifications of the protocols for set disjointness are proposed. The modified protocols solve the decisional set inclusion problem. The proposed protocols can be based on homomorphic encryption and superposed encryption schemes, and have different levels of security and efficiency. An unconditionally secure protocol for multi-party set intersection is proposed based on verifiable secret sharing scheme, which is commonly used in the general protocols in the information-theoretic model, and the technique of representing sets as polynomials, which is commonly used in the protocols for set operation problems in the cryptographic model. The security of the proposed protocol is proved. A new private set operation is proposed: $n$ parties $P_1$, ..., $P_n$ have secret sets $S_1$, ..., $S_n$ respectively. Let $P_n$ be the leader and $t < n-1$ be a threshold value. For each element $w_j \in S_n$, if $w_j$ appears $t'> t$ times in $S_1$, ..., $S_{n-1}$, then $P_n$ learns whether $w_j \in S_i$ or not, otherwise, $P_n$ learns nothing, $i=1, ..., n-1$. By ``private" we mean that the leader cannot learn more than what is implied by the result and its secret set, and other parties learn nothing. In the semi-honest model, for the threshold value $\frac{2(n-1)}{3} < t
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/7584
Appears in Collections:中科院软件所

Files in This Item:
File Name/ File Size Content Type Version Access License
10001_200318015001010李荣花_paper.pdf(2086KB)----限制开放-- 联系获取全文

Recommended Citation:
李荣花. 安全多方计算中秘密匹配问题的研究[D]. 软件研究所. 中国科学院软件研究所. 2008-01-14.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[李荣花]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[李荣花]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace