Secure Two-Party Computation via Cut-and-Choose Oblivious Transfer

Protocols for secure two-party computation enable a pair of parties to compute a function of their inputs while preserving security properties such as privacy, correctness and independence of inputs. Recently, a number of protocols have been proposed for the efficient construction of two-party computation secure in the presence of malicious adversaries (where security is proven under the standard simulation-based ideal/real model paradigm for defining security). In this paper, we present a protocol for this task that follows the methodology of using cut-and-choose to boost Yao’s protocol to be secure in the presence of malicious adversaries. Relying on specific assumptions (DDH), we construct a protocol that is significantly more efficient and far simpler than the protocol of Lindell and Pinkas (Eurocrypt 2007) that follows the same methodology. We provide an exact, concrete analysis of the efficiency of our scheme and demonstrate that (at least for not very small circuits) our protocol is more efficient than any other known today.     

Fast Cut-and-Choose-Based Protocols for Malicious and Covert Adversaries

In the setting of secure two-party computation, two parties wish to securely compute a joint function of their private inputs, while revealing only the output. One of the primary techniques for achieving efficient secure two-party computation is that of Yao’s garbled circuits (FOCS 1986). In the semi-honest model, where just one garbled circuit is constructed and evaluated, Yao’s protocol has proven itself to be very efficient. However, a malicious adversary who constructs the garbled circuit may construct a garbling of a different circuit computing a different function, and this cannot be detected (due to the garbling). In order to solve this problem, many circuits are sent and some of them are opened to check that they are correct while the others are evaluated. This methodology, called cut-and-choose, introduces significant overhead, both in computation and in communication, and is mainly due to the number of circuits that must be used in order to prevent cheating. In this paper, we present a cut-and-choose protocol for secure computation based on garbled circuits, with security in the presence of malicious adversaries, that vastly improves on all previous protocols of this type. Concretely, for a cheating probability of at most \(2^{-40}\), the best previous works send between 125 and 128 circuits. In contrast, in our protocol 40 circuits alone suffice (with some additional overhead). Asymptotically, we achieve a cheating probability of \(2^{-s}\) where \(s\) is the number of garbled circuits, in contrast to the previous best of \(2^{-0.32s}\). We achieve this by introducing a new cut-and-choose methodology with the property that in order to cheat, all of the evaluated circuits must be incorrect, and not just the majority as in previous works. The security of our protocol relies on the decisional Diffie–Hellman assumption.     

安全向量优势协议及其应用

百万富翁问题是安全多方计算研究的热点问题之一,也是其他安全多方计算协议的基本构成模块.安全向量优势统计问题是百万富翁问题的推广,用于两方在不泄漏自己保密向量信息的前提下统计出满足大于关系的分量的数目.本文基于同态加密算法,通过对保密的数据进行编码,设计了一个计算百万富翁问题的协议,并利用模拟范例对协议进行安全性证明.然后利用这个新的协议作为基本模块,设计了一个向量优势统计协议,通过效率分析显示我们的方案是简单、高效的.最后将向量优势统计协议应用到整除判定问题和点与若干直线关系判定问题.     

一种安全的Ad Hoc On-demand路由协议

由于Ad Hoc网络固有的弱点,设计安全、有效的Ad Hoc路由协议是困难的.本文从新的角度设计了一个简单、安全的On-demand路由协议.在路径请求和响应阶段,源节点和目的节点的身份分别被隐藏,只有那些位于目的节点选择的最优路径上的节点可以获得完整的路由信息,从而产生有效的前向和反向路径.同时,一个公开的单向Hash函数可以利用隐藏的路由信息构建单向Hash链用于路由信息的认证,从而不需要预先的共享密钥.在一次路由计算中,只有源节点和目的节点需要进行一次非对称密码运算.     

一个保护私有信息的多边形相交判定协议

安全多方计算是信息安全领域的研究热点问题之一.保护私有信息的多边形相交判定是一个特殊的安全多方计算问题,在军事、商业等领域有着重要的应用前景.现有多边形相交判定算法的主要操作是执行点积协议,而目前的点积协议在安全性和计算效率上均难以同时满足该判定算法的要求.本文首先设计了一个常数时间的线段相交判定协议,在此基础上提出了一个保护私有信息的判定多边形相交的概率算法;证明了该算法是一个蒙特卡洛偏真算法,理论分析与实验结果均表明,该方法性能优于现有算法.     

数据相等问题的安全多方计算方案研究

安全多方计算是国际密码学界近年来的研究热点.本文主要研究科学计算中多个数据相等问题的安全多方计算,目前关于这个问题的研究还很少.本文设计了一种新的编码方法,以新的编码方法与ElGamal同态加密算法为基础,分别利用秘密分享技术和门限密码体制构造了两个在半诚实模型下能够抵抗合谋攻击的保密判定协议,应用模拟范例证明了协议的安全性,效率分析表明所设计的保密计算协议是高效的协议.并进一步设计了恶意模型下的安全计算方案.     

A new privacy-preserving Euclid-distance protocol and its applications in WSNs

Recently, privacy concerns become an increasingly critical issue. Secure multi-party computation plays an important role in privacy-preserving. Secure multi-party computational geometry is a new field of secure multi-party computation. In this paper, we devote to investigating the solutions to some secure geometric problems in a cooperative environment. The problem is collaboratively computing the Euclid-distance between two private vectors without disclosing the private input to each other. A general privacy-preserving Euclid-distance protocol is firstly presented as a building block and is proved to be secure and efficient in the comparison with the previous methods. And we proposed a new protocol for the application in Wireless Sensor Networks (WSNs), based on the novel Euclid-distance protocol and Density-Based Clustering Protocol (DBCP), so that the nodes from two sides can compute cooperatively to divide them into clusters without disclosing their location information to the opposite side.     

最小值问题的安全多方计算及其应用

安全多方计算是国际密码学界近年来的研究热点.本文主要研究科学计算中最小值问题的安全多方计算,目前尚没有见到关于这个问题的解决方案.本文设计了一种新的编码方法,应用该编码方法和ElGamal乘法同态加密算法,并结合秘密分享以及门限密码体制,在半诚实模型下设计了三个能够抵抗合谋攻击的最小值安全多方计算方案,并应用模拟范例证明了方案的安全性.以最小值解决方案为基础还可以解决最大值安全计算以及并集的安全计算等科学计算问题.效率分析表明所设计的安全计算方案是高效的方案.     

Almost-Everywhere Secure Computation with Edge Corruptions

We consider secure multi-party computation (MPC) in a setting where the adversary can separately corrupt not only the parties (nodes) but also the communication channels (edges), and can furthermore choose selectively and adaptively which edges or nodes to corrupt. Note that if an adversary corrupts an edge, even if the two nodes that share that edge are honest, the adversary can control the link and thus deliver wrong messages to both players. We consider this question in the information-theoretic setting, and require security against a computationally unbounded adversary.In a fully connected network the above question is simple (and we also provide an answer that is optimal up to a constant factor). What makes the problem more challenging is to consider the case of sparse networks. Partially connected networks are far more realistic than fully connected networks, which led Garay and Ostrovsky [Eurocrypt’08] to formulate the notion of (unconditional) almost everywhere (a.e.) secure computation in the node-corruption model, i.e., a model in which not all pairs of nodes are connected by secure channels and the adversary can corrupt some of the nodes (but not the edges). In such a setting, MPC among all honest nodes cannot be guaranteed due to the possible poor connectivity of some honest nodes with other honest nodes, and hence some of them must be “given up” and left out of the computation. The number of such nodes is a function of the underlying communication graph and the adversarial set of nodes.In this work we introduce the notion of almost-everywhere secure computation with edge corruptions, which is exactly the same problem as described above, except that we additionally allow the adversary to completely control some of the communication channels between two correct nodes—i.e., to “corrupt” edges in the network. While it is easy to see that an a.e. secure computation protocol for the original node-corruption model is also an a.e. secure computation protocol tolerating edge corruptions (albeit for a reduced fraction of edge corruptions with respect to the bound for node corruptions), no polynomial-time protocol is known in the case where a constant fraction of the edges can be corrupted (i.e., the maximum that can be tolerated) and the degree of the network is sublinear.We make progress on this front, by constructing graphs of degree O(n ^? ) (for arbitrary constant 0<?<1) on which we can run a.e. secure computation protocols tolerating a constant fraction of adversarial edges. The number of given-up nodes in our construction is μn (for some constant 0<μ<1 that depends on the fraction of corrupted edges), which is also asymptotically optimal.     

Security Against Covert Adversaries: Efficient Protocols for Realistic Adversaries

In the setting of secure multiparty computation, a set of mutually distrustful parties wish to securely compute some joint function of their private inputs. The computation should be carried out in a secure way, meaning that no coalition of corrupted parties should be able to learn more than specified or somehow cause the result to be “incorrect.” Typically, corrupted parties are either assumed to be semi-honest (meaning that they follow the protocol specification) or malicious (meaning that they may deviate arbitrarily from the protocol). However, in many settings, the assumption regarding semi-honest behavior does not suffice and security in the presence of malicious adversaries is excessive and expensive to achieve. In this paper, we introduce the notion of covert adversaries, which we believe faithfully models the adversarial behavior in many commercial, political, and social settings. Covert adversaries have the property that they may deviate arbitrarily from the protocol specification in an attempt to cheat, but do not wish to be “caught” doing so. We provide a definition of security for covert adversaries and show that it is possible to obtain highly efficient protocols that are secure against such adversaries. We stress that in our definition, we quantify over all (possibly malicious) adversaries and do not assume that the adversary behaves in any particular way. Rather, we guarantee that if an adversary deviates from the protocol in a way that would enable it to “cheat” (meaning that it can achieve something that is impossible in an ideal model where a trusted party is used to compute the function), then the honest parties are guaranteed to detect this cheating with good probability. We argue that this level of security is sufficient in many settings.     

基于密钥共享的安全多方计算应用

介绍了安全多方计算的基本概念和基于密钥共享的安全多方计算协议。现有的基于密钥共享的安全多方计算协议,能够计算有限域上的任意函数,但是研究表明,如果一个协议使用广泛,那么必然会牺牲性能上的一些代价。构造了函数f（s1,s2,…,sn）=αs1＋αs2＋…＋αsn的安全多方计算协议,对一般化的基于密钥共享的安全多方计算协议进行剪裁,去掉不相关的部分,并增加可验证性,大大提高了协议效率和实用性。     

集合成员关系的安全多方计算及其应用

集合成员关系的安全多方计算在保密数据挖掘和保密数据查询等方面有着重要的应用价值.针对以往方案在集合规模较大时的低效问题,本文将原问题转化成多项式一次性求值问题,在此基础上共设计了四个协议.利用同态加密设计了平凡协议1;利用离散对数设计了高效协议2,此协议非常简洁.最后,针对不同的应用场景又分别设计了云计算环境下外包用户计算的协议3和抗抵赖环境下可公开保密判定的协议4.通过分析和比较显示,我们的方案除了集合的势,其余任何信息都没有泄露,并且在集合规模较大时,相比以往方案高效而简洁.     

基于CPK的可证安全组群密钥交换协议

CPK组合公钥密码体制无需证书来保证公钥的真实性,克服了用户私钥完全由密钥管理中心生成的问题。丈中基于CPK设计了一个高效常数轮的组群密钥交挟协议,并且协议在CDH假设下可证安全和具有完美的前向安全性。该协议只需两轮通信即可协商一个组群会话密钥,无论在通信以及计算方面均很高效。此外该协议提供了一个设计组群密钥交换协议的方法,大部分的秘密共享体制均可直接应用于该协议。     

Concurrent Composition of Secure Protocols in the Timing Model

In the setting of secure multiparty computation, a set of mutually distrustful parties wish to securely compute some joint function of their inputs. In the stand-alone case it has been shown that every efficient function can be securely computed. However, in the setting of concurrent composition, broad impossibility results have been proven for the case of no honest majority and no trusted setup phase. These results hold both for the case of general composition (where a secure protocol is run many times concurrently with arbitrary other protocols) and self-composition (where a single secure protocol is run many times concurrently). In this paper we investigate the feasibility of obtaining security in the concurrent setting, assuming that each party has a local clock and that these clocks proceed at approximately the same rate. We show that under this mild timing assumption, it is possible to securely compute any multiparty functionality under concurrent self-composition. Loosely speaking, we also show that it is possible to securely compute any multiparty functionality under concurrent general composition, as long as the secure protocol is run only with protocols whose messages are delayed by a specified amount of time. On the negative side, we show that it is impossible to achieve security under concurrent general composition with no restrictions whatsoever on the network (like the aforementioned delays), even in the timing model.     

通用可组合公平安全多方计算协议简

在通用可组合框架下研究安全多方计算的公平性问题。在UC框架下,提出公平安全多方计算的安全模型。在模型中形式化定义了公平安全多方加法计算理想函数 和公平安全多方乘法计算理想函数 。然后,基于双线性对技术和承诺方案理想函数 ,在 -混合模型下分别设计公平加法协议 和公平乘法协议 安全实现理想函数 和 。最后,性能分析表明所提协议的有效性,能更好地满足应用需求。     

标准模型下高效的基于口令认证密钥协商协议

基于口令的认证密钥协商协议是利用预先共享的口令协商安全性较高的密钥。现有的基于口令认证密钥协商协议大多需要较大的计算量,或者只在随机预言模型下证明了协议的安全性。该文提出了新的标准模型下基于口令密钥协商协议,协议只需要一个生成元。 与其它标准模型下的协议相比,新协议不需要CPA或CCA2安全的加密方案,因而具有计算复杂度低和协议描述简单的特点。相对于殷胤等人在标准模型下可证安全的加密密钥协商协议一文中提出的协议,新协议将指数运算降低了64%。最后,基于DDH假设,在标准模型下证明了协议的安全性。     

Provably Secure On-Demand Source Routing in Mobile Ad Hoc Networks

Routing is one of the most basic networking functions in mobile ad hoc networks. Hence, an adversary can easily paralyze the operation of the network by attacking the routing protocol. This has been realized by many researchers and several "secure" routing protocols have been proposed for ad hoc networks. However, the security of those protocols has mainly been analyzed by informal means only. In this paper, we argue that flaws in ad hoc routing protocols can be very subtle, and we advocate a more systematic way of analysis. We propose a mathematical framework in which security can be precisely defined and routing protocols for mobile ad hoc networks can be proved to be secure in a rigorous manner. Our framework is tailored for on-demand source routing protocols, but the general principles are applicable to other types of protocols too. Our approach is based on the simulation paradigm, which has already been used extensively for the analysis of key establishment protocols, but, to the best of our knowledge, it has not been applied in the context of ad hoc routing so far. We also propose a new on-demand source routing protocol, called endairA, and we demonstrate the use of our framework by proving that it is secure in our model     

区间关系保密计算若干问题研究

安全多方计算是密码学界的一个重要研究方向,本文主要研究区间的安全计算问题.首先应用Paillier加密方案设计"点与区间"以及"区间与区间"关系两方保密计算基础协议,协议的特点是判定结果以密文形式输出.将其推广为有理区间关系判定协议时,相比已有协议,本文协议更为安全与高效.在此基础上,进一步研究多维度的"点与区间"以及...     

Completeness in Two-Party Secure Computation: A Computational View

A Secure Function Evaluation (SFE) of a two-variable function f(·,·) is a protocol that allows two parties with inputs x and y to evaluate f(x,y) in a manner where neither party learns "more than is necessary". A rich body of work deals with the study of completeness for secure two-party computation. A function f is complete for SFE if a protocol for securely evaluating f allows the secure evaluation of all (efficiently computable) functions. The questions investigated are which functions are complete for SFE, which functions have SFE protocols unconditionally and whether there are functions that are neither complete nor have efficient SFE protocols. The previous study of these questions was mainly conducted from an information theoretic point of view and provided strong answers in the form of combinatorial properties. However, we show that there are major differences between the information theoretic and computational settings. In particular, we show functions that are considered as having SFE unconditionally by the combinatorial criteria but are actually complete in the computational setting. We initiate the fully computational study of these fundamental questions. Somewhat surprisingly, we manage to provide an almost full characterization of the complete functions in this model as well. More precisely, we present a computational criterion (called computational row non-transitivity) for a function f to be complete for the asymmetric case. Furthermore, we show a matching criterion called computational row transitivity for f to have a simple SFE (based on no additional assumptions). This criterion is close to the negation of the computational row non-transitivity and thus we essentially characterize all "nice" functions as either complete or having SFE unconditionally.     

Identity‐based proxy signature over NTRU lattice

Proxy signature scheme is an important cryptographic primitive, for an entity can delegate his signing right to another entity. Although identity‐based proxy signature schemes based on conventional number‐theoretic problems have been proposed for a long time, the researchers have paid less attention to lattice‐based proxy signature schemes that can resist quantum attack. In this paper, we first propose an identity‐based proxy signature scheme over Number Theory Research Unit (NTRU)‐lattice. We proved that the proposed paradigm is secure under the hardness of the γ‐shortest vector problem on the NTRU lattice in random oracle model; furthermore, the comparison with some existing schemes shows our scheme is more efficient in terms of proxy signature secret key size, proxy signature size, and computation complexity. As the elemental problem of the proposed scheme is difficult even for quantum computation model, our scheme can work well in quantum age.