Partial Fairness in Secure Two-Party Computation

A protocol for secure computation is fair if either both parties learn the output or else neither party does. A seminal result of Cleve (STOC ’86) is that, in general, complete fairness is impossible to achieve in two-party computation. In light of this, various techniques for obtaining partial fairness have been suggested in the literature. We propose a definition of partial fairness within the standard real-/ideal-world paradigm. We also show broad feasibility results with respect to our definition: partial fairness is possible for any (randomized) functionality f:X×Y→Z ¹×Z ² at least one of whose domains or ranges is polynomial in size. Our protocols are always private, and when one of the domains has polynomial size our protocols also achieve the usual notion of security with abort. We work in the standard communication model (in particular, we do not assume simultaneous channels) and, in contrast to some prior work, rely only on standard cryptographic assumptions (e.g., enhanced trapdoor permutations).     

路径点包含安全两方计算问题的求解

多方安全计算中集合点包含和几何点包含等方法都是近几年密码学研究的一个热点问题。提出路径点包含的安全多方计算问题,并对路径点包含基本原理进行研究。通过对选定路径进行特殊编码,编码后把路径转化为集合,再利用集合包含问题的处理方法,计算了两集合的交集,进而又把集合还原为路径,求出了两路径的公共路径,得到路径点包含安全两方计算的保密结果。最后分析证明了新方案的安全性。     

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.     

Parallel Coin-Tossing and Constant-Round Secure Two-Party Computation

In this paper we show that any two-party functionality can be securely computed in a constant number of rounds , where security is obtained against (polynomial-time) malicious adversaries that may arbitrarily deviate from the protocol specification. This is in contrast to Yao's constant-round protocol that ensures security only in the face of semi-honest adversaries, and to its malicious adversary version that requires a polynomial number of rounds. In order to obtain our result, we present a constant-round protocol for secure coin-tossing of polynomially many coins (in parallel). We then show how this protocol can be used in conjunction with other existing constructions in order to obtain a constant-round protocol for securely computing any two-party functionality. On the subject of coin-tossing, we also present a constant-round almost perfect coin-tossing protocol, where by ``almost perfect' we mean that the resulting coins are guaranteed to be statistically close to uniform (and not just pseudorandom).     

Completeness for Symmetric Two-Party Functionalities: Revisited

Understanding the minimal assumptions required for carrying out cryptographic tasks is one of the fundamental goals of theoretic cryptography. A rich body of work has been dedicated to understanding the complexity of cryptographic tasks in the context of (semi-honest) secure two-party computation. Much of this work has focused on the characterization of trivial and complete functionalities (resp., functionalities that can be securely implemented unconditionally, and functionalities that can be used to securely compute all functionalities). Most previous works define reductions via an ideal implementation of the functionality; i.e., f reduces to g if one can implement f using a black-box (or oracle) that computes the function g and returns the output to both parties. Such a reduction models the computation of f as an atomic operation. However, in the real world, protocols proceed in rounds, and the output is not learned by the parties simultaneously. In this paper, we show that this distinction is significant. Specifically, we show that there exist symmetric functionalities (where both parties receive the same outcome) that are neither trivial nor complete under “black-box reductions,” and yet the existence of a constant-round protocol for securely computing such a functionality implies infinitely often oblivious transfer (meaning that it is secure for infinitely many values of the security parameter). In light of the above, we propose an alternative definitional infrastructure for studying the triviality and completeness of functionalities.     

Toward a Game Theoretic View of Secure Computation

We demonstrate how Game Theoretic concepts and formalism can be used to capture cryptographic notions of security. In the restricted but indicative case of two-party protocols in the face of malicious fail-stop faults, we first show how the traditional notions of secrecy and correctness of protocols can be captured as properties of Nash equilibria in games for rational players. Next, we concentrate on fairness. Here we demonstrate a Game Theoretic notion and two different cryptographic notions that turn out to all be equivalent. In addition, we provide a simulation-based notion that implies the previous three. All four notions are weaker than existing cryptographic notions of fairness. In particular, we show that they can be met in some natural setting where existing notions of fairness are provably impossible to achieve.     

安全的两方协作SM2签名算法

在签名算法中,一旦签名私钥被窃取,敌手就可以随意伪造合法用户的签名,从而致使合法用户的权益受到侵害.为了降低签名私钥泄露的风险,本文提出了一种安全的两方协作SM2数字签名算法,该算法将签名私钥拆分成两个部分,分别交由两方来保管,通过采用零知识证明、比特承诺、同态加密等密码学技术保证了只有合法的通信双方才能安全地协作产生完整的SM2签名,任何一方都不能单独恢复出完整的签名私钥,方案的安全性在通用可组合安全框架下被证明,与已有的SM2协作签名方案相比,本文方案具有交互次数少、协作签名效率高等优势.     

安全多方计算研究

安全多方计算（Secure Multi—party Computation,SMC）是解决一组互不信任的参与方之间保护隐私的协同计算问题,SMC需要确保输入的独立性、计算正确性,同时各输入值也不泄露给参与方。SMC计算首先由百万富翁问题提出,随着互联网、电子商务、电子政务的普及,可以广泛应用在网络投票、网络拍卖等应用场合。文中分析了SMC计算的关键技术,如协议安全、零知识证明、比特承诺、不经意传输等,并对此展开了应用研究,介绍SMC计算的应用,具有一定的理论和实际意义。     

安全两方向量优势统计协议及其应用

 安全两方向量优势统计问题是百万富翁问题的推广问题,用于两方在不泄漏自己保密向量信息的前提下统计出满足大于关系的分量的数目.本文在半诚实模型下利用加同态加密体制解决了安全两方向量优势统计问题,分析了该解决方案的正确性,安全性和复杂性;利用该优势统计协议设计了一个安全两方向量分量和排序协议,并且将设计的安全两方向量分量和排序协议应用于安全生成最小树图形算法中.     

Secure Computation Without Authentication

Research on secure multiparty computation has mainly concentrated on the case where the parties can authenticate each other and the communication between them. This work addresses the question of what security can be guaranteed when authentication is not available. We consider a completely unauthenticated setting, where all messages sent by the parties may be tampered with and modified by the adversary without the uncorrupted parties being able to detect this fact. In this model, it is not possible to achieve the same level of security as in the authenticated-channel setting. Nevertheless, we show that meaningful security guarantees can be provided: Essentially, all the adversary can do is to partition the network into disjoint sets, where in each set the computation is secure in of itself, and also independent of the computation in the other sets. In this setting we provide, for the first time, nontrivial security guarantees in a model with no setup assumptions whatsoever. We also obtain similar results while guaranteeing universal composability, in some variants of the common reference string model. Finally, our protocols can be used to provide conceptually simple and unified solutions to a number of problems that were studied separately in the past, including password-based authenticated key exchange and nonmalleable commitments. As an application of our results, we study the question of constructing secure protocols in partially authenticated networks, where some of the links are authenticated, and some are not (as is the case in most networks today).     

Efficient One-Sided Adaptively Secure Computation

Adaptive security is a strong security notion that captures additional security threats that are not addressed by static corruptions. For instance, it captures real-world scenarios where “hackers” actively break into computers, possibly while they are executing secure protocols. Studying this setting is interesting from both theoretical and practical points of view. A primary building block in designing adaptively secure protocols is a non-committing encryption (NCE) that implements secure communication channels in the presence of adaptive corruptions. Current constructions require a number of public key operations that grow linearly with the length of the message. Furthermore, general two-party protocols require a number of NCE calls that dependent both on the circuit size and on the security parameter. In this paper, we study the two-party setting in which at most one of the parties is adaptively corrupted, and demonstrate the feasibility of (1) NCE with constant number of public key operations for large message spaces, (2) oblivious transfer with constant number of public key operations for large sender’s input spaces, and (3) constant round secure computation protocols with an overall number of public key operations that is linear in the circuit size. Our study demonstrates that such primitives indeed exist in the presence of single corruptions without erasures, while this is not known for fully adaptive security under standard assumptions (where both parties may get corrupted). Our results are shown in the UC setting with a CRS setup.     

On the Limitations of Universally Composable Two-Party Computation Without Set-Up Assumptions

The recently proposed universally composable security framework for analyzing security of cryptographic protocols provides very strong security guarantees. In particular, a protocol proven secure in this framework is guaranteed to maintain its security even when run concurrently with arbitrary other protocols. It has been shown that if a majority of the parties are honest, then universally composable protocols exist for essentially any cryptographic task in the plain model (i.e., with no set-up assumptions beyond that of authenticated communication). When honest majority is not guaranteed, general feasibility results are known only when given a trusted set-up, such as in the common reference string model. Only little was known regarding the existence of universally composable protocols in the plain model without honest majority, and in particular regarding the important special case of two-party protocols. We study the feasibility of universally composable two-party function evaluation in the plain model. Our results show that in this setting, very few functions can be securely computed in the framework of universal composability. We demonstrate this by providing broad impossibility results that apply to large classes of deterministic and probabilistic functions. For some of these classes, we also present full characterizations of what can and cannot be securely realized in the framework of universal composability. Specifically, our characterizations are for the classes of deterministic functions in which (a) both parties receive the same output, (b) only one party receives output, and (c) only one party has input.     

Secure Multi-Party Computation without Agreement

It has recently been shown that authenticated Byzantine agreement, in which more than a third of the parties are corrupted, cannot be securely realized under concurrent or parallel (stateless) composition. This result puts into question any usage of authenticated Byzantine agreement in a setting where many executions take place. In particular, this is true for the whole body of work of secure multi-party protocols in the case that a third or more of the parties are corrupted. This is because these protocols strongly rely on the extensive use of a broadcast channel, which is in turn realized using authenticated Byzantine agreement. We remark that it was accepted folklore that the use of a broadcast channel (or authenticated Byzantine agreement) is actually essential for achieving meaningful secure multi-party computation whenever a third or more of the parties are corrupted. In this paper we show that this folklore is false. We present a mild relaxation of the definition of secure computation allowing abort. Our new definition captures all the central security issues of secure computation, including privacy, correctness and independence of inputs. However, the novelty of the definition is in decoupling the issue of agreement from these issues. We then show that this relaxation suffices for achieving secure computation in a point-to-point network. That is, we show that secure multi-party computation for this definition can be achieved for any number of corrupted parties and without a broadcast channel (or trusted pre-processing phase as required for running authenticated Byzantine agreement). Furthermore, this is achieved by just replacing the broadcast channel in known protocols with a very simple and efficient echo-broadcast protocol. An important corollary of our result is the ability to obtain multi-party protocols that remain secure under composition, without assuming a broadcast channel.     

移动漫游中强安全的两方匿名认证密钥协商方案

由于低功耗的移动设备计算和存储能力较低,设计一种高效且强安全的两方匿名漫游认证与密钥协商方案是一项挑战性的工作.现有方案不仅计算开销较高,而且不能抵抗临时秘密泄露攻击.针对这两点不足,提出一种新的两方匿名漫游认证与密钥协商方案.在新方案中,基于Schnorr签名机制,设计了一种高效的基于身份签密算法,利用签密的特性实现实体的相互认证和不可追踪;利用认证双方的公私钥直接构造了一个计算Diffie-Hellman（Computational Diffie-Hellman,CDH）问题实例,能抵抗临时秘密泄露攻击.新方案实现了可证明安全,在eCK（extended Canetti-Krawczyk）模型基础上,探讨两方漫游认证密钥协商方案安全证明过程中可能出现的情形,进行归纳和拓展,并给出新方案的安全性证明,其安全性被规约为多项式时间敌手求解椭圆曲线上的CDH问题.对比分析表明：新方案安全性更强,需要实现的算法库更少,计算和通信开销较低.新方案可应用于移动通信网络、物联网或泛在网络,为资源约束型移动终端提供漫游接入服务.     

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.     

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

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

Minimal Complete Primitives for Secure Multi-Party Computation

The study of minimal cryptographic primitives needed to implement secure computation among two or more players is a fundamental question in cryptography. The issue of complete primitives for the case of two players has been thoroughly studied. However, in the multi-party setting, when there are n > 2 players and t of them are corrupted, the question of what are the simplest complete primitives remained open for t n/3. (A primitive is called complete if any computation can be carried out by the players having access only to the primitive and local computation.) In this paper we consider this question, and introduce complete primitives of minimal cardinality for secure multi-party computation. The cardinality issue (number of players accessing the primitive) is essential in settings where primitives are implemented by some other means, and the simpler the primitive the easier it is to realize. We show that our primitives are complete and of minimal cardinality possible for most cases.     

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

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