The bounded-storage model in the presence of a quantum adversary

Robert T. Konig*, Barbara M. Terhal

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

37 Citations (Scopus)


An extractor is a function that is used to extract randomness. Given an imperfect random source Χ and a uniform seed Y, the output Ε(X,Y) is close to uniform. We study properties of such functions in the presence of prior quantum information about X, with a particular focus on cryptographic applications. We prove that certain extractors are suitable for key expansion in the bounded-storage model where the adversary has a limited amount of quantum memory. For extractors with one-bit output we show that the extracted bit is essentially equally secure as in the case where the adversary has classical resources. We prove the security of certain constructions that output multiple bits in the bounded-storage model.
Original languageEnglish
Pages (from-to)749-762
Number of pages14
JournalIEEE Transactions on Information Theory
Issue number2
Publication statusPublished - 2008
Externally publishedYes


  • Bounded-storage model
  • Cryptography
  • Extractors
  • Locking
  • Privacy amplification
  • Quantum information theory
  • Quantum key distribution
  • Quantum memory
  • Security proofs
  • Universal composability


Dive into the research topics of 'The bounded-storage model in the presence of a quantum adversary'. Together they form a unique fingerprint.

Cite this