## CryptoDB

### Louis Salvail

#### Affiliation: University of Montreal, Canada

#### 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.

2018

TCC

Secure Certification of Mixed Quantum States with Application to Two-Party Randomness Generation
Abstract

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

2007

EPRINT

Secure Identification and QKD in the Bounded-Quantum-Storage Model
Abstract

We consider the problem of secure identification: user U proves to server S that he knows an agreed (possibly low-entropy) password w, while giving away as little information on w as possible, namely the adversary can exclude at most one possible password for each execution of the scheme. We propose a solution in the bounded-quantum-storage model, where U and S may exchange qubits, and a dishonest party is assumed to have limited quantum memory. No other restriction is posed upon the adversary.
An improved version of the proposed identification scheme is also secure against a man-in-the-middle attack, but requires U and S to additionally share a high-entropy key k. However, security is still guaranteed if one party loses k to the attacker but notices the loss. In both versions of the scheme, the honest participants need no quantum memory, and noise and imperfect quantum sources can be tolerated. The schemes compose sequentially, and w and k can securely be re-used.
A small modification to the identification scheme results in a quantum-key-distribution (QKD) scheme, secure in the bounded-quantum-storage model, with the same re-usability properties of the keys, and without assuming authenticated channels. This is in sharp contrast to known QKD schemes (with unbounded adversary) without authenticated channels, where authentication keys must be updated, and unsuccessful executions can cause the parties to run out of keys.

2007

EPRINT

A Tight High-Order Entropic Quantum Uncertainty Relation With Applications
Abstract

We derive a new entropic quantum uncertainty relation involving min-entropy. The relation is tight and can be applied in various quantum-cryptographic settings.
Protocols for quantum 1-out-of-2 Oblivious Transfer and quantum Bit Commitment are presented and the uncertainty relation is used to prove the security of these protocols in the bounded-quantum-storage model according to new strong security definitions.
As another application, we consider the realistic setting of Quantum Key Distribution (QKD) against quantum-memory-bounded eavesdroppers. The uncertainty relation allows to prove the security of QKD protocols in this setting while tolerating considerably higher error rates compared to the standard model with unbounded adversaries. For instance, for the six-state protocol with one-way communication, a bit-flip error rate of up to 17% can be tolerated (compared to 13% in the standard model).
Our uncertainty relation also yields a lower bound on the min-entropy key uncertainty against known-plaintext attacks when quantum ciphers are composed. Previously, the key uncertainty of these ciphers was only known with respect to Shannon entropy.

2005

EPRINT

Cryptography In the Bounded Quantum-Storage Model
Abstract

We initiate the study of two-party cryptographic primitives with unconditional security, assuming that the adversary's {\em quantum}memory is of bounded size. We show that oblivious transfer and bit
commitment can be implemented in this model using protocols where honest parties need no quantum memory, whereas an adversarial player needs quantum memory of size at least $n/2$ in order to break the protocol, where $n$ is the number of qubits transmitted. This is in sharp contrast to the classical bounded-memory model, where we can only tolerate adversaries with memory of size quadratic in honest players' memory size. Our protocols are efficient, non-interactive and can be implemented using today's technology. On the technical side, a new entropic uncertainty relation involving min-entropy is established.

2005

EPRINT

Oblivious Transfer and Linear Functions
Abstract

We study unconditionally secure 1-out-of-2 Oblivious Transfer (1-2 OT). We first point out that a standard security requirement for 1-2 OT of bits, namely that the receiver only learns one of the bits sent, holds if and only if the receiver has no information on the XOR of the two bits. We then generalize this to 1-2 OT of strings and show that the security can be characterized in terms of binary linear functions. More precisely, we show that the receiver learns only one of the two strings sent if and only if he has no information on the result of
applying any binary linear function (which non-trivially depends on both inputs) to the two strings.
We then argue that this result not only gives new insight into the nature of 1-2 OT, but it in particular provides a very powerful tool for analyzing 1-2 OT protocols. We demonstrate this by showing that with our characterization at hand, the reduceability of 1-2 OT (of strings) to a wide range of weaker primitives follows by a very simple argument. This is in sharp contrast to previous literature, where reductions of 1-2 OT to weaker flavors have rather complicated and sometimes even incorrect proofs.

2004

EUROCRYPT

2004

EPRINT

On the Key-Uncertainty of Quantum Ciphers and the Computational Security of One-way Quantum Transmission
Abstract

We consider the scenario where Alice wants to send a secret(classical) $n$-bit message to Bob using a classical key, and where
only one-way transmission from Alice to Bob is possible. In this
case, quantum communication cannot help to obtain perfect secrecy
with key length smaller then $n$. We study the question of whether
there might still be fundamental differences between the case where
quantum as opposed to classical communication is used. In this
direction, we show that there exist ciphers with perfect security producing quantum ciphertext where, even if an adversary knows the
plaintext and applies an optimal measurement on the ciphertext, his
Shannon uncertainty about the key used is almost maximal. This is in
contrast to the classical case where the adversary always learns $n$
bits of information on the key in a known plaintext attack. We also
show that there is a limit to how different the classical and
quantum cases can be: the most probable key, given matching plain-
and ciphertexts, has the same probability in both the quantum and
the classical cases. We suggest an application of our results in
the case where only a short secret key is available and the message
is much longer.

1999

EUROCRYPT

#### Program Committees

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

#### Coauthors

- Charles H. Bennett (2)
- François Bessette (2)
- Gilles Brassard (5)
- Claude Crépeau (4)
- Ivan Damgård (14)
- Paul Dumais (2)
- Frédéric Dupuis (4)
- Serge Fehr (13)
- Peter Høyer (2)
- Kassem Kalach (2)
- Marc Kaplan (2)
- Joe Kilian (1)
- Frédéric Légaré (1)
- Philippe Lamontagne (2)
- Sophie Laplante (2)
- Carolin Lunemann (1)
- Dominic Mayers (2)
- Kirill Morozov (1)
- Jesper Buus Nielsen (2)
- Thomas Brochmann Pedersen (3)
- Renato Renner (2)
- Christian Schaffner (9)
- Jean-Raymond Simard (1)
- John A. Smolin (2)
- Miroslava Sotáková (1)
- Alain Tapp (1)