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.     

Random Oracles in Constantinople: Practical Asynchronous Byzantine Agreement Using Cryptography

Byzantine agreement requires a set of parties in a distributed system to agree on a value even if some parties are maliciously misbehaving. A new protocol for Byzantine agreement in a completely asynchronous network is presented that makes use of new cryptographic protocols, specifically protocols for threshold signatures and coin-tossing. These cryptographic protocols have practical and provably secure implementations in the random oracle model. In particular, a coin-tossing protocol based on the Diffie-Hellman problem is presented and analyzed. The resulting asynchronous Byzantine agreement protocol is both practical and theoretically optimal because it tolerates the maximum number of corrupted parties, runs in constant expected rounds, has message and communication complexity close to the optimum, and uses a trusted dealer only once in a setup phase, after which it can process a virtually unlimited number of transactions. The protocol is formulated as a transaction processing service in a cryptographic security model, which differs from the standard information-theoretic formalization and may be of independent interest.     

Fairness Versus Guaranteed Output Delivery in Secure Multiparty Computation

In the setting of secure multiparty computation, a set of parties wish to compute a joint function of their private inputs. The computation should preserve security properties such as privacy, correctness, independence of inputs, fairness and guaranteed output delivery. In the case of no honest majority, fairness and guaranteed output delivery cannot always be obtained. Thus, protocols for secure multiparty computation are typically of two disparate types: protocols that assume an honest majority (and achieve all properties including fairness and guaranteed output delivery) and protocols that do not assume an honest majority (and achieve all properties except for fairness and guaranteed output delivery). In addition, in the two-party case, fairness and guaranteed output delivery are equivalent. As a result, the properties of fairness (which means that if corrupted parties receive output then so do the honest parties) and guaranteed output delivery (which means that corrupted parties cannot prevent the honest parties from receiving output in any case) have typically been considered to be the same. In this paper, we initiate a study of the relation between fairness and guaranteed output delivery in secure multiparty computation. We show that in the multiparty setting these properties are distinct and proceed to study under what conditions fairness implies guaranteed output delivery (the opposite direction always holds). We also show the existence of non-trivial functions for which complete fairness is achievable (without an honest majority) but guaranteed output delivery is not, and the existence of non-trivial functions for which complete fairness and guaranteed output delivery are achievable. Our study sheds light on the role of broadcast in fairness and guaranteed output delivery and shows that these properties should sometimes be considered separately.     

基于安全多方计算的可信防共谋协议模型

n个互不信任的参与方共同计算一个函数,其中部分参与方形成联盟,通过共谋而破坏其他参与方的安全性,利用安全多方计算技术和通信通道,针对可嵌套共谋,提出可信防共谋协议模型。将模型运用到博弈论中,借助相关均衡的概念取代了可信第三方。     

多方隐私集合交集计算技术综述

随着互联网、大数据等新技术的快速发展,越来越多的分布式数据需要多方协作处理,隐私保护技术由此面临更大的挑战。安全多方计算是一种重要的隐私保护技术,可为数据的安全高效共享问题提供解决方案。作为安全多方计算的一个重要分支,隐私集合交集(PSI)计算技术可以在保护参与方的数据隐私性前提下计算两个或多个参与者私有数据集的交集,按照参与方数目可分为两方PSI和多方PSI。随着私人数据共享规模的扩大,多于两个参与方的应用场景越来越常见。多方PSI具有与两方PSI相似的技术基础但又有本质的不同。该文首先讨论了两方PSI的研究进展,其次详细梳理多方PSI技术的发展历程,将多方PSI技术依据应用场景的不同分为传统多方PSI技术以及门限多方PSI技术,并在不同场景下按照协议所采用密码技术和功能进行更细致的划分;对典型多方PSI协议进行分析,并对相关密码技术、敌手模型以及计算与通信复杂度进行对比。最后,给出了多方PSI技术的研究热点和未来发展方向。     

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).     

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.     

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.     

基于椭圆曲线的隐私增强认证密钥协商协议

认证密钥协商协议能够为不安全网络中的通信双方提供安全的会话密钥,但是,大多数的认证密钥协商协议并没有考虑保护用户隐私.论文关注网络服务中用户的隐私属性,特别是匿名性和可否认性,规范了增强用户隐私的认证密钥协商协议应满足的安全需求,即双向认证、密钥控制、密钥确认、会话密钥保密、已知会话密钥安全、会话密钥前向安全、用户身份匿名、用户身份前向匿名、不可关联和可否认,并基于椭圆曲线密码系统设计了一个满足安全需求的隐私增强认证密钥协商协议.     

姚氏百万富翁问题的高效解决方案

姚氏百万富翁问题解决方案已经成为许多多方保密计算问题解决方案的一个基本模块,但现有的解决方案效率低下,因而影响到其他多方保密计算方案的效率.本文利用长度函数与不经意传输设计了一个高效的解决方案,新方案同原有方案相比,计算复杂性明显降低.     

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.     

PUF‐based solutions for secure communications in Advanced Metering Infrastructure (AMI)

Advanced metering infrastructure (AMI) provides 2‐way communications between the utility and the smart meters. Developing authenticated key exchange (AKE) and broadcast authentication (BA) protocols is essential to provide secure communications in AMI. The security of all existing cryptographic protocols is based on the assumption that secret information is stored in the nonvolatile memories. In the AMI, the attackers can obtain some or all of the stored secret information from memories by a great variety of inexpensive and fast side‐channel attacks. Thus, all existing AKE and BA protocols are no longer secure. In this paper, we investigate how to develop secure AKE and BA protocols in the presence of memory attacks. As a solution, we propose to embed a physical unclonable function (PUF) in each party, which generates the secret values as required without the need to store them. By combining PUFs and 2 well‐known and secure protocols, we propose PUF‐based AKE and BA protocols. We show that our proposed protocols are memory leakage resilient. In addition, we prove their security in the standard model. Performance analysis of both protocols shows their efficiency for AMI applications. The proposed protocols can be easily implemented.     

Characterization of Secure Multiparty Computation Without Broadcast

A major challenge in the study of cryptography is characterizing the necessary and sufficient assumptions required to carry out a given cryptographic task. The focus of this work is the necessity of a broadcast channel for securely computing symmetric functionalities (where all the parties receive the same output) when one third of the parties, or more, might be corrupted. Assuming all parties are connected via a point-to-point network, but no broadcast channel (nor a secure setup phase) is available, we prove the following characterization:

• A symmetric n-party functionality can be securely computed facing \(n/3\le t<n/2\) corruptions (i.e., honest majority), if and only if it is \((n-2t)\) -dominated; a functionality is k-dominated, if any k-size subset of its input variables can be set to determine its output to some predetermined value.
• Assuming the existence of one-way functions, a symmetric n-party functionality can be securely computed facing \(t\ge n/2\) corruptions (i.e., no honest majority), if and only if it is 1-dominated and can be securely computed with broadcast.

It follows that, in case a third of the parties might be corrupted, broadcast is necessary for securely computing non-dominated functionalities (in which “small” subsets of the inputs cannot determine the output), including, as interesting special cases, the Boolean XOR and coin-flipping functionalities.

     

Unconditionally secure key agreement and the intrinsic conditionalinformation

This paper is concerned with secret-key agreement by public discussion. Assume that two parties Alice and Bob and an adversary Eve have access to independent realizations of random variables X, Y, and Z, respectively, with joint distribution P_XYZ. The secret-key rate S(X;Y∥Z) has been defined as the maximal rate at which Alice and Bob can generate a secret key by communication over an insecure, but authenticated channel such that Eve's information about this key is arbitrarily small. We define a new conditional mutual information measure, the intrinsic conditional mutual information between S and Y when given Z, denoted by I(X;Y↓Z), which is an upper bound on S(X;Y∥Z). The special scenarios are analyzed where X, Y, and Z are generated by sending a binary random variable R, for example a signal broadcast by a satellite, over independent channels, or two scenarios in which Z is generated by sending X and Y over erasure channels. In the first two scenarios it can be shown that the secret-key rate is strictly positive if and only if I(X;Y↓Z) is strictly positive. For the third scenario, a new protocol is presented which allows secret-key agreement even when all the previously known protocols fail     

A pairing-free identity-based authenticated group key agreement protocol for imbalanced mobile networks

The secure and reliable group communication gains popularity in imbalanced mobile networks due to the increase demand of the group-oriented applications such as teleconferences, collaborative workspaces, etc. For acquiring the group security objectives, many authenticated group key agreement (AGKA) protocols exploiting the public key infrastructure have been proposed, which require additional processing and storage space for validation of the public keys and the certificates. In addition, the most of the AGKA protocols are implemented using bilinear pairing and a map-to-point (MTP) hash function. The relative computation cost of the bilinear pairing is approximately two to three times more than the elliptic curve point multiplication (ECPM) and the MTP function has higher computation cost than an ECPM. Due to the limitation of communication bandwidth, computation ability, and storage space of the low-power mobile devices, these protocols are not suitable especially for insecure imbalanced mobile networks. To cope with the aforementioned problems, in this paper, we proposed a pairing-free identity-based authenticated group key agreement protocol using elliptic curve cryptosystem. It is found that the proposed protocol, compared with the related protocols, not only improves the computational efficiencies, but also enhances the security features.     

基于椭圆曲线的三方比特承诺

比特承诺是安全多方计算中最重要的基础协议之一,对构建更复杂的多方协议起着重要作用。该文提出了三方比特承诺模型,在该模型中,由两个证明者共同向一个验证者作出承诺。给出了基于椭圆曲线的三方比特承诺方案,经证明,尽管该方案完全基于经典计算环境,但是并不需要对协议参与方的计算能力作任何限制性假设,具有无条件安全性且对信道窃听免疫。该方案同时可以推广到比特串承诺协议。     

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

安全多方计算是国际密码学界近年来的研究热点.本文主要研究科学计算中最小值问题的安全多方计算,目前尚没有见到关于这个问题的解决方案.本文设计了一种新的编码方法,应用该编码方法和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.     

量子消息认证协议

研究了在量子信道上实现经典消息和量子消息认证的方法。给出了一个基于量子单向函数的非交互式经典消息认证加密协议。证明了给出的协议既是一个安全的加密方案,也是一个安全的认证方案。利用该认证加密协议作为子协议,构造了一个量子消息认证方案,并证明了其安全性。与BARNUM等给出的认证方案相比,该方案缩减了通信双方共享密钥的数量。     

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

安全多方计算是密码学界的一个重要研究方向,本文主要研究区间的安全计算问题.首先应用Paillier加密方案设计"点与区间"以及"区间与区间"关系两方保密计算基础协议,协议的特点是判定结果以密文形式输出.将其推广为有理区间关系判定协议时,相比已有协议,本文协议更为安全与高效.在此基础上,进一步研究多维度的"点与区间"以及"区间与区间"关系阈值判定这一类新问题.由于基础协议的输出结果为密文,故以此为基础所设计的多维度问题协议更加安全.最后,应用模拟范例方法严格证明了协议的安全性,并对协议进行了效率分析及模拟实验,理论分析及实验结果都说明本文协议是高效的.