<Emphasis Type="Italic">t</Emphasis>-Private and <Emphasis Type="Italic">t</Emphasis>-Secure Auctions

In most of the auction systems the values of bids are known to the auctioneer. This allows him to manipulate the outcome of the auction. Hence, one might be interested in hiding these values. Some cryptographically secure protocols for electronic auctions have been presented in the last decade. Our work extends these protocols in several ways. On the basis of garbled circuits, i.e., encrypted circuits, we present protocols for sealed-bid auctions that fulfill the following requirements： 1） protocols are information-theoretically t-private for honest but curious parties; 2） the number of bits that can be learned by malicious adversaries is bounded by the output length of the auction; 3） the computational requirements for participating parties are very low： only random bit choices and bitwise computation of the XOR-function are necessary. Note that one can distinguish between the protocol that generates a garbled circuit for an auction and the protocol to evaluate the auction. In this paper we address both problems. We will present a t-private protocol for the construction of a garbled circuit that reaches the lower bound of 2t ＋ 1 parties, and Finally, we address the problem of bid changes in an auction. a more randomness efficient protocol for （t ＋ 1）^2 parties     

A cryptographically t‐private auction system

We present a cryptographically t‐private protocol for electronic auctions whose low resource demands make it viable for practical use. Our construction is based on Yao's garbled circuits and pseudorandom number generators (PRNGs). Our protocol involves a field of (t + 1)² parties for the generation of the garbled circuit and permits an arbitrary large number of bidders. The computational requirements are low: Only t + 1 parties of the field have to use the PRNG, the remaining parties execute only primitive computations (XOR, permutations and sharing). The bidders have to stay active for one round of communication, independent of each other. Each bidder has to compute only t + 1 XOR‐operations. We present an implementation and evaluate its performance. The observed running time of our protocol is linear in the size of the auction circuit and the number of bidders and, as expected, grows quadratically in the parameter t. Copyright © 2010 John Wiley & Sons, Ltd.     

实用安全多方计算协议关键技术研究进展

在安全多方计算协议中,2个或多个持有秘密输入的参与方想要利用他们的输入来计算某个联合函数,并达到隐私性、正确性及输入无关性等安全要求.安全多方计算既是安全协议的一般性基础研究,也在许多应用领域(比如电子投票、网上合同签署、隐私信息检索等)有明确应用背景,其研究为密码学多个领域提供了核心工具.近年来,安全多方计算协议的研究,特别是在实用化技术方面取得了快速发展,协议实用化成为安全多方计算一个新的关注点.介绍了实用化安全多方计算协议研究的主要进展和成果,并重点介绍安全多方计算实用化的3个支撑性重要技术,包括混乱电路优化、剪切-选择技术及不经意传输扩展技术,这些技术在不同的方面显著提高了安全多方计算协议的效率.     

安全多方计算理论研究综述

文章针对安全多方计算理论的广泛应用价值和研究热潮,综述了安全多方计算理论的研究现状。在分析安全多方计算理论的数学模型、与密码学的关系、应用领域和基础协议的基础上,着重梳理了安全多方计算理论的研究进展,进一步探讨了研究热点和发展趋势。     

一种高效的私有信息检索方案

私有信息检索是一个重要的安全多方计算协议，是指参与查询的用户与数据库拥有者希望在各自的私有信息互不泄露的情况下完成查询操作，该问题在多个情报部门的合作计算领域有着广阔的应用前景．本文将密码学技术应用于预处理辅助随机服务器协议，提出了一个新的私有信息检索解决方案，该方案在保持传统PIR协议通信复杂度不变的情况下，有效地降低了计算复杂度，可以高效应用于文件数据检索．对方案的安全性，计算复杂性和通信复杂性进行了分析．     

Secure Two-Party Point-Circle Inclusion Problem

Privacy-preserving computational geometry is a special secure multi-party computation and has many applications. Previous protocols for determining whether a point is inside a circle are not secure enough. We present a two-round protocol for computing the distance between two private points and develop a more efficient protocol for the point-circle inclusion problem based on the distance protocol. In comparison with previous solutions, our protocol not only is more secure but also reduces the number of communication rounds and the number of modular multiplications significantly.     

基于Cut-and-Choose技术的安全多方计算

Cut-and-Choose技术是密码学中一种被广泛使用的密码学工具,对安全多方计算协议的设计起着重要的作用.其主要思想是一方在协议中构造多份混淆电路,另一方要求打开其中一部分电路进行检查,若检查通过则计算剩余的电路,决定电路的最终输出.在早期工作中,Cut-and-Choose技术主要应用于恶意模型下的安全两方计算,并由此产生了许多优秀的工作.尽管该技术在隐蔽安全模型中的工作也很早提出,但在当时并没有引起太多的关注.近年来,随着学者对于隐蔽敌手的深入研究,Cut-and-Choose技术以及基于该技术的思想也开始被用于实现公开可验证的隐蔽安全协议,涌现出一些代表性的工作.首先介绍了Cut-and-Choose技术在恶意安全模型和隐蔽安全模型中的研究进展;其次重点介绍其应用于公开可验证隐蔽安全模型中的研究成果;最后通过对该领域的研究成果进行详细的总结与分析,并指出后续可能的发展方向.     

一个保护私有信息的线段与椭圆相交判定协议

保护隐私的计算几何是一类特殊的安全多方计算问题。保密路径判定作为一种特殊的保密隐私的几何计算问题,在军事、商业等领域具有重要的应用前景。设计了一个直线与椭圆的位置关系保密判定协议,基于该协议提出了线段与椭圆相交的保密判定协议,并给出协议的正确性、安全性和复杂性的分析。     

一种最小化安全多方计算任务的方法

安全多方计算(Secure multi-party computation, MPC)允许在不公开各参与方私有数据的情况下完成联合计算;然而,现有的计算任务往往涉及到多方海量数据集的分析与处理,使得MPC的实际可用性显著降低;提高MPC数据处理体量,是目前研究的主要方向之一;为提高MPC处理大规模数据的能力,将MPC算法与数据并行分析框架相结合,基于最小化多方计算任务的思想,提出安全多方计算效率优化技术;创建算法的有向无环图,标注MPC节点及非MPC节点,采用静态分析、查询重写转换和分区启发式等技术,最小化MPC计算量,提高计算的并发程度;以多方线性回归为例,讨论适应大数据分析的安全多方计算技术;实验结果表明提出的安全多方计算优化技术在确保计算精度的条件下能够显著降低计算耗时;算法提高了系统的效率,增强了MPC的实用能力。     

隐私保护集合交集计算技术研究综述

隐私保护集合交集(private set intersection, PSI)计算属于安全多方计算领域的特定应用问题,不仅具有重要的理论意义也具有很强的应用背景,在大数据时代,对该问题的研究更是符合人们日益强烈的在享受各种服务的同时达到隐私保护的需求.对安全多方计算基础理论进行了简要介绍,并重点介绍了目前主流的安全多方计算框架下2类PSI研究技术：传统的基于公钥加密机制,混乱电路,不经意传输的PSI协议和新型的云辅助的PSI协议,并对各类协议的过程、适用性、复杂性进行简要分析总结.同时,也对隐私保护集合交集问题的应用场景进行详细说明,进一步体现对该问题的实际研究价值.随着对该问题的不断深入研究,目前已经设计了在半诚实模型下快速完成上亿元素规模的隐私集合求交集协议.     

Garbled computation in cloud

With the wide adoption of cloud computing paradigm, it is important to develop appropriate techniques to protect client data privacy in the cloud. Encryption is one of the major techniques that could be used to achieve this gaol. However, data encryption at the rest along is insufficient for secure cloud computation environments. Further efficient techniques for carrying out computation over encrypted data are also required. Fully homomorphic encryption (FHE) and garbled circuits are naturally used to process encrypted data without leaking any information about the data. However, existing FHE schemes are inefficient for processing large amount of data in cloud and garbled circuits are one time programs and cannot be reused. Using modern technologies such as FHE, several authors have developed reusable garbled circuit techniques in recent years. But they are not efficient either and could not be deployed at a large scale. By relaxing the privacy definition from perfect forward secrecy to all-or-nothing privacy, we are able to design efficient reusable garbled circuits in this paper. These reusable garbled computation techniques could be used for processing encrypted cloud data efficiently.     

面向隐私保护的集合交集计算综述

随着物联网和大数据技术的发展,在计算机和手机上出现了大量分布式应用程序.然而现有的分布式数据处理方式已不能很好地满足用户对隐私保护的需求.隐私集合交集(private set intersection, PSI)协议作为一项典型的面向隐私保护的分布式集合计算技术,允许各参与方输入其私有集合,共同计算集合的交集,且不泄露除交集以外的任何信息.PSI协议作为安全多方计算的一种重要应用,已被广泛应用于隐私计算领域,具有重要的理论和实践意义.首先介绍PSI协议的基本密码技术、敌手模型、安全证明、编程框架等基础知识;其次系统总结了构造传统PSI协议的设计框架: 基于公钥加密体制的框架、基于混淆电路的框架、基于不经意传输的框架;随后介绍PSI协议核心的隐私集合元素比较技术/工具: 不经意伪随机函数、不经意多项式评估、布隆过滤器等;进一步地详细阐述了适应新型应用场景的PSI方案: 基于云辅助的PSI、非平衡型PSI、基于阈值的PSI和多方PSI;最后总结并展望面向隐私保护的集合交集计算中亟待解决问题和发展方向.     

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.     

基于同态加密技术的安全多方乘积协议

安全多方乘积计算是一类特殊的安全多方计算问题,用于共享多个参与方进行乘积计算的结果。针对现有安全多方乘积协议频繁调用安全两方乘积协议造成的通信代价高,数据量大的问题,在半诚实模型下,利用同态加密技术,提出了适用于复杂网络环境的串行安全多方乘积协议和理想通信环境下的并行安全多方乘积协议,并从理论上证明了协议的正确性与安全性。通过已有协议的对比分析,证明了提出的两个协议在通信代价和执行效率上具有明显的优势。     

Secure Two-Party Computational Geometry

Secure Multi-party Computation has been a research focus in international cryptographic community in recent years. In this paper the authors investigate how some computational geometric problems could be solved in a cooperative environment, where two parties need to solve a geometric problem based on their joint data, but neither wants to disclose its private data to the other party. These problems are the distance between two private points, the relation between a private point and a circle area, the relation between a private point and an ellipse area and the shortest distance between two point sets. The paper gives solutions to these specific geometric problems, and in doing so a building block is developed, the protocol for the distance between two private points, that is also useful in the solutions to other geometric problems and combinatorial problems.     

多方安全矩阵乘积协议及应用

研究特殊的多方安全计算问题,已经成为多方安全计算研究的一个新的重要内容,美国普渡大学的Du博士在他的学位论文中,已经研究、总结了部分特殊两方安全计算问题．同时,Du博士指出如何把两方安全计算推广到多方安全计算,如何把半诚实模型推广到恶意模型是一个非常有意义的工作．该文研究了在科学计算方向上Du博士提出的几个多方安全计算问题,得到了一些结果．该文的主要结果有：给出了一个科学计算基础协议——安全多方矩阵乘积协议,应用该协议,给出了解线性方程组、计算矩阵特征值问题的多方安全计算协议．     

公平理性委托计算协议

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

一种基于MLWE的同态内积方案

同态内积在安全多方几何计算、隐私数据挖掘、外包计算、可排序的密文检索等场景有广泛的应用.但现有的同态内积计算方案大多是基于RLWE的全同态加密方案,普遍存在效率不高的问题.在柯程松等人提出的基于MLWE的低膨胀率加密算法基础上,提出了一种同态内积方案.首先给出了密文空间上的张量积运算⊗,该密文空间上的运算对应明文空间上的整数向量内积运算;然后分析了方案的正确性与安全性;最后给出了两种优化的加密参数,对应计算两种不同大小的整数向量同态内积的应用场景.通过C++与大整数计算库NTL实现了该方案.对比其他同态加密方案,该方案能够比较高效地计算整数向量的同态内积.     

面向数据联邦的安全多方θ-连接算法

近年来,多个国家地区出台了一系列数据安全相关的法律,例如欧盟的《通用数据保护条例》等.这些相关法律法规的出台,加剧了各企业机构等多方之间数据共享难的数据孤岛问题.数据联邦(data federation)正是解决该问题的可能出路.数据联邦是指多个数据拥有方在不泄露各自原始数据的前提下,结合安全多方计算等隐私计算技术,联合完成查询任务的计算.这一概念已成为近年来的研究热点,并涌现出一系列相关的代表性系统工作,如SMCQL、Conclave.然而,针对关系数据库系统中核心的连接查询,现有数据联邦系统还存在如下问题:首先,连接种类单一,难以满足复杂连接条件下的查询需求;其次,算法性能低下,由于现有系统往往直接调用安全工具库,其运行时间与通信开销高昂.因此,针对以上问题进行研究,提出了数据联邦下连接算法.主要贡献如下:首先,设计实现了面向多方的联邦安全算子,能够支持多种运算;其次,提出了支持θ-连接的联邦连接算法与优化策略,显著减少了连接查询所需安全计算代价;最后,基于基准数据集TPC-H,验证了该算法的性能.实验结果表明,与现有数据联邦系统SMCQL、Conclave相比,该算法能够将运行时...     

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.