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, 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, 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, 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.
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 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 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.
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).
We present a round-efficient black-box construction of a general multi-party computation (MPC) protocol that satisfies composability in the plain model. The security of our protocol is proven in the angel-based UC framework [Prabhakaran and Sahai, STOC’04] under the minimal assumption of the existence of semi-honest oblivious transfer protocols. The round complexity of our protocol is max(O(log2n),O(ROT))
when the round complexity of the underlying oblivious transfer protocol is ROT
. Since constant-round semi-honest oblivious transfer protocols can be constructed under standard assumptions (such as the existence of enhanced trapdoor permutations), our result gives a O(log2n)
-round protocol under these assumptions. Previously, only an O(max(nϵ,ROT))
-round protocol was shown, where ϵ>0
is an arbitrary constant. We obtain our MPC protocol by constructing a O(log2n)
-round CCA-secure commitment scheme in a black-box way under the assumption of the existence of one-way functions.