We provide the first proof of that for every language L isin NP there exists an O(1)-round computational zero-knowledge argument with polynomial precision for L. Our result assumes that ratio of running-time of any adversary verifier in some same verifier round of any two different executions of the argument is bounded by nalpha, where n is secure parameter and alpha is any predeterminate constant. Such verifiers are called restricted verifiers. Precise zero-knowledge was introduced by Micali and Pass in STOC'06 (They used the term "local zero-knowledge" there.) and they constructed some omega(1)-round polynomial/linear precise zero- knowledge protocols for NP and hence left an open problem how to construct O(1)-round polynomial/linear precise zero-knowledge protocols. By providing a precise simulator for Barak's O(1)-round non-black-box zero-knowledge argument, we prove that the argument is polynomial precise.
Although the semi-honest model is reasonable in some cases, it is unrealistic to assume that adversaries will al- ways follow the protocols exactly. In particular, malicious adversaries could deviate arbitrarily from their prescribed protocols. Clearly, protocols that can withstand malicious adversaries provide more security. However, there is an ob- vious trade-off: protocols that are secure against malicious adversaries are generally more expensive than those secure against semi-honest adversaries only. In this paper, our goal is to make an analysis of trade-offs between perfor- mance and security in privacy-preserving distributed data mining algorithms in the two models. In order to make a realistic comparison, we enhance commonly used subpro- tocols that are secure in the semi-honest model with zero knowledge proofs to be secure in the malicious model. We compare the performance of these protocols in both models.
Nishanth Chandran, Vipul Goyal, Rafail Ostrovsky, Amit Sahai
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.