Secure computation with horizontally partitioned data using adaptive regression splines

When several data owners possess data on different records but the same variables, known as horizontally partitioned data, the owners can improve statistical inferences by sharing their data with each other. Often, however, the owners are unwilling or unable to share because the data are confidential or proprietary. Secure computation protocols enable the owners to compute parameter estimates for some statistical models, including linear regressions, without sharing individual records’ data. A drawback to these techniques is that the model must be specified in advance of initiating the protocol, and the usual exploratory strategies for determining good-fitting models have limited usefulness since the individual records are not shared. In this paper, we present a protocol for secure adaptive regression splines that allows for flexible, semi-automatic regression modeling. This reduces the risk of model mis-specification inherent in secure computation settings. We illustrate the protocol with air pollution data.     

分布式环境下保持隐私的聚类挖掘算法

隐私保护是数据挖掘中一个重要的研究方向。针对如何在不共享精确数据的条件下,应用k-平均聚类算法从数据中发现有意义知识的问题,提出了一种基于安全多方计算的算法。算法利用半可信第三方参与下的安全求平均值协议,实现了在分布式数据中进行k-平均聚类挖掘时隐私保护的要求。实验表明算法能很好的隐藏数据,保护隐私信息,且对聚类的结果没有影响。     

分布式环境下保持隐私的关联规则挖掘算法

保持隐私是未来数据挖掘领域的焦点问题之一,如何在不共享精确数据的条件下,获取准确的数据关系是保持隐私的数据挖掘的首要任务。该文介绍了分布式环境下保持隐私的数据挖掘的基本问题和措施,研究了一种基于向量点积的关联规则挖掘算法,给出了一种安全的向量点积协议。对于垂直划分的分布式数据库,该协议既可用于搜索频繁项集,又能保持各方数据的隐私。     

基于隐私保护的数据相似性度量

数据对象间的相似性度量是数据挖掘中一个重要的内容。针对如何在不共享精确数据的条件下,安全计算数据对象间的相似性问题,提出了几种基于安全多方计算协议的算法。算法很好的隐藏数据,保护隐私信息,且对相似性计算的结果没有影响。     

A Secure Multi-party Data Federation System

In the era of big data, data is of great value as an essential factor in production. It is of great significance to implement its analysis, mining, and utilization of large-scale data via data sharing. However, due to the heterogeneous dispersion of data and increasingly rigorous privacy protection regulations, data owners cannot arbitrarily share data, and thus data owners are turned into data silos. Since data federation can achieve collaborative queries while preserving the privacy of data silos, we present in this paper a secure multi-party relational data federation system based on the idea of federated computation that ``data stays, computation moves.'' The system is compatible with a variety of relational databases and can shield users from the heterogeneity of the underlying data from multiple data owners. On the basis of secret sharing, the system implements the secure multi-party operator library supporting the secure multi-party basic operations, and the resulting reconstruction process of operators is optimized with higher execution efficiency. On this basis, the system supports query operations such as Summation (SUM), Averaging (AVG), Minimization/Maximization (MIN/MAX), equi-join, and $\theta $-join and makes full use of multi-party features to reduce data interactions among data owners and security overhead, thus effectively supporting efficient data sharing. Finally, experiments are conducted on the benchmark dataset TPC-H. The experimental results show that the system can support more data owners than the current data federation systems SMCQL and Conclave and has higher execution efficiency in a variety of query operations, exceeding the existing systems by as much as 3.75 times.     

Formal anonymity models for efficient privacy-preserving joins

Organizations, such as federally-funded medical research centers, must share de-identified data on their consumers to publicly accessible repositories to adhere to regulatory requirements. Many repositories are managed by third-parties and it is often unknown if records received from disparate organizations correspond to the same individual. Failure to resolve this issue can lead to biased (e.g., double counting of identical records) and underpowered (e.g., unlinked records of different data types) investigations. In this paper, we present a secure multiparty computation protocol that enables record joins via consumers’ encrypted identifiers. Our solution is more practical than prior secure join models in that data holders need to interact with the third party one time per data submission. Though technically feasible, the speed of the basic protocol scales quadratically with the number of records. Thus, we introduce an extended version of our protocol in which data holders append k-anonymous features of their consumers to their encrypted submissions. These features facilitate a more efficient join computation, while providing a formal guarantee that each record is linkable to no less than k individuals in the union of all organizations’ consumers. Beyond a theoretical treatment of the problem, we provide an extensive experimental investigation with data derived from the US Census to illustrate the significant gains in efficiency such an approach can achieve.     

保护隐私的曼哈顿距离计算及其推广应用

安全多方计算是信息时代保护隐私和信息安全的一项关键技术.安全多方科学计算是安全多方计算十分重要的组成部分,目前已经有许多安全多方科学计算问题的解决方案,但还有更多的问题值得人们去研究.关于曼哈顿距离的安全多方计算问题目前研究的结果很少,构造曼哈顿距离的安全计算协议在密码学中有着重要的理论意义,作为基础协议能够广泛应用于其他安全多方计算协议的构造,比如保密计算两点间路径问题,保密判定点与区间以及点与点集的关系问题,以及向量相似度的保密计算都可以归约到曼哈顿距离的安全多方计算问题.本文应用加密选择技巧与一种新的编码方法相结合,以Paillier加密算法为基础,对于不同的情形(无全集限制或有全集限制)设计两数之差绝对值的高效保密计算协议.并以此为基础,设计出两种不同情形下保密计算曼哈顿距离的协议.本文证明了在半诚实模型下这些协议是安全的,并通过模拟实验来测试协议的具体执行时间,理论分析和仿真结果表明本文方案是简单易行的.最后,文中给出实例阐明本文协议在理论以及实际中的广泛应用.     

Secure computation of hidden Markov models and secure floating-point arithmetic in the malicious model

Hidden Markov model (HMM) is a popular statistical tool with a large number of applications in pattern recognition. In some of these applications, such as speaker recognition, the computation involves personal data that can identify individuals and must be protected. We thus treat the problem of designing privacy-preserving techniques for HMM and companion Gaussian mixture model computation suitable for use in speaker recognition and other applications. We provide secure solutions for both two-party and multi-party computation models and both semi-honest and malicious settings. In the two-party setting, the server does not have access in the clear to either the user-based HMM or user input (i.e., current observations) and thus the computation is based on threshold homomorphic encryption, while the multi-party setting uses threshold linear secret sharing as the underlying data protection mechanism. All solutions use floating-point arithmetic, which allows us to achieve high accuracy and provable security guarantees, while maintaining reasonable performance. A substantial part of this work is dedicated to building secure protocols for floating-point operations in the two-party setting, which are of independent interest.     

Fuzzy trust evaluation and credibility development in multi-agent systems

E-commerce markets can increase their efficiency through the usage of intelligent agents which negotiate and execute contracts on behalf of their owners. The measurement and computation of trust to secure interactions between autonomous agents is crucial for the success of automated e-commerce markets. Building a knowledge sharing network among peer agents helps to overcome trust-related boundaries in an environment where least human intervention is desired. Nevertheless, a risk management model which allows individual customisation to meet the different security needs of agent–owners is vital.The calculation and measurement of trust in unsupervised virtual communities like multi-agent environments involves complex aspects such as credibility rating for opinions delivered by peer agents, or the assessment of past experiences with the peer node one wishes to interact with. The deployment of suitable algorithms and models imitating human reasoning can help to solve these problems.This paper proposes not only a customisable trust evaluation model based on fuzzy logic but also demonstrates the integration of post-interaction processes like business interaction reviews and credibility adjustment. Fuzzy logic provides a natural framework to deal with uncertainty and the tolerance of imprecise data inputs to fuzzy-based systems makes fuzzy reasoning especially attractive for the subjective tasks of trust evaluation, business-interaction review and credibility adjustment.     

公平理性委托计算协议

已存在的安全计算集合关系的协议大多基于公钥加密算法,因此很难再嵌入到带有属性关系的公钥加密或密文搜索中.针对该问题,本文给出了非加密方法安全计算集合包含关系和集合交集的2个协议.我们首先利用（n,n）秘密共享的思想分别将原来2个问题转化为集合相等问题.在此基础上,结合离散对数,构造了安全计算集合包含关系的协议1和集合交集的协议2.最后的分析显示：我们的方案没有使用任何公钥加密方法,在保持了较优通信复杂性的同时,便于作为一种子模块嵌入到带有集合操作关系的公钥加密体制或者密文搜索体制中,从而丰富这些方案的功能.     

面向多方安全的数据联邦系统

大数据时代,数据作为生产要素具有重要价值.因此,通过数据共享实现大规模数据的分析挖掘与利用具有重要意义.然而,近年来日益严格的隐私安全保护要求使得数据分散异质的多方之间不能任意共享数据,加剧了"数据孤岛"问题.数据联邦能让多数据拥有方在保护隐私的前提下完成联合查询.因此,基于"数据不动计算动"的联邦计算思想实现了一种多...     

Secure multi-party computation protocol for sequencing problem

In the field of multi-party computation,an important problem is how to construct an efficient and secure multi-party computation protocol for certain specific problems.In the present study,we make use of a secret sharing scheme to construct an efficient and secure multi-party computation protocol for sequencing problems.Our protocols are perfectly secure against both a passive adversary that can corrupt at most t (n-1)/2 participants, and an active adversary that can corrupt at most t < n/3 participants.The...     

基于茫然第三方的比较相同集合的计算实现

互不信任的个成员通过网络共同完成可靠的计算任务是可信计算的热点,我们借助茫然第三方,构建了安全多方求解相同集合的比较协议。该协议保证了计算过程中隐私数据的安全性,在社交网络、社会公共服务系统中应用前景广阔。     

On private Hamming distance computation

Finding similarities between two datasets is an important task in many research areas, particularly those of data mining, information retrieval, cloud computing, and biometrics. However, maintaining data protection and privacy while enabling similarity measurements has become a priority for data owners in recent years. In this paper, we study the design of an efficient and secure protocol to facilitate the Hamming distance computation between two semi-honest parties (a client and a server). In our protocol design, both parties are constrained to ensure that no extra information will be revealed other than the computed result (privacy is protected) and further, the output of the protocol is according to the prescribed functionality (correctness is guaranteed). In order to achieve these requirements, we utilize a multiplicative homomorphic cryptosystem and include chaff data into the computation. Two experimental results in this paper demonstrate the performance of both the client and the server.     

Secure Hamming distance based record linkage with malicious adversaries

Record linkage aims at finding the matching records from two or multiple different databases. Many approximate string matching methods in privacy-preserving record linkage have been presented. In this paper, we study the problem of secure record linkage between two data files in the two-party computation setting. We note that two records are linked when all the Hamming distances between their attributes are smaller than some fixed thresholds. We firstly construct two efficient secure protocols for computing the powers of an encrypted value and implementing zero test on an encrypted value, then present an efficient protocol within constant rounds for computing the Hamming distance based record linkage in the presence of malicious adversaries by transferring these two protocols. We also discuss the extension of our protocol for settling the Levenshtein distance based record linkage problem.     

半诚实模型下关于安全多方求解交集问题的研究

特殊情形下的安全多方计算问题是目前密码学界研究的热点,特殊的安全多方计算协议的设计与分析自然成为当前人们致力研究的热门课题。数据库共享过程中,如何在不暴露各自数据集的前提下计算出交集？一直是我们感兴趣的问题,问题的解决对实现新型、安全、公平的数据共享有着重要的意义。在半诚实模型下我们基于计算不可区分概念以及交换加密的安全性假设,给出了一个用于求解交集的特殊安全双方计算协议。该协议具有公平性、安全性,并借助茫然第三方的参与,使协议简单有效。作为茫然第三方不知道最后结果及参与方的秘密,也不能与参与方串谋作弊。文中对协议的安全性进行了理论证明和分析。该协议在政府文件共享、医疗机构的合作研究、数据挖掘等领域中有着广阔的应用前景。     

外包数据库系统中隐私匹配与包含关系的安全计算协议

针对外包数据库系统中的隐私匹配问题,提出了基于分布式环境的安全计算协议(协议1):数据所有者采用Mignotte秘密共享方案将数据集外包,用户与第三方服务提供者交互,通过加法同态加密与秘密重构构造判别式,以判别式的值是否为零来判断用户的数据集的元素是否属于数据所有者的数据集,最终实现隐私匹配。此外,在协议1的基础上还提出了一种判断用户数据集是否包含于数据所有者的数据集的协议(协议2)。在半诚实模型下,采用基于模拟器的方法证明了两个协议的安全性。     

分布式数据集极差与极值和的保密计算

随着信息通信技术的不断突破与发展,信息获取变得非常便利.与此同时,隐私信息也更容易泄露.将智能领域与安全多方计算技术相结合,有望解决隐私保护问题.目前,安全多方计算已经解决了许多不同隐私保护问题,但还有更多的问题等待人们去解决.对于极差、极值和的安全多方计算问题目前研究的结果很少,极差、极值和作为统计学的常用工具在实际中有广泛的应用,研究极差、极值和的保密计算具有重要意义.提出新编码方法,用新编码方法解决了两种不同的安全多方计算问题,一是极差的保密计算问题,二是极值和的保密计算问题.新编码方法结合Lifted ElGamal门限密码系统,设计多方参与、每方拥有一个数据场景下分布式隐私数据集极差的保密计算协议;将新编码方法稍作改动解决相同场景下保密计算极值和的问题.以此为基础,对新编码方法进一步修改,结合Paillier密码系统设计了两方参与、每方拥有多个数据情况下分布式隐私数据集极差、极值和的保密计算协议.用模拟范例方法证明协议在半诚实模型下的安全性.最后,用模拟实验测试协议的复杂性.效率分析和实验结果表明所提协议简单高效,可广泛用于实际应用中,是解决其他很多安全多方计算问题的重要工具...     

适应性选择密文安全的可公开验证加密方案

在密钥托管、电子公平交易、可公开分享和安全多方计算中,对可公开验证加密有广泛的应用需求,但是已有的可公开验证加密方案或者是选择明文安全的,或者是在随机预言机模下是选择密文安全的,显然不满足诸多复杂应用环境的安全需求。在对已有可公开验证方案的分析和现实应用需求的基础上,结合CS加密方案,利用非交互性零知识证明协议提出了一个新的可公开验证的加密方案,新方案使得除发送方和接收方外的任何第三方都可以验证密文的有效性,且不会泄露消息的其他任何信息。最后,相对于随机预言机模型,在标准模型下证明了新方案是适应性选择密文安全的。     

A Secure Scalar Product Protocol Against Malicious Adversaries

A secure scalar product protocol is a type of specific secure multi-party computation problem.Using this kind of protocol,two involved parties are able to jointly compute the scalar product of their private vectors,but no party will reveal any information about his/her private vector to another one.The secure scalar product protocol is of great importance in many privacy-preserving applications such as privacy-preserving data mining,privacy-preserving cooperative statistical analysis,and privacy-preserving geometry computation.In this paper,we give an efficient and secure scalar product protocol in the presence of malicious adversaries based on two important tools:the proof of knowledge of a discrete logarithm and the verifiable encryption.The security of the new protocol is proved under the standard simulation-based definitions.Compared with the existing schemes,our scheme offers higher efficiency because of avoiding inefficient cut-and-choose proofs.