向量等分量数的两方保密计算及推广应用

安全多方计算是近年来国际密码学界的研究热点.安全向量计算作为安全多方计算研究的重要内容,也是解决许多实际安全计算问题的基本工具.在科学研究中很多研究对象都可以用向量来刻画,并通过对这些向量进行各种计算从而得到所需结果,这也使安全向量计算在电子商务推荐、保密的分类、保密聚类等研究中得到了广泛应用.本文主要研究向量等分量数计算问题,即保密计算两个向量有多少个对应分量相等,这个问题的研究对于安全多方计算和隐私保护有重要的理论与实际意义.首先设计编码方法对保密向量进行编码,并结合具有加法同态性的Paillier加密方案,针对数据范围有限制和无限制两种不同情形分别设计了高效的保密计算协议,应用模拟范例严格证明了协议的安全性.作为向量等分量数保密计算协议的应用,进一步研究了向量等分量数阈值判定问题和向量优势统计问题的解决方案.并以所设计的协议为基础解决了多个点与区间(或集合)关系判定问题和字符串模式匹配等实际应用问题.复杂性分析和实验测试都表明本文协议是高效和实用的.

Privately Computing Number of Equal Components of Two Private Vectors and Its Applications

Secure multiparty computation(SMC) is a hot research topic in recent years in the international cryptographic community. Secure multiparty computation of vectors is an important problem of SMC and is a basic tool for constructing many SMC protocols. In scientific research,many objects can be described by vectors, and we can do various computations of those vectors.Therefore secure vector computation can be widely applied to private e-commerce recommendation,private classification, private clustering, and so on. This paper focuses on the problem of privately computing how many corresponding components of two vectors are equal(VCE), which has important theoretical and practical significance for SMC and privacy-preserving. In this paper, an encoding scheme is designed to encode the private vectors and the additively homomorphic property of Paillier cryptosystem is used to privately compute how many corresponding components of two vectors are equal. Two efficient protocols are designed for two cases, in one case, the value range of the components of private vectors is known, and in the other case, the value range is not known. By using the wellaccepted simulation paradigm, it is proved that these two protocols are secure in the semi-honest model. As applications of these two protocols, it is shown how to apply them to privately compute whether the number of equal components of two vectors is larger than some threshold, and how to privately solve the vector dominance statistics problem under a threshold. Based on these protocols,the problems of privately determining the relationship between multiple points and multiple intervals and privately determining whether a string is a substring of another string are solved. Theoretical analysis and experiment show that the designed protocols are efficient and practical.