Tal Mor

TCS Journal 2020 Journal Article

Composable security against collective attacks of a modified BB84 QKD protocol with information only in one basis

• Michel Boyer
• Rotem Liss
• Tal Mor

Quantum Cryptography uses the counter-intuitive properties of Quantum Mechanics for performing cryptographic tasks in a secure and reliable way. The Quantum Key Distribution (QKD) protocol BB84 has been proven secure against several important types of attacks: collective attacks and joint attacks. Here we analyze the security of a modified BB84 protocol, for which information is sent only in the z basis while testing is done in both the z and the x bases, against collective attacks. The proof follows the framework of a previous paper [1], but it avoids a classical information-theoretical analysis and proves a fully composable security. We show that this modified BB84 protocol is as secure against collective attacks as the original BB84 protocol, and that it requires more bits for testing.

TCS Journal 2014 Journal Article

Preface

• Tal Mor
• Renato Renner

TCS Journal 2013 Journal Article

Preface

• Tal Mor
• Alain Tapp

TCS Journal 2006 Journal Article

Chosen ciphertext attacks on lattice-based public key encryption and modern (non-quantum) cryptography in a quantum environment

• Oleg Izmerly
• Tal Mor

Modern cryptography is based on various building blocks such as one way functions with or without trapdoors, pseudo-random functions, one way permutations with or without trapdoors, etc. In a quantum world some of the main candidates for these building blocks are broken. For instance, the security of the most popular public-key cryptosystem—RSA—is related to the difficulty of factoring large numbers, and is broken (in principle) by a quantum computer. We investigate some of the remaining candidates, and discuss the resulting “Post-Quantum Cryptography” (namely, the resulting “modern cryptography in a quantum environment”). About half a decade ago Ajtai and Dwork (and later on, also Goldreich, Goldwasser and Halevi) proposed a public key cryptosystem that has a proven security under a plausible complexity assumption. The plausible assumption is that the so-called unique shortest vector problem (u-SVP) is hard on the worst case. This problem is potentially still hard also in a quantum environment. Recently, Regev introduced a new (and much simpler) public key cryptosystem, based on the same u-SVP hardness assumption, but with improved parameters. In this paper we present chosen ciphertext attacks (CCA) against all three cryptosystems. Our attack shows that these cryptosystems are totally insecure against CCA, because the private keys can be recovered in polynomial time. We then discuss the possibility of making public key encryption (PKE) secure against CCA, without adding stronger assumptions than the assumption that u-SVP is hard. We conclude that the current understanding of modern cryptography in a quantum environment can only suggest CCA-secure interactive-PKE, which is obviously weaker than CCA-secure PKE. Finally, we discuss the relation of our attack to the reaction attack of Hall, Goldberg and Schneier, which we only recently became aware of.

TCS Journal 2004 Journal Article

Quantum computing without entanglement

• Eli Biham
• Gilles Brassard
• Dan Kenigsberg
• Tal Mor

It is generally believed that entanglement is essential for quantum computing. We present here a few simple examples in which quantum computing without entanglement is better than anything classically achievable, in terms of the reliability of the outcome after a fixed number of oracle calls. Using a separable (that is, unentangled) state, we show that the Deutsch–Jozsa problem and the Simon problem can be solved more reliably by a quantum computer than by the best possible classical algorithm, even probabilistic. We conclude that: (a)~entanglement is not essential for quantum computing; and (b)~some advantage of quantum algorithms over classical algorithms persists even when the quantum state contains an arbitrarily small amount of information—that is, even when the state is arbitrarily close to being totally mixed.

STOC Conference 2000 Conference Paper

A proof of the security of quantum key distribution (extended abstract)

• Eli Biham
• Michel Boyer
• P. Oscar Boykin
• Tal Mor
• Vwani P. Roychowdhury

FOCS Conference 1999 Conference Paper

On Universal and Fault-Tolerant Quantum Computing: A Novel Basis and a New Constructive Proof of Universality for Shor's Basis

• P. Oscar Boykin
• Tal Mor
• Matthew Pulver
• Vwani P. Roychowdhury
• Farrokh Vatan

A novel universal and fault-tolerant basis (set of gates) for quantum computation is described. Such a set is necessary to perform quantum computation in a realistic noisy environment. The new basis consists of two single-qubit gates (Hadamard and /spl sigma//sub z//sup 1/4 /) and one double-qubit gate (Controlled-NOT). Since the set consisting of Controlled-NOT and Hadamard gates is not universal, the new basis achieves universality by including only one additional elementary (in the sense that it does not include angles that are irrational multiples of /spl pi/) single-qubit gate, and hence, is potentially the simplest universal basis that one can construct. We also provide an alternative proof of universality for the only other known class of universal and fault-tolerant basis proposed by P. W. Shor (1996) and A. Y. Kitaev (1997).