CryptoDB
Gilles Brassard
NOTE: imports for ToSC and TCHES are no longer functioning.
Publications
Year
Venue
Title
2019
JOFC
Key Establishment à la Merkle in a Quantum World
Abstract
In 1974, Ralph Merkle proposed the first unclassified protocol for secure communications over insecure channels. When legitimate communicating parties are willing to spend an amount of computational effort proportional to some parameter N , an eavesdropper cannot break into their communication without spending a time proportional to $$N^2$$ N 2 , which is quadratically more than the legitimate effort. In a quantum world, however, Merkle’s protocol is immediately broken by Grover’s algorithm, but it is easily repaired if we are satisfied with a quantum protocol against which a quantum adversary needs to spend a time proportional to $$N^{3/2}$$ N 3 / 2 in order to break it. Can we do better? We give two new key establishment protocols in the spirit of Merkle’s. The first one, which requires the legitimate parties to have access to a quantum computer, resists any quantum adversary who is not willing to make an effort at least proportional to $$N^{5/3}$$ N 5 / 3 , except with vanishing probability. Our second protocol is purely classical, yet it requires any quantum adversary to work asymptotically harder than the legitimate parties, again except with vanishing probability. In either case, security is proved for a typical run of the protocols: the probabilities are taken over the random (or quantum) choices made by the legitimate participants in order to establish their key as well as over the random (or quantum) choices made by the adversary who is trying to be privy to it.
1989
EUROCRYPT
1987
CRYPTO
Program Committees
- Crypto 1997
- Crypto 1989 (Program chair)
- Crypto 1988
Coauthors
- Pierre Beauchemin (4)
- Samy Bengio (1)
- Charles H. Bennett (6)
- François Bessette (2)
- Gilles Brassard (29)
- Seth Breidbard (1)
- Anne Broadbent (1)
- Claude Crépeau (10)
- Ivan Damgård (1)
- Yvo Desmedt (1)
- Joseph Fitzsimons (1)
- Sébastien Gambs (1)
- Claude Goutier (2)
- Peter Høyer (2)
- Kassem Kalach (2)
- Marc Kaplan (2)
- Sophie Laplante (2)
- Norbert Lütkenhaus (1)
- Tal Mor (1)
- Carl Pomerance (1)
- Jean-Jacques Quisquater (1)
- Jean-Marc Robert (2)
- Louis Salvail (5)
- Barry C. Sanders (1)
- Marie-Hélène Skubiszewska (1)
- John A. Smolin (2)
- Alain Tapp (1)
- Stephen Wiesner (1)
- Stefan Wolf (1)
- Moti Yung (2)