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.     

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.     

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.     

Player Simulation and General Adversary Structures in Perfect Multiparty Computation

The goal of secure multiparty computation is to transform a given protocol involving a trusted party into a protocol without need for the trusted party, by simulating the party among the players. Indeed, by the same means, one can simulate an arbitrary player in any given protocol. We formally define what it means to simulate a player by a multiparty protocol among a set of (new) players, and we derive the resilience of the new protocol as a function of the resiliences of the original protocol and the protocol used for the simulation. In contrast to all previous protocols that specify the tolerable adversaries by the number of corruptible players (a threshold), we consider general adversaries characterized by an adversary structure, a set of subsets of the player set, where the adversary may corrupt the players of one set in the structure. Recursively applying the simulation technique to standard threshold multiparty protocols results in protocols secure against general adversaries. The classical results in unconditional multiparty computation among a set of n players state that, in the passive model, any adversary that corrupts less than n/2 players can be tolerated, and in the active model, any adversary that corrupts less than n/3 players can be tolerated. Strictly generalizing these results we prove that, in the passive model, every function (more generally, every cooperation specified by involving a trusted party) can be computed securely with respect to a given adversary structure if and only if no two sets in the adversary structure cover the full set of players, and, in the active model, if and only if no three sets cover the full set of players. The complexities of the protocols are polynomial in the number of maximal adverse player sets in the adversary structure. Received 31 December 1997 and revised 26 February 1999     

Adaptive Zero-Knowledge Proofs and Adaptively Secure Oblivious Transfer

In the setting of secure computation, a set of parties wish to securely compute some function of their inputs, in the presence of an adversary. The adversary in question may be static (meaning that it controls a predetermined subset of the parties) or adaptive (meaning that it can choose to corrupt parties during the protocol execution and based on what it sees). In this paper, we study two fundamental questions relating to the basic zero-knowledge and oblivious transfer protocol problems:

Cryptanalysis of an identity‐based authenticated key exchange protocol

Authenticated key exchange protocols represent an important cryptographic mechanism that enables several parties to communicate securely over an open network. Elashry, Mu, and Susilo proposed an identity‐based authenticated key exchange (IBAKE) protocol where different parties establish secure communication by means of their public identities.The authors also introduced a new security notion for IBAKE protocols called resiliency, that is, if the secret shared key is compromised, the entities can generate another shared secret key without establishing a new session between them. They then claimed that their IBAKE protocol satisfies this security notion. We analyze the security of their protocol and prove that it has a major security flaw, which renders it insecure against an impersonation attack. We also disprove the resiliency property of their scheme by proposing an attack where an adversary can compute any shared secret key if just one secret bit is leaked.     

Secure Computation of the Median (and Other Elements of Specified Ranks)

We consider the problem of securely computing the kth-ranked element of the union of two or more large, confidential data sets. This is a fundamental question motivated by many practical contexts. For example, two competitive companies may wish to compute the median salary of their combined employee populations without revealing to each other the exact salaries of their employees. While protocols do exist for computing the kth-ranked element, they require time that is at least linear in the sum of the sizes of their combined inputs. This paper investigates two-party and multi-party protocols for both the semi-honest and malicious cases. In the two-party setting, we prove that the problem can be solved in a number of rounds that is logarithmic in k, where each round requires communication and computation cost that is linear in b, the number of bits needed to describe each element of the input data. In the multi-party setting, we prove that the number of rounds is linear in b, where each round has overhead proportional to b multiplied by the number of parties. The multi-party protocol can be used in the two-party case. The overhead introduced by our protocols closely match the communication complexity lower bound. Our protocols can handle a malicious adversary via simple consistency checks.     

Session-Key Generation Using Human Passwords Only

We present session-key generation protocols in a model where the legitimate parties share only a human-memorizable password, and there is no additional set-up assumption in the network. Our protocol is proven secure under the assumption that enhanced trapdoor permutations exist. The security guarantee holds with respect to probabilistic polynomial-time adversaries that control the communication channel (between the parties), and may omit, insert, and modify messages at their choice. Loosely speaking, the effect of such an adversary that attacks an execution of our protocol is comparable with an attack in which an adversary is only allowed to make a constant number of queries of the form "is w the password of Party A." We stress that the result holds also in case the passwords are selected at random from a small dictionary so that it is feasible (for the adversary) to scan the entire directory. We note that prior to our result, it was not known whether or not such protocols were attainable without the use of random oracles or additional set-up assumptions.     

Secure Communication in Minimal Connectivity Models

Problems of secure communication and computation have been studied extensively in network models. In this work we ask what is possible in the information-theoretic setting when the adversary is very strong (Byzantine) and the network connectivity is very low (minimum needed for crash-tolerance). We concentrate on a new model called ``multicast lines,' and show a sizable gap between the connectivity required for perfect security and for almost perfect security. Our results also have implications to the commonly studied simple channel model and to general secure multiparty computation. Received 10 September 1997 and revised June, 1999     

A secure and efficient password‐authenticated group key exchange protocol for mobile ad hoc networks

Password‐authenticated group key exchange protocols enable communication parties to establish a common secret key (a session key) by only using short secret passwords. Such protocols have been receiving significant attention. This paper shows some security weaknesses in some recently proposed password‐authenticated group key exchange protocols. Furthermore, a secure and efficient password‐authenticated group key exchange protocol in mobile ad hoc networks is proposed. It only requires constant round to generate a group session key under the dynamic scenario. In other words, the overhead of key generation is independent of the size of a total group. Further, the security properties of our protocol are formally validated by a model checking tool called AVISPA. Security and performance analyses show that, compared with other related group key exchange schemes, the proposed protocol is also efficient for real‐world applications in enhancing the security over wireless communications. Copyright © 2011 John Wiley & Sons, Ltd.     

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.     

Joint encryption and message-efficient secure computation

This paper addresses the message complexity of secure computation in the (passive adversary) privacy setting. We show that O(nC) encrypted bits of communication suffice for n parties to evaluate any boolean circuit of size C privately, under a specific cryptographic assumption. This work establishes a connection between secure distributed computation and group-oriented cryptography, i.e., cryptographic methods in which subsets of individuals can act jointly as single agents. Our secure computation protocol relies on a new group-oriented probablistic public-key encryption scheme with useful algebraic properties.Work performed while at Columbia University, with the support of a summer internship at Bellcore and a visiting position at C.W.I.     

Byzantine Agreement Given Partial Broadcast

This paper considers unconditionally secure protocols for reliable broadcast among a set of n players, where up to t of the players can be corrupted by a (Byzantine) adversary but the remaining h = n - t players remain honest. In the standard model with a complete, synchronous network of bilateral authenticated communication channels among the players, broadcast is achievable if and only if 2n/h < 3. We show that, by extending this model by the existence of partial broadcast channels among subsets of b players, global broadcast can be achieved if and only if the number h of honest players satisfies 2n/h < b + 1. Achievability is demonstrated by protocols with communication and computation complexities polynomial in the size of the network, i.e., in the number of partial broadcast channels. A respective characterization for the related consensus problem is also given.     

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

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

Adaptive versus Non-Adaptive Security of Multi-Party Protocols

Security analysis of multi-party cryptographic protocols distinguishes between two types of adversarial settings: In the non-adaptive setting the set of corrupted parties is chosen in advance, before the interaction begins. In the adaptive setting the adversary chooses who to corrupt during the course of the computation. We study the relations between adaptive security (i.e., security in the adaptive setting) and nonadaptive security, according to two definitions and in several models of computation.     

Information Theoretic Bounds on Authentication Systems in Query Model

Authentication codes provide message integrity guarantees in an information theoretic sense within a symmetric key setting. Information theoretic bounds on the success probability of an adversary who has access to previously authenticated messages have been derived by Simmons and Rosenbaum, among others. In this paper, we consider a strong attack scenario where the adversary is adaptive and has access to authentication and verification oracles. We derive information theoretic bounds on the success probability of the adversary and on the key size of the code. This brings the study of unconditionally secure authentication systems on a par with the study of computationally secure ones. We characterize the codes that meet these bounds and compare our result with the earlier ones.     

An efficient pairing‐free identity‐based authenticated group key agreement protocol

An authenticated group key agreement protocol allows participants to agree on a group key that will be subsequently used to provide secure group communication over an insecure network. In this paper, we give a security analysis on a pairing‐free identity‐based authenticated group key agreement because of Islam et al. We show that the protocol of Islam et al. cannot satisfy the minimal security requirements of the key agreement protocols. We propose an efficient pairing‐free identity‐based authenticated group key agreement for imbalanced mobile network. The proposed protocol can be implemented easily for practical application in mobile networks as it is free from bilinear. Under the difficulty of the InvCDH and CDH we demonstrate that the proposed protocol provides perfect forward secrecy, implicit key authentication and the dynamic functionality. As compared with the group key agreement protocols for imbalanced mobile network, the proposed protocol provides stronger security properties and high efficiency. Copyright © 2013 John Wiley & Sons, Ltd.     

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.