International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Christian Schaffner

Affiliation: QuSoft and University of Amsterdam

Publications

Year
Venue
Title
2018
EUROCRYPT
2017
ASIACRYPT
2016
CRYPTO
2016
CRYPTO
2015
EPRINT
2011
CRYPTO
2011
ASIACRYPT
2010
EPRINT
Random Oracles in a Quantum World
Once quantum computers reach maturity most of today’s traditional cryptographic schemes based on RSA or discrete logarithms become vulnerable to quantum-based attacks. Hence, schemes which are more likely to resist quantum attacks like lattice-based systems or code-based primitives have recently gained significant attention. Interestingly, a vast number of such schemes also deploy random oracles, which have mainly be analyzed in the classical setting. Here we revisit the random oracle model in cryptography in light of quantum attackers. We show that there are protocols using quantum-immune primitives and random oracles, such that the protocols are secure in the classical world, but insecure if a quantum attacker can access the random oracle via quantum states. We discuss that most of the proof techniques related to the random oracle model in the classical case cannot be transferred immediately to the quantum case. Yet, we show that “quantum random oracles” can nonetheless be used to show for example that the basic Bellare-Rogaway encryption scheme is quantum-immune against plaintext attacks (assuming quantum-immune primitives).
2009
TCC
2009
ASIACRYPT
2009
CRYPTO
2008
TCC
2007
CRYPTO
2007
CRYPTO
2007
EPRINT
Randomness Extraction via Delta-Biased Masking in the Presence of a Quantum Attacker
Serge Fehr Christian Schaffner
Randomness extraction is of fundamental importance for information-theoretic cryptography. It allows to transform a raw key about which an attacker has some limited knowledge into a fully secure random key, on which the attacker has essentially no information. We show a new randomness-extraction technique which works also in case where the attacker has quantum information on the raw key. Randomness extraction is done by XORing a so-called delta-biased mask to the raw key. Up to date, only very few techniques are known to work against a quantum attacker, much in contrast to the classical (non-quantum) setting, which is much better understood and for which a vast amount of different techniques for randomness extraction are known. We show two applications of the new result. We first show how to encrypt a long message with a short key, information-theoretically secure against a quantum attacker, provided that the attacker has enough quantum uncertainty on the message. This generalizes the concept of entropically-secure encryption to the case of a quantum attacker. As a second application, we show how the new randomness-extraction technique allows to do error-correction without leaking partial information to a quantum attacker. Such a technique is useful in settings where the raw key may contain errors, since standard error-correction techniques may provide the attacker with information on, say, a secret key that was used to obtain the raw key.
2007
EPRINT
Secure Identification and QKD in the Bounded-Quantum-Storage Model
Ivan Damgård Serge Fehr Louis Salvail Christian Schaffner
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
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.
2006
CRYPTO
2006
EUROCRYPT
2006
EPRINT
Information-Theoretic Conditions for Two-Party Secure Function Evaluation
The standard security definition of unconditional secure function evaluation, which is based on the ideal/real model paradigm, has the disadvantage of being overly complicated to work with in practice. On the other hand, simpler ad-hoc definitions tailored to special scenarios have often been flawed. Motivated by this unsatisfactory situation, we give an information-theoretic security definition of secure function evaluation which is very simple yet provably equivalent to the standard, simulation-based definitions.
2005
EPRINT
Cryptography In the Bounded Quantum-Storage Model
Ivan Damgård Serge Fehr Louis Salvail Christian Schaffner
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
Ivan Damgård Serge Fehr Louis Salvail Christian Schaffner
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.

Program Committees

Eurocrypt 2019
PKC 2018
Crypto 2017
Eurocrypt 2015
Crypto 2013