共查询到20条相似文献,搜索用时 31 毫秒
1.
Yehuda Lindell 《Journal of Cryptology》2008,21(2):200-249
In the setting of concurrent self composition, a single protocol is executed many times concurrently in a network. In this
paper, we prove lower bounds and impossibility results for secure protocols in this setting. First and foremost, we prove
that there exist large classes of functionalities that cannot be securely computed under concurrent self composition, by any protocol. We also prove a communication complexity lower bound on protocols that securely compute a large class of functionalities in this setting. Specifically, we show that
any protocol that computes a functionality from this class and remains secure for m concurrent executions, must have bandwidth of at least m bits. The above results are unconditional and hold for any type of simulation (i.e., even for non-black-box simulation).
In addition, we prove a severe lower bound on protocols that are proven secure using black-box simulation. Specifically, we
show that any protocol that computes the blind signature or oblivious transfer functionalities and remains secure for m concurrent executions, where security is proven via black-box simulation, must have at least m rounds of communication. Our results hold for the plain model, where no trusted setup phase is assumed. While proving our
impossibility results, we also show that for many functionalities, security under concurrent self composition (where a single secure protocol is run many times) is actually equivalent to the seemingly more stringent requirement
of security under concurrent general composition (where a secure protocol is run concurrently with other arbitrary protocols). This observation has significance
beyond the impossibility results that are derived by it for concurrent self composition.
This paper combines results that appeared in extended abstracts in Lindell (35th STOC, pp. 683–692, 2003; 1st Theory of Cryptography
Conference (TOC), LNCS, vol. 2951, pp. 203–222, 2004). 相似文献
2.
为了降低零知识的错误概率,通常采用协议的组合操作,独立运行安全的协议,在组合情形,其安全性却并非平凡的。利用UC安全密码元件可以在协议组合过程中作为一个模块安全调用的特性,在UC框架下,通过定义理想功能Fwzk,在Fwzk-混合模型下,讨论零知识协议的组合安全性问题。得到结果:基本Blum协议在序列合成时零知识性具有封闭性。 相似文献
3.
Universal composability and concurrent general composition consider a setting where secure protocols are run concurrently with each other and with arbitrary other possibly insecure protocols. Protocols that meet the definition of universal composability are guaranteed to remain secure even when run in this strongly adversarial setting. In the case of an honest majority, or where there is a trusted setup phase of some kind (like a common reference string or the key-registration public-key infrastructure of Barak et al.?in FOCS 2004), it has been shown that any functionality can be securely computed in a universally composable way. On the negative side, it has also been shown that in the plain model where there is no trusted setup at all, there are large classes of functionalities which cannot be securely computed in a universally composable way without an honest majority. In this paper, we extend these impossibility results for universal composability. We study a number of public-key models and show for which models the impossibility results of universal composability hold and for which they do not. We also consider a setting where the inputs to the protocols running in the network are fixed before any execution begins. The majority of our results are negative and we show that the known impossibility results for universal composability in the case of no honest majority extend to many other settings. 相似文献
4.
Yehuda Lindell 《Journal of Cryptology》2009,22(3):395-428
Concurrent general composition relates to a setting where a secure protocol is run in a network concurrently with other, arbitrary protocols. Clearly, security
in such a setting is what is desired, or even needed, in modern computer networks where many different protocols are executed
concurrently. Canetti (FOCS 2001) introduced the notion of universal composability and showed that security under this definition is sufficient for achieving concurrent general composition. However, it is
not known whether or not the opposite direction also holds.
Our main result is a proof that security under concurrent general composition, when interpreted in the natural way under the
simulation paradigm, is equivalent to a variant of universal composability, where the only difference relates to the order
of quantifiers in the definition. (In newer versions of universal composability, these variants are equivalent.) An important
corollary of this theorem is that existing impossibility results for universal composability (for all its variants) are inherent
for definitions that imply security under concurrent general composition, as formulated here. In particular, there are large
classes of two-party functionalities for which it is impossible to obtain protocols (in the plain model) that remain secure under concurrent general composition. We stress that the impossibility
results obtained are not “black-box,” and apply even to non-black-box simulation.
Our main result also demonstrates that the definition of universal composability is somewhat “minimal” in that the composition
guarantee provided by universal composability implies the definition itself. This indicates that the security definition of
universal composability is not overly restrictive.
An extended abstract of this work appeared in the 44th FOCS, 2003.
Yehuda Lindell: Most of this work was carried out while the author was at the IBM T.J. Watson Research Center. 相似文献
5.
6.
Universally composable three‐party password‐authenticated key exchange with contributiveness
下载免费PDF全文
![点击此处可从《International Journal of Communication Systems》网站下载免费的PDF全文](/ch/ext_images/free.gif)
Xuexian Hu Zhenfeng Zhang Qihui Zhang 《International Journal of Communication Systems》2015,28(6):1100-1111
Three‐party password‐authenticated key exchange (3PAKE) allows two clients, each sharing a password with a trusted server, to establish a session key with the help of the server. It is a quite practical mechanism for establishing secure channels in a large communication network. However, most current 3PAKE protocols are analyzed in security models that do not adequately address protocol composition problem. In this paper, an ideal functionality for 3PAKE within the universal composability framework is defined, which not only provides security guarantees under arbitrary composition with other protocols but also achieves contributiveness and explicit authentication. Moreover, we propose a generic construction of contributory 3PAKE protocol and prove that it securely realizes the ideal functionality in the static corruption model. Copyright © 2014 John Wiley & Sons, Ltd. 相似文献
7.
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. 相似文献
8.
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. 相似文献
9.
Within the framework of universal composability, an appropriate ideal functionality that captures the basic security requirements of three party password-based key exchange was defined. An efficient real-word three party password-based key exchange protocol was also proposed. This protocol securely realizes the ideal functionality with respect to static party corruption. Thus it provides security guarantees under arbitrary composition with other protocols. 相似文献
10.
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. 相似文献
11.
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. 相似文献
12.
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. 相似文献
13.
Player Simulation and General Adversary Structures in Perfect Multiparty Computation 总被引:6,自引:0,他引:6
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 相似文献
14.
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. 相似文献
15.
XIAO Feng ZHOU Ya-jian ZHOU Jing-xian ZHU Hong-liang NIU Xin-xin 《中国邮电高校学报(英文版)》2013,20(1):115-121,128
As an important component of internet of things, electronic product code (EPC) system is widely used in many areas. However, the mass deployment of EPC system is frequently degraded by security and privacy problems. Therefore, the major researches focus on the design of a secure EPC system with high efficiency. This paper discusses the security requirements of EPC system and presents a universal composable (UC) model for EPC system, the ideal functionality of EPC system is also formally defined with the UC framework. Then a secure protocol for EPC system under UC framework is proposed and the analysis of security and performance of the proposed protocol is given, in comparison with other protocols, the results show that the proposed protocol is UC secure and can provide privacy protection, untraceability, authorized access, anonymity and concurrent security for EPC system. Furthermore, less computation and storage resource are required by the proposed protocol. 相似文献
16.
17.
分类算法是机器学习和数据分析中重要的算法.当需要对分类算法本身以及算法的输入数据进行隐私保护时,就出现了分类算法安全评估问题.针对现有的分类算法安全评估协议效率较低的问题,文章给出了一种基于代数决策图和线性多分支程序的解决方案.首先,设计了基于代数决策图的安全函数评估协议,用以安全评估决策函数;其次,引入了线性多分支程序的概念,用其对分类算法进行表示.最后,借助线性多分支程序和基于代数决策图的安全函数评估协议,给出了一个私有线性多分支程序的安全评估协议.对新的协议的正确性和安全性进行了分析和证明.实验数据表明,与原有的解决方案相比,新的协议在效率上有明显的提高. 相似文献
18.
19.
A Distributed Key Generation (DKG) protocol is an essential component of threshold cryptosystems required to initialize the
cryptosystem securely and generate its private and public keys. In the case of discrete-log-based (dlog-based) threshold signature
schemes (ElGamal and its derivatives), the DKG protocol is further used in the distributed signature generation phase to generate
one-time signature randomizers (r = gk). In this paper we show that a widely used dlog-based DKG protocol suggested by Pedersen does not guarantee a uniformly random
distribution of generated keys: we describe an efficient active attacker controlling a small number of parties which successfully
biases the values of the generated keys away from uniform. We then present a new DKG protocol for the setting of dlog-based
cryptosystems which we prove to satisfy the security requirements from DKG protocols and, in particular, it ensures a uniform
distribution of the generated keys. The new protocol can be used as a secure replacement for the many applications of Pedersen's
protocol. Motivated by the fact that the new DKG protocol incurs additional communication cost relative to Pedersen's original
protocol, we investigate whether the latter can be used in specific applications which require relaxed security properties
from the DKG protocol. We answer this question affirmatively by showing that Pedersen's protocol suffices for the secure implementation
of certain threshold cryptosystems whose security can be reduced to the hardness of the discrete logarithm problem. In particular,
we show Pedersen's DKG to be sufficient for the construction of a threshold Schnorr signature scheme. Finally, we observe
an interesting trade-off between security (reductions), computation, and communication that arises when comparing Pedersen's
DKG protocol with ours. 相似文献
20.
Lindell 《Journal of Cryptology》2008,16(3):143-184
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). 相似文献