Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

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

Shweta Agrawal, Vipul Goyal, Abhishek Jain, Manoj Prabhakaran, Amit Sahai

Published Jan 1, 2012• 18 citations
Publisher
DOI
10.1007/978-3-642-32009-5_26

Related papers

Lower Bounds and Impossibility Results for Concurrent Self Composition

Yehuda Lindell

Journal of Cryptology•Sep 27, 2007•36 citations

Concurrently Composable Non-interactive Secure Computation

Andrew Morgan, Rafael Pass

Lecture notes in computer science•Jan 1, 2022•0 citations

Adaptive and Concurrent Secure Computation from New Adaptive, Non-malleable Commitments

Dana Dachman-Soled, Tal Malkin, Mariana Raykova +1 more

Lecture notes in computer science•Jan 1, 2013•25 citations

Simulatable Security and Polynomially Bounded Concurrent Composition.

Dennis Hofheinz, Dominique Unruh

•Jan 1, 2006•2 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, 2012•0 citations

Black-Box Constructions of Bounded-Concurrent Secure Computation

Sanjam Garg, Xiao Rong Liang, Omkant Pandey +1 more

Lecture notes in computer science•Jan 1, 2020•3 citations
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.