Interactive Proofs For Quantum Computations (2008)
Aharonov, Dorit, Ben-Or, Michael, Eban, Elad
The widely held belief that BQP strictly contains BPP raises fundamental questions: Upcoming generations of quantum computers might already be too large to be simulated classically. Is it possible to...
Aharonov, Dorit, Ben-Or, Michael, Sattath, Or
Valiant-Vazirani showed in 1985 that solving NP with the promise that "yes" instances have only one witness is powerful enough to solve the entire NP class (under randomized reductions). We are...
Michael Ben-or, Shafi Goldwassert
Every function of n inputs can be efficiently computed by a complete network of n processors in such a way that:
Quantum Multi Prover Interactive Proofs with Communicating Provers (2008)
Ben-Or, Michael, Hassidim, Avinatan, Pilpel, Haran
Multi Prover Interactive Proof systems (MIPs)were first presented in a cryptographic context, but ever since they were used in various fields. Understanding the power of MIPs in the quantum context...
We present a fast quantum Byzantine Agreement protocol that can reach agreement in O(1) expected communication rounds against a strong full information, dynamic adversary, tolerating up to the...
1984 he was awarded the Israeli Government Alon Fellowship and he joined the faculty of the Hebrew University where he is currently a Senior Lecturer of
Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority (2008)
Ben-Or, Michael, Crépeau, Claude, Gottesman, Daniel, Hassidim, Avinatan, Smith, Adam
Secret sharing and multiparty computation (also called "secure function evaluation") are fundamental primitives in modern cryptography, allowing a group of mutually distrustful players to perform...
Dorit Aharonov, Michael Ben-or, Russell Impagliazzo, Noam Nisan
In this paper we study noisy reversible circuits. Noisy computation and reversible computation have been studied separately, and it is known that they are equivalent in power to unrestricted...
Detrimental Decoherence (2007)
Gil Kalai, Dorit Aharonov, Michael Ben-or, Greg Kuperberg
We propose and discuss two conjectures on the nature of informa-tion leaks (decoherence) for quantum computers. These conjectures, if (or when) they hold, are damaging for quantum error-correction as...
The universal composable security of quantum key distribution (2005)
Michael Ben-or, Debbie W. Leung, Dominic Mayers
The existing unconditional security definitions of quantum key distribution (QKD) do not apply to joint attacks over QKD and the subsequent use of the resulting key. In this paper, we close this...
General Security Definition and Composability for Quantum & Classical Protocols (2004)
Ben-Or, Michael, Mayers, Dominic
We generalize the universally composable definition of Canetti to the Quantum World. The basic idea is the same as in the classical world. The main contribution is that we unfold the result in a new...
Resilient-optimal interactive consistency in constant time (2003)
For a complete network of n processors within which communication lines are private, we show how to achieve concurrently many Byzantine Agreements within constant expected time both on synchronous...
Resilient-optimal interactive consistency in constant time (2003)
For a complete network of n processors within which communication lines are private, we show how to achieve concurrently many Byzantine Agreements within constant expected time both on synchronous...
Increasing the Power of the Dealer in Non-interactive ZeroKnowledge Proof Systems (2000)
Danny Gutfreund, Michael Ben-or
Abstract. We introduce weaker models for non-interactive zero knowledge, in which the dealer is not restricted to deal a truly random string and may also have access to the input to the protocol...
Fault-Tolerant Quantum Computation With Constant Error Rate (1999)
Aharonov, Dorit, Ben-Or, Michael
This paper proves the threshold result, which asserts that quantum computation can be made robust against errors and inaccuracies, when the error rate, $\eta$, is smaller than a constant threshold,...
A Tight Lower Bound for Randomized Synchronous Consensus (1999)
Ziv Bar-joseph, Michael Ben-or
We prove tight upper and lower bounds of \Theta(t= n) on the expected number of rounds needed for randomized synchronous consensus protocols for a fail-stop, full information, adaptive adversary. In...
Polynomial Simulations of Decohered Quantum Computers (1996)
Aharonov, Dorit, Ben-Or, Michael
We define formally decohered quantum computers (using density matrices), and present a simulation of them by a probabalistic classical Turing Machine. We study the slowdown of the simulation for two...
Fault Tolerant Quantum Computation with Constant Error (1996)
Aharonov, Dorit, Ben-Or, Michael
Recently Shor showed how to perform fault tolerant quantum computation when the error probability is logarithmically small. We improve this bound and describe fault tolerant quantum computation when...
Polynomial simulations of decohered quantum computers (1996)
Dorit Aharonov, Michael Ben-or
Recently it has become clear, that a key issue in quantum computation is understanding how interaction with the environment, or "decoherence", effects the computational power of...
Agreement In the Presence of Faults, On Networks of Bounded Degree (1996)
We present networks of bounded degree and a fully polynomial almost everywhere agreement scheme which tolerate, with high probability, randomly located faulty processors, where processors fail...