International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Randomness Extraction via Delta-Biased Masking in the Presence of a Quantum Attacker

Serge Fehr
Christian Schaffner
Search ePrint
Search Google
Abstract: 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.
  title={Randomness Extraction via Delta-Biased Masking in the Presence of a Quantum Attacker},
  booktitle={IACR Eprint archive},
  keywords={foundations / randomness extraction, quantum cryptography, entropic security, delta-biased sets, error-correction},
  note={ 13686 received 22 Jun 2007},
  author={Serge Fehr and Christian Schaffner},