International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Louis Salvail

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.
2018
TCC
Secure Certification of Mixed Quantum States with Application to Two-Party Randomness Generation
We investigate sampling procedures that certify that an arbitrary quantum state on n subsystems is close to an ideal mixed state $$\varphi ^{\otimes n}$$ for a given reference state $$\varphi $$, up to errors on a few positions. This task makes no sense classically: it would correspond to certifying that a given bitstring was generated according to some desired probability distribution. However, in the quantum case, this is possible if one has access to a prover who can supply a purification of the mixed state.In this work, we introduce the concept of mixed-state certification, and we show that a natural sampling protocol offers secure certification in the presence of a possibly dishonest prover: if the verifier accepts then he can be almost certain that the state in question has been correctly prepared, up to a small number of errors.We then apply this result to two-party quantum coin-tossing. Given that strong coin tossing is impossible, it is natural to ask “how close can we get”. This question has been well studied and is nowadays well understood from the perspective of the bias of individual coin tosses. We approach and answer this question from a different—and somewhat orthogonal—perspective, where we do not look at individual coin tosses but at the global entropy instead. We show how two distrusting parties can produce a common high-entropy source, where the entropy is an arbitrarily small fraction below the maximum.
2017
EUROCRYPT
2016
CRYPTO
2012
CRYPTO
2011
CRYPTO
2011
ASIACRYPT
2010
CRYPTO
2009
ASIACRYPT
2009
CRYPTO
2007
CRYPTO
2007
CRYPTO
2006
CRYPTO
2005
CRYPTO
2004
CRYPTO
2004
EUROCRYPT
2004
TCC
2004
TCC
2001
EUROCRYPT
2000
EUROCRYPT
1999
EUROCRYPT
1998
CRYPTO
1995
EUROCRYPT
1993
EUROCRYPT
1992
JOFC
1990
EUROCRYPT

Program Committees

Eurocrypt 2018
Eurocrypt 2017
Crypto 2005
Eurocrypt 2005
TCC 2005
Eurocrypt 2001