Gilles Brassard

TCS Journal 2024 Journal Article

On computable numbers, with an application to the Druckproblem

• Sophie Berthelette
• Gilles Brassard
• Xavier Coiteux-Roy

In the famous paper in which he introduced what is now known as the Turing machine, Alan Turing gave a definition of computable real numbers under which it turns out that multiplication by 3 is uncomputable. This shortcoming vanished in a Correction to his paper that Turing himself published shortly afterwards, but it clearly illustrates the subtlety of defining computability issues correctly. In this paper, we give the name “printable” to real numbers that Turing originally called “computable”, we recall what is now the generally accepted definition of computable real numbers (which is not quite Turing's amended definition, but is equivalent to it), and we contrast the two notions. Despite the fact that the multiplication by 3 of printable numbers is uncomputable, as opposed to the same operation on computable numbers, a real number is computable if and only if it is printable. The resolution of this apparent paradox is that no machine can transform the “computable” description of a real number to its “printable” description, as Turing proved in his Correction. Finally, we address the subtle issue of allowing or not the printable description of a real number to end with an infinite sequence of 9s (or of 1s in binary), which was left open by Turing in his Correction. Several of these results were already known, as they appear in scattered places, some in non-refereed publications, but we give a unified treatment with some different proofs and a historical perspective.

FOCS Conference 2014 Conference Paper

Noisy Interactive Quantum Communication

• Gilles Brassard
• Ashwin Nayak 0001
• Alain Tapp
• Dave Touchette
• Falk Unger

We study the problem of simulating protocols in a quantum communication setting over noisy channels. This problem falls at the intersection of quantum information theory and quantum communication complexity, and will be of importance for eventual real-world applications of interactive quantum protocols, which can be proved to have exponentially lower communication costs than their classical counterparts for some problems. These are the first results concerning the quantum version of this problem, originally studied by Schulman in a classical setting (FOCS '92, STOC '93). We simulate a length N quantum communication protocol by a length O(N) protocol with arbitrarily small error. Our simulation strategy has a far higher communication rate than a naive one that encodes separately each particular round of communication to achieve comparable success. Such a strategy would have a communication rate going to 0 in the worst interaction case as the length of the protocols increases, in contrast to our strategy, which has a communication rate proportional to the capacity of the channel used. Under adversarial noise, our strategy can withstand, for arbitrarily small ε > 0, error rates as high as 1/2 -- ε when parties preshare perfect entanglement, but the classical channel is noisy. We show that this is optimal. Note that in this model, the naive strategy would not work for any constant fraction of errors. We provide extension of these results in several other models of communication, including when also the entanglement is noisy, and when there is no pre-shared entanglement but communication is quantum and noisy. We also study the case of random noise, for which we provide simulation protocols with positive communication rates and no pre-shared entanglement over some quantum channels with quantum capacity Q = 0, proving that Q is in general not the right characterization of a channel's capacity for interactive quantum communication. Our results are stated for a general quantum communication protocol in which Alice and Bob collaborate, and hold in particular in the quantum communication complexity settings of the Yao and Cleve-Buhrman models.

TCS Journal 2014 Journal Article

Quantum cryptography: Public key distribution and coin tossing

• Charles H. Bennett
• Gilles Brassard

TCS Journal 2013 Journal Article

Classical, quantum and nonsignalling resources in bipartite games

• Gilles Brassard
• Anne Broadbent
• Esther Hänggi
• André Allan Méthot
• Stefan Wolf

We study bipartite games that arise in the context of nonlocality with the help of graph theory. Our main results are alternate proofs that deciding whether a no-communication classical winning strategy exists for certain games (called forbidden-edge and covering games) is NP-complete, while the problem of deciding if these games admit a nonsignalling winning strategy is in P. We discuss relations between quantum winning strategies and orthogonality graphs. We also show that every pseudotelepathy game yields both a proof of the Bell–Kochen–Specker theorem and an instance of a two-prover interactive proof system that is classically sound, but that becomes unsound when provers use shared entanglement.

TCS Journal 2013 Journal Article

Strict hierarchy among Bell Theorems

• Gilles Brassard
• André Allan Méthot

As demonstrated by John Bell, quantum mechanics exhibits correlations in spacelike separated bipartite systems that are impossible to reproduce by classical means. There are three levels of “Bell Theorems”, depending on which aspects of the quantum correlations can or cannot be reproduced classically. The original “Bell Inequalities” (BI) require a perfect classical simulation of all quantum probabilities. With “Bell Theorems Without Inequalities” (BTWI), we ask the classical simulation to be able to produce precisely the outcomes that could occur according to quantum mechanics, but we do not worry about their exact probabilities. With “Pseudotelepathy” (PT), we are satisfied if the classical simulation produces only outcomes allowed by quantum mechanics, but not necessarily all of them. Bell’s original proof of BI involved a maximally entangled 2 × 2 bipartite state such as the singlet state. Hardy proved that BTWI are possible in dimension 2 × 2, but his construction used a non-maximally entangled state. Here, we prove that no 2 × 2 maximally entangled state can serve to produce BTWI. Combining this with our earlier result that 2 × 2 entangled states cannot be used at all for the purpose of PT, it follows a strict hierarchy on the quantum resources that are required to exhibit the various levels of Bell Theorems.

ICML Conference 2007 Conference Paper

Quantum clustering algorithms

• Esma Aïmeur
• Gilles Brassard
• Sébastien Gambs

By the term "quantization", we refer to the process of using quantum mechanics in order to improve a classical algorithm, usually by making it go faster. In this paper, we initiate the idea of quantizing clustering algorithms by using variations on a celebrated quantum algorithm due to Grover. After having introduced this novel approach to unsupervised learning, we illustrate it with a quantized version of three standard algorithms: divisive clustering, k -medians and an algorithm for the construction of a neighbourhood graph. We obtain a significant speedup compared to the classical approach.

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.

FOCS Conference 1993 Conference Paper

A Quantum Bit Commitment Scheme Provably Unbreakable by both Parties

• Gilles Brassard
• Claude Crépeau
• Richard Jozsa
• Denis Langlois

We describe a complete protocol for bit commitment based on the transmission of polarized photons. We show that under the laws of quantum physics, this protocol cannot be cheated by either party except with exponentially small probability (exponential in the running time needed to implement the honest protocol). A more thorough analysis is required to adjust all the constants used in this paper to get the best performance from our construction. Better performances may probably be achieved by using a third conjugate transmission-reception basis of circular polarization. >

TCS Journal 1991 Journal Article

Constant-round perfect zero-knowledge computationally convincing protocols

• Gilles Brassard
• Claude Crépeau
• Moti Yung

A perfect zero-knowledge interactive protocol allows a prover to convince a verifier of the validity of a statement in a way that does not give the verifier any additional information. Such protocols take place by the exchange of messages back and forth between the prover and the verifier. An important measure of efficiency for these protocols is the number of rounds in the interaction. In previously known perfect zero-knowledge protocols for statements concerning NP-complete problems, at least k rounds were necessary in order to prevent one party from having a probability of undetected cheating greater than 2−k. In this paper, we give the first perfect zero-knowledge protocol that offers arbitrarily high security for any statement in NP with a constant number of rounds. The protocol is computationally convincing (rather than statistically convincing as would have been an interactive proof-system in the sense of Goldwasser, Micali and Rackoff) because the verifier's belief in the prover's claim is partly based on the assumption that it is feasible to find a prime p with known factorization of p − 1 such that it is infeasible to compute discrete logarithms modulo p even for someone who knows the factors of p − 1. Our protocol can also be based on the more general assumption that one-way certified group actions exist. It is still open whether it would be sufficient to assume the existence of one-way functions in order to obtain perfect zero-knowledge computationally convincing interactive protocols for all statements in NP.

FOCS Conference 1991 Conference Paper

Subquadratic Zero-Knowledge

• Joan Boyar
• Gilles Brassard
• René Peralta 0001

The communication complexity of zero-knowledge proof systems is improved. Let C be a Boolean circuit of size n. Previous zero-knowledge proof systems for the satisfiability of C require the use of Omega (kn) bit commitments in order to achieve a probability of undetected cheating not greater than 2/sup -k/. In the case k=n, the communication complexity of these protocols is therefore Omega (n/sup 2/) bit commitments. A zero-knowledge proof is given for achieving the same goal with only O(n/sup m/+k square root n/sup m/) bit commitments, where m=1+ epsilon /sub n/ and epsilon /sub n/ goes to zero as n goes to infinity. In the case k=n, this is O(n square root n/sup m/). Moreover, only O(k) commitments need ever be opened, which is interesting if committing to a bit is significantly less expensive than opening a commitment. >

FOCS Conference 1986 Conference Paper

Information Theoretic Reductions among Disclosure Problems

• Gilles Brassard
• Claude Crépeau
• Jean-Marc Robert 0001

Alice disposes of some number of secrets. She is willing to disclose one of them to Bob. Although she agrees to let him choose which secret he wants, she is not willing to allow him to gain any information on more than one secret. On the other hand, Bob does not want Alice to know which secret he wishes. An all-or-nothing disclosure is one by which, as soon as Bob has gained any information whatsoever on one of Alice's secrets, he has wasted his chances to learn anything about the other secrets. We assume that Alice is honest when she claims to be willing to disclose one secret to Bob (i. e. she is not about to send junk). The only cheating Alice is susceptible of trying is to figure out which secret is of interest to Bob. We address the following question from an information theoretic point of view: what is the most elementary disclosure problem? The main result is that the general all-or-nothing disclosure of secrets is equivalent to a much simpler problem, which we call the two-bit problem.

FOCS Conference 1986 Conference Paper

Non-Transitive Transfer of Confidence: A Perfect Zero-Knowledge Interactive Protocol for SAT and Beyond

• Gilles Brassard
• Claude Crépeau

A perfect zero-knowledge interactive proof is a protocol by which Alice can convince Bob of the truth of some theorem in a way that yields no information as to how the proof might proceed (in the sense of Shannon's information theory). We give a general technique for achieving this goal for any problem in NP (and beyond). The fact that our protocol is perfect zero-knowledge does not depend on unproved cryptographic assumptions. Furthermore, our protocol is powerful enough to allow Alice to convince Bob of theorems for which she does not even have a proof. Whenever Alice can convince herself probabilistically of a theorem, perhaps thanks to her knowledge of some trap-door information, she can convince Bob as well without compromising the trap-door in any way. This results in a non-transitive transfer of confidence from Alice to Bob, because Bob will not be able to subsequently convince someone else that the theorem is true. Our protocol is dual to those of [GMW1, BC].

FOCS Conference 1980 Conference Paper

A Time-Luck Tradeoff in Cryptography

• Gilles Brassard

New definitions are proposed for the security of Transient-Key Cryptography (a variant on Public-Key Cryptography) that account for the possibility of super-polynomial-time, Monte Carlo cryptanalytic attacks. The basic question we address is: how can one relate the amount of time a cryptanalyst is willing to spend decoding cryptograms to his likelihood of success? This question and others are partially answered in a relativized model of computation in which there provably exists a transient-key cryptosystem such that even a cryptanalyst willing to spend as much as (almost) O(2n/log n) steps on length n cryptograms cannot hope to break but an exponentially small fraction of them, even if he is allowed to make use of a true random bit generator.

FOCS Conference 1979 Conference Paper

Relativized Cryptography

• Gilles Brassard

It seems very difficult to give a formal definition of computational security for Public Key Cryptography. We define a slightly different notion, called Transient-Key Cryptography, for which a natural definition of security against chosen-plaintext-attacks can be given. The main result presented here is the existence of a relativized model of computation under which there exists a provably secure transientkey cryptosystem. Indeed, there exists a computable oracle that can be used by cryptographers to efficiently encipher and decipher messages, yet it is of no help to the cryptanalyst trying to decode messages not intended for him. As a corollary, there exists a length-preserving permutation, the inverse of which is hard to compute on most elements of its domain even if arbitrary evaluations of the function itself are allowed for free.