Paper 2007/249

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

Serge Fehr and Christian Schaffner

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.

Note: 14 pages

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
randomness extractionquantum cryptographyentropic securitydelta-biased setserror-correction
Contact author(s)
c schaffner @ cwi nl
History
2007-06-22: received
Short URL
https://ia.cr/2007/249
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/249,
      author = {Serge Fehr and Christian Schaffner},
      title = {Randomness Extraction via Delta-Biased Masking in the Presence of a Quantum Attacker},
      howpublished = {Cryptology ePrint Archive, Paper 2007/249},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/249}},
      url = {https://eprint.iacr.org/2007/249}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.