ACM Symposium on Theory of Computing (STOC)

Information-theoretically secure protocols and security under composition

Eyal Kushilevitz Z, Yehuda Lindell, Tal Rabin

Published May 21, 2006• 84 citations

Abstract

We investigate the question of whether security of protocols in the information-theoretic setting (where the adversary is computationally unbounded) implies security under concurrent composition. This question is motivated by the folklore that all known protocols that are secure in the information-theoretic setting are indeed secure under concurrent composition. We provide answers to this question for a number of different settings (i.e., considering perfect versus statistical security, and concurrent composition with adaptive versus fixed inputs). Our results enhance the understanding of what is necessary for obtaining security under composition, as well as providing tools (i.e., composition theorems) that can be used for proving the security of protocols under composition while considering only the standard stand-alone definitions of security.

DOI: 10.1145/1132516.1132532

Related papers

Information-Theoretically Secure Protocols and Security under Composition

Eyal Kushilevitz Z, Yehuda Lindell, Tal Rabin

We investigate the question of whether the security of protocols in the information-theoretic setting (where the adversary is computationally unbounded) implies the security of these protocols under concurrent composition. This question is motivated by the folklore that all known protocols that are secure in the information-theoretic setting are indeed secure under concurrent composition. We provide answers to this question for a number of different settings (i.e., considering perfect versus statistical security, and concurrent composition with adaptive versus fixed inputs). Our results enhance the understanding of what is necessary for obtaining security under composition, as well as providing tools (i.e., composition theorems) that can be used for proving the security of protocols under composition while considering only the standard stand-alone definitions of security.

SIAM Journal on ComputingJan 1, 201071 citations

Information-Theoretically Secure Protocols and Security Under Composition.

Eyal Kushilevitz Z, Yehuda Lindell, Tal Rabin

We investigate the question of whether security of protocols in the information-theoretic setting (where the adversary is computationally unbounded) implies the security of these protocols under concurrent composition. This question is motivated by the folklore that all known protocols that are secure in the information-theoretic setting are indeed secure under concurrent composition. We provide answers to this question for a number of different settings (i.e., considering perfect versus statistical security, and concurrent composition with adaptive versus fixed inputs). Our results enhance the understanding of what is necessary for obtaining security under composition, as well as providing tools (i.e., composition theorems) that can be used for proving the security of protocols under composition while considering only the standard stand-alone definitions of security.

Jan 1, 20091 citation

On the Necessity of Rewinding in Secure Multiparty Computation.

Michael Backes A, Jörn Müller‐Quade, Dominique Unruh

Abstract. We investigate whether security of multiparty computation in the information-theoretic setting implies their security under concurrent composition. We show that security in the stand-alone model proven using black-box simulators in the information-theoretic setting does not imply security under concurrent composition, not even security under 2-bounded concurrent self-composition with an inefficient simulator and fixed inputs. This in particular refutes recently made claims on the equiv-alence of security in the stand-alone model and concurrent composition for perfect and statistical security (STOC’06). Our result strongly relies on the question whether every rewinding simulator can be transformed into an equivalent, potentially inefficient non-rewinding (straight-line) simulator. We answer this question in the negative by giving a protocol that can be proven secure using a rewinding simulator, yet that is not secure for any non-rewinding simulator. 1

Jan 1, 20063 citations

Information-Theoretically Secure Protocols and Security under Composition

KushilevitzEyal, LindellYehuda, RabinTal

SIAM Journal on ComputingMar 1, 20102 citations

New Impossibility Results for Concurrent Composition and a Non-Interactive Completeness Theorem for Secure Computation.

Shweta Agrawal, Vipul Goyal, Abhishek Jain +2 more

We consider the client-server setting for the concurrent composition of secure protocols: in this setting, a single server interacts with multiple clients concurrently, executing with each client a specified protocol where only the client should receive any nontrivial output. Such a setting is easily motivated from an application standpoint. There are important special cases for which positive results are known – such as concurrent zero knowledge protocols – and it has been an open question explicitly asked, for instance, by Lindell [J. Cryptology’08] – whether other natural functionalities such as Oblivious Transfer (OT) are possible in this setting. In this work: • We resolve this open question by showing that unfortunately, even in this very limited concurrency setting, broad new impossibility results hold, ruling out not only OT, but in fact all nontrivial asymmetric functionalities. Our new negative results hold even if the inputs of all honest parties are fixed in advance, and the adversary receives no auxiliary information. • Along the way, we establish a new unconditional completeness result for asymmetric functionalities, where we characterize functionalities that are non-interactively complete secure against active adversaries.

Jan 1, 20120 citations

Security and Composition of Multi-party Cryptographic Protocols.

Ran Canetti

We present general definitions of security for multi-party cryptographic protocols, with focus on the task of evaluating a probabilistic function of the parties' inputs. We show that, with respect to these definitions, security is preserved under a natural composition operation. The definitions follow the general paradigm of known definitions; yet some substantial modifications and simplifications are introduced. The composition operation is the natural `subroutine substitution' operation, formalized by Micali and Rogaway. We consider several standard settings for multi-party protocols, including the cases of eavesdropping, Byzantine, non-adaptive and adaptive adversaries, as well as the information-theoretic and the computational models. In particular, in the computational model we provide the first definition of security of protocols that is shown to be preserved under composition.

Jan 1, 199880 citations