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

On the Round Complexity of Covert Computation.

Vipul Goyal, Abhishek Jain

Published Jan 1, 2010• 0 citations
OpenAlex

Abstract

In STOC’05, von Ahn, Hopper and Langford introduced the notion of covert computation. In covert computation, a party runs a secure computation protocol over a covert (or steganographic) channel without knowing if the other parties are participating as well or not. At the end of the protocol, if all parties participated in the protocol and if the function output is “favorable ” to all parties, then the output is revealed (along with the fact that everyone participated). All covert computation protocols known so far require a large polynomial number of rounds. In this work, we first study the question of the round complexity of covert computation and obtain the following results: • There does not exist a constant round covert computation protocol with respect to black box simulation even for the case of two parties. (In comparison, such protocols are known even for the multi-party case if there is no covertness requirement.) • By relying on the two slot non-black-box simulation technique of Pass (STOC’04) and techniques from cryptography in NC 0 (Applebaum et al, FOCS’04), we obtain a construction of a constant round covert multi-party computation protocol. Put together, the above adds one more example to the growing list of tasks for which non-black-box simulation techniques (introduced in the work of Barak in FOCS’01) are necessary. Finally, we study the problem of covert multi-party computation in the setting where the parties only have point to point (covert) communication channels. We observe that our covert computation protocol for the broadcast channel inherits, from the protocol of Pass, the property of secure composition in the bounded concurrent setting. Then, as an application of this protocol, somewhat surprisingly we show the existence of covert multi-party computation with point to point channels (assuming that the number of parties is a constant). 0 1

Related papers

On the round complexity of covert computation

Vipul Goyal, Abhishek Jain

In STOC'05, von Ahn, Hopper and Langford introduced the notion of covert computation. In covert computation, a party runs a secure computation protocol over a covert (or steganographic) channel without knowing if the other parties are participating as well or not. At the end of the protocol, if all parties participated in the protocol and if the function output is "favorable" to all parties, then the output is revealed (along with the fact that everyone participated). All covert computation protocols known so far require a large polynomial number of rounds. In this work, we first study the question of the round complexity of covert computation and obtain the following results: There does not exist a constant round covert computation protocol with respect to black box simulation even for the case of two parties. (In comparison, such protocols are known even for the multi-party case if there is no covertness requirement.) By relying on the two slot non-black-box simulation technique of Pass (STOC'04) and techniques from cryptography in NC0 (Applebaum et al, FOCS'04), we obtain a construction of a constant round covert multi-party computation protocol.

ACM Symposium on Theory of Computing (STOC)•Jun 5, 2010•22 citations

Covert Multi-Party Computation

Nishanth Chandran, Vipul Goyal, Rafail Ostrovsky +1 more

In STOC'05, Aim, Hopper and Longford introduced the notion of covert computation. A covert computation protocol is one in which parties am run a protocol without knowing if other parties ore also participating in the protocol or not. At the end of the protocol, if all parties participated in the protocol and if the function output is favorable to all parties, then the output is revealed. Ahn et al. constructed a protocol for covert two-partv computation in the random oracle model In this paper, we offer a construction for covert multiparty computation. Our construction is in the standard model and does not require random oracles. In order to achieve this goal, we introduce a number of new techniques. Central to our work is the development of "zero-knowledge proofs to garbled circuits," which we believe could be of independent interest. Along the way, we also develop a definition of covert computation as per the Ideal/Real model simulation paradigm.

Annual Symposium on Foundations of Computer Science•Oct 1, 2007•51 citations

Black-Box, Round-Efficient Secure Computation via Non-malleability Amplification

Hoeteck Wee

We present round-efficient protocols for secure multi-party computation with a dishonest majority that rely on black-box access to the underlying primitives. Our main contributions are as follows: · a O(log* n)-round protocol that relies on black-box access to dense cryptosystems, homomorphic encryption schemes, or lossy encryption schemes. This improves upon the recent O(1)log* n-round protocol of Lin, Pass and Venkitasubramaniam (STOC 2009) that relies on non-black-box access to a smaller class of primitives. · a O(1)-round protocol requiring in addition, black-box access to a one-way function with sub-exponential hardness, improving upon the recent work of Pass and Wee (Eurocrypt 2010). These are the first black-box constructions for secure computation with sublinear round complexity. Our constructions build on and improve upon the work of Lin and Pass (STOC 2009) on nonmalleability amplification, as well as that of Ishai et al. (STOC 2006) on black-box secure computation. In addition to the results on secure computation, we also obtain a simple construction of a 0(log* n)-round non-malleable commitment scheme based on one-way functions, improving upon the recent O(1)log* n-round protocol of Lin and Pass (STOC 2009). Our construction uses a novel transformation for handling arbitrary man-in-the-middle scheduling strategies which improves upon a previous construction of Barak (FOCS 2002).

Annual Symposium on Foundations of Computer Science•Oct 1, 2010•96 citations

Geometry of Secure Two-party Computation

Saugata Basu, Hamidreza Amini Khorasgani, Hemanta K. Maji +1 more

What is the round and communication complexity of secure computation? The seminal results of Chor-Kushilevitz-Beaver (STOC-1989, FOCS-1989, DIMACS-1989) answer this question for computations with deterministic output. However, this question has remained unanswered for computations with randomized output. Our work answers this question for two-party secure function evaluation functionalities. We introduce a geometric encoding of all candidate secure protocols for a given computation as points in a high-dimensional space. The following results follow by analyzing the properties of these sets of points.1)It is decidable to determine if a given computation has a secure protocol within round or communication constraints.2)We construct one such protocol if it exists.3)Otherwise, we present an obstruction to achieving security.Our technical contributions imply new information complexity bounds for secure computation.

Annual Symposium on Foundations of Computer Science•Oct 1, 2022•4 citations

The Exact Round Complexity of Secure Computation.

Sanjam Garg, Pratyay Mukherjee, Omkant Pandey +1 more

We revisit the exact round complexity of secure computation in the multi-party and two-party settings. For the special case of two-parties without a simultaneous message exchange channel, this question has been extensively studied and resolved. In particular, Katz and Ostrovsky CRYPTO '04 proved that 5 rounds are necessary and sufficient for securely realizing every two-party functionality where both parties receive the output. However, the exact round complexity of general multi-party computation, as well as two-party computation with a simultaneous message exchange channel, is not very well understood. These questions are intimately connected to the round complexity of non-malleable commitments. Indeed, the exact relationship between the round complexities of non-malleable commitments and secure multi-party computation has also not been explored. In this work, we revisit these questions and obtain several new results. First, we establish the following main results. Suppose that there exists a k-round non-malleable commitment scheme, and let $$k'=\max 4,k+1$$k'=max4,k+1; then,Two-party setting with simultaneous message transmission: there exists a $$k'$$k'-round protocol for securely realizing every two-party functionality;Multi-party setting: there exists a $$k'$$k'-round protocol for securely realizing the multi-party coin-flipping functionality. As a corollary of the above results, by instantiating them with existing non-malleable commitment protocols from the literature, we establish that four rounds are both necessary and sufficient for both the results above. Furthermore, we establish that, for every multi-party functionalityfive rounds are sufficient. We actually obtain a variety of results offering trade-offs between rounds and the cryptographic assumptions used, depending upon the particular instantiations of underlying protocols.

•Jan 1, 2016•0 citations

Perfect Secure Computation in Two Rounds

Benny Applebaum, Zvika Brakerski, Rotem Tsabary

We show that any multiparty functionality can be evaluated using a 2-round protocol with perfect correctness and perfect semihonest security, provided that the majority of parties are honest. This settles the round complexity of information-theoretic semihonest multiparty computation, resolving a longstanding open question [Y. Ishai and E. Kushilevitz, Randomizing polynomials: A new representation with applications to round-efficient secure computation, in Proceedings of the 41st Annual Symposium on Foundations of Computer Science FOCS 2000, IEEE Computer Society, 2000, pp. 294--304]. The protocol is efficient for ${NC}^1$ functionalities. Furthermore, given black-box access to a one-way function, the protocol can be made efficient for any polynomial functionality, at the cost of only guaranteeing computational security. Our results are based on a new notion of multiparty randomized encoding which extends and relaxes the standard notion of randomized encoding of functions [Y. Ishai and E. Kushilevitz, Randomizing polynomials: A new representation with applications to round-efficient secure computation, in Proceedings of the 41st Annual Symposium on Foundations of Computer Science FOCS 2000, IEEE Computer Society, 2000, pp. 294--304]. The property of a multiparty randomized encoding (MPRE) is that if the functionality $g$ is an encoding of the functionality $f$, then for any (permitted) coalition of players, their respective outputs and inputs in $g$ allow them to simulate their respective inputs and outputs in $f$, without learning anything else, including the other outputs of $f$. We further introduce a new notion of effective degree, and show that the round complexity of a functionality $f$ is characterized by the degree of its MPRE. We construct degree-2 MPREs for general functionalities in several settings under different assumptions, and use these constructions to obtain 2-round protocols. Our constructions also give rise to new protocols in the client-server model with optimal round complexity.

SIAM Journal on Computing•Jan 1, 2021•7 citations
In STOC’05, von Ahn, Hopper and Langford introduced the notion of covert computation. In covert computation, a party runs a secure computation protocol over a covert (or steganographic) channel without knowing if the other parties are participating as well or not. At the end of the protocol, if all parties participated in the protocol and if the function output is “favorable ” to all parties, then the output is revealed (along with the fact that everyone participated). All covert computation protocols known so far require a large polynomial number of rounds. In this work, we first study the question of the round complexity of covert computation and obtain the following results: • There does not exist a constant round covert computation protocol with respect to black box simulation even for the case of two parties. (In comparison, such protocols are known even for the multi-party case if there is no covertness requirement.) • By relying on the two slot non-black-box simulation technique of Pass (STOC’04) and techniques from cryptography in NC 0 (Applebaum et al, FOCS’04), we obtain a construction of a constant round covert multi-party computation protocol. Put together, the above adds one more example to the growing list of tasks for which non-black-box simulation techniques (introduced in the work of Barak in FOCS’01) are necessary. Finally, we study the problem of covert multi-party computation in the setting where the parties only have point to point (covert) communication channels. We observe that our covert computation protocol for the broadcast channel inherits, from the protocol of Pass, the property of secure composition in the bounded concurrent setting. Then, as an application of this protocol, somewhat surprisingly we show the existence of covert multi-party computation with point to point channels (assuming that the number of parties is a constant). 0 1
In STOC'05, von Ahn, Hopper and Langford introduced the notion of covert computation. In covert computation, a party runs a secure computation protocol over a covert (or steganographic) channel without knowing if the other parties are participating as well or not. At the end of the protocol, if all parties participated in the protocol and if the function output is "favorable" to all parties, then the output is revealed (along with the fact that everyone participated). All covert computation protocols known so far require a large polynomial number of rounds. In this work, we first study the question of the round complexity of covert computation and obtain the following results: There does not exist a constant round covert computation protocol with respect to black box simulation even for the case of two parties. (In comparison, such protocols are known even for the multi-party case if there is no covertness requirement.) By relying on the two slot non-black-box simulation technique of Pass (STOC'04) and techniques from cryptography in NC0 (Applebaum et al, FOCS'04), we obtain a construction of a constant round covert multi-party computation protocol.
In STOC'05, Aim, Hopper and Longford introduced the notion of covert computation. A covert computation protocol is one in which parties am run a protocol without knowing if other parties ore also participating in the protocol or not. At the end of the protocol, if all parties participated in the protocol and if the function output is favorable to all parties, then the output is revealed. Ahn et al. constructed a protocol for covert two-partv computation in the random oracle model In this paper, we offer a construction for covert multiparty computation. Our construction is in the standard model and does not require random oracles. In order to achieve this goal, we introduce a number of new techniques. Central to our work is the development of "zero-knowledge proofs to garbled circuits," which we believe could be of independent interest. Along the way, we also develop a definition of covert computation as per the Ideal/Real model simulation paradigm.
We present round-efficient protocols for secure multi-party computation with a dishonest majority that rely on black-box access to the underlying primitives. Our main contributions are as follows: · a O(log* n)-round protocol that relies on black-box access to dense cryptosystems, homomorphic encryption schemes, or lossy encryption schemes. This improves upon the recent O(1)log* n-round protocol of Lin, Pass and Venkitasubramaniam (STOC 2009) that relies on non-black-box access to a smaller class of primitives. · a O(1)-round protocol requiring in addition, black-box access to a one-way function with sub-exponential hardness, improving upon the recent work of Pass and Wee (Eurocrypt 2010). These are the first black-box constructions for secure computation with sublinear round complexity. Our constructions build on and improve upon the work of Lin and Pass (STOC 2009) on nonmalleability amplification, as well as that of Ishai et al. (STOC 2006) on black-box secure computation. In addition to the results on secure computation, we also obtain a simple construction of a 0(log* n)-round non-malleable commitment scheme based on one-way functions, improving upon the recent O(1)log* n-round protocol of Lin and Pass (STOC 2009). Our construction uses a novel transformation for handling arbitrary man-in-the-middle scheduling strategies which improves upon a previous construction of Barak (FOCS 2002).
What is the round and communication complexity of secure computation? The seminal results of Chor-Kushilevitz-Beaver (STOC-1989, FOCS-1989, DIMACS-1989) answer this question for computations with deterministic output. However, this question has remained unanswered for computations with randomized output. Our work answers this question for two-party secure function evaluation functionalities. We introduce a geometric encoding of all candidate secure protocols for a given computation as points in a high-dimensional space. The following results follow by analyzing the properties of these sets of points.1)It is decidable to determine if a given computation has a secure protocol within round or communication constraints.2)We construct one such protocol if it exists.3)Otherwise, we present an obstruction to achieving security.Our technical contributions imply new information complexity bounds for secure computation.
We revisit the exact round complexity of secure computation in the multi-party and two-party settings. For the special case of two-parties without a simultaneous message exchange channel, this question has been extensively studied and resolved. In particular, Katz and Ostrovsky CRYPTO '04 proved that 5 rounds are necessary and sufficient for securely realizing every two-party functionality where both parties receive the output. However, the exact round complexity of general multi-party computation, as well as two-party computation with a simultaneous message exchange channel, is not very well understood. These questions are intimately connected to the round complexity of non-malleable commitments. Indeed, the exact relationship between the round complexities of non-malleable commitments and secure multi-party computation has also not been explored. In this work, we revisit these questions and obtain several new results. First, we establish the following main results. Suppose that there exists a k-round non-malleable commitment scheme, and let k′=max⁡4,k+1k'=\max 4,k+1k′=max4,k+1k'=max4,k+1; then,Two-party setting with simultaneous message transmission: there exists a k′k'k′k'-round protocol for securely realizing every two-party functionality;Multi-party setting: there exists a k′k'k′k'-round protocol for securely realizing the multi-party coin-flipping functionality. As a corollary of the above results, by instantiating them with existing non-malleable commitment protocols from the literature, we establish that four rounds are both necessary and sufficient for both the results above. Furthermore, we establish that, for every multi-party functionalityfive rounds are sufficient. We actually obtain a variety of results offering trade-offs between rounds and the cryptographic assumptions used, depending upon the particular instantiations of underlying protocols.
We show that any multiparty functionality can be evaluated using a 2-round protocol with perfect correctness and perfect semihonest security, provided that the majority of parties are honest. This settles the round complexity of information-theoretic semihonest multiparty computation, resolving a longstanding open question [Y. Ishai and E. Kushilevitz, Randomizing polynomials: A new representation with applications to round-efficient secure computation, in Proceedings of the 41st Annual Symposium on Foundations of Computer Science FOCS 2000, IEEE Computer Society, 2000, pp. 294--304]. The protocol is efficient for NC1{NC}^1NC1 functionalities. Furthermore, given black-box access to a one-way function, the protocol can be made efficient for any polynomial functionality, at the cost of only guaranteeing computational security. Our results are based on a new notion of multiparty randomized encoding which extends and relaxes the standard notion of randomized encoding of functions [Y. Ishai and E. Kushilevitz, Randomizing polynomials: A new representation with applications to round-efficient secure computation, in Proceedings of the 41st Annual Symposium on Foundations of Computer Science FOCS 2000, IEEE Computer Society, 2000, pp. 294--304]. The property of a multiparty randomized encoding (MPRE) is that if the functionality ggg is an encoding of the functionality fff, then for any (permitted) coalition of players, their respective outputs and inputs in ggg allow them to simulate their respective inputs and outputs in fff, without learning anything else, including the other outputs of fff. We further introduce a new notion of effective degree, and show that the round complexity of a functionality fff is characterized by the degree of its MPRE. We construct degree-2 MPREs for general functionalities in several settings under different assumptions, and use these constructions to obtain 2-round protocols. Our constructions also give rise to new protocols in the client-server model with optimal round complexity.