International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Gilles Brassard

Publications

Year
Venue
Title
2019
JOFC
Key Establishment à la Merkle in a Quantum World
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.
2011
CRYPTO
2007
ASIACRYPT
2003
JOFC
2000
EUROCRYPT
1997
CRYPTO
1997
EUROCRYPT
1996
EPRINT
Oblivious Transfers and Intersecting Codes
Gilles Brassard Claude Crépeau Miklos Santha
Assume A owns t secret k-bit strings. She is willing to disclose one of them to B, at his choosing, provided he does not learn anything about the other strings. Conversely, B does not want A to learn which secret he chose to learn. A protocol for the above task is said to implement One-out-of-t String Oblivious Transfer. An apparently simpler task corresponds to the case k=1 and t=2 of two one-bit secrets: this is known as One-out-of-two Bit OT. We address the question of implementing the former assuming the existence of the later. In particular, we prove that the general protocol can be implemented from O(tk) calls to One-out-of-two Bit OT. This is optimal up to a small multiplicative constant. Our solution is based on the notion of self-intersecting codes. Of independent interest, we give several efficient new constructions for such codes. Another contribution of this paper is a set of information-theoretic definitions for correctness and privacy of unconditionally-secure oblivious transfer.
1993
EUROCRYPT
1992
JOFC
1991
CRYPTO
1991
JOFC
1990
CRYPTO
1990
CRYPTO
1990
EUROCRYPT
1989
EUROCRYPT
1989
EUROCRYPT
1989
EUROCRYPT
1988
CRYPTO
1988
JOFC
1988
JOFC
1987
CRYPTO
1986
CRYPTO
1986
CRYPTO
1986
CRYPTO
1985
CRYPTO
1984
CRYPTO
1982
CRYPTO
1982
CRYPTO
1981
CRYPTO

Program Committees

Crypto 1997
Crypto 1989 (Program chair)
Crypto 1988