Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Mohammad Mahmoody:

TR13-137 | 29th September 2013
Mohammad Mahmoody, Hemanta Maji, Manoj Prabhakaran

On the Power of Public-key Encryption in Secure Computation

We qualitatively separate semi-honest secure computation of non-trivial secure-function evaluation (SFE) functionalities from existence of key-agreement protocols.
Technically, we show the existence of an oracle (namely, PKE-oracle) relative to which key-agreement protocols exist; but it is useless for semi-honest secure realization of symmetric 2-party (deterministic finite) SFE functionalities, i.e. any ... more >>>

TR12-065 | 16th May 2012
Mohammad Mahmoody, Hemanta Maji, Manoj Prabhakaran

Limits of Random Oracles in Secure Computation

Revisions: 2

The seminal result of Impagliazzo and Rudich (STOC 1989) gave a black-box separation between one-way functions and public-key encryption: informally, a public-key encryption scheme cannot be constructed using one-way functions as the sole source of computational hardness. In addition, this implied a black-box separation between one-way functions and protocols for ... more >>>

TR12-052 | 27th April 2012
Mohammad Mahmoody, David Xiao

Languages with Efficient Zero-Knowledge PCPs are in SZK

A Zero-Knowledge PCP (ZK-PCP) is a randomized PCP such that the view of any (perhaps cheating) efficient verifier can be efficiently simulated up to small statistical distance. Kilian, Petrank, and Tardos (STOC '97) constructed ZK-PCPs for all languages in $NEXP$. Ishai, Mahmoody, and Sahai (TCC '12), motivated by cryptographic applications, ... more >>>

TR10-020 | 19th February 2010
Vipul Goyal, Yuval Ishai, Mohammad Mahmoody, Amit Sahai

Interactive Locking, Zero-Knowledge PCPs, and Unconditional Cryptography

Motivated by the question of basing cryptographic protocols on stateless tamper-proof hardware tokens, we revisit the question of unconditional two-prover zero-knowledge proofs for $NP$. We show that such protocols exist in the {\em interactive PCP} model of Kalai and Raz (ICALP '08), where one of the provers is replaced by ... more >>>

TR10-001 | 30th December 2009
Iftach Haitner, Mohammad Mahmoody, David Xiao

A New Sampling Protocol and Applications to Basing Cryptographic Primitives on the Hardness of $NP$

We investigate the question of what languages can be decided efficiently with the help of a recursive collision-finding oracle. Such an oracle can be used to break collision-resistant hash functions or, more generally, statistically hiding commitments. The oracle we consider, $Sam_d$ where $d$ is the recursion depth, is based on ... more >>>

TR09-139 | 17th December 2009
Mohammad Mahmoody, David Xiao

On the Power of Randomized Reductions and the Checkability of SAT

Revisions: 3

The closure of complexity classes is a elicate question and the answer varies depending on the type of reduction considered. The closure of most classes under many-to-one (Karp) reductions is clear, but the question becomes complicated when oracle (Cook) reductions are allowed, and even more so when the oracle reductions ... more >>>

ISSN 1433-8092 | Imprint