A Caltech Library Service

The Bounded-Storage Model in the Presence of a Quantum Adversary

König, Robert T. and Terhal, Barbara M. (2008) The Bounded-Storage Model in the Presence of a Quantum Adversary. IEEE Transactions on Information Theory, 54 (2). pp. 749-762. ISSN 0018-9448. doi:10.1109/TIT.2007.913245.

See Usage Policy.


Use this Persistent URL to link to this item:


An extractor is a function ${ssr E}$ that is used to extract randomness. Given an imperfect random source $X$ and a uniform seed $Y$, the output ${ssr E}(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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© Copyright 2008 IEEE. Reprinted with permission. Manuscript received September 13, 2006; revised March 21, 2007. [Posted online: 2008-01-22] The work of R.T. König was supported by the European Commission through the FP6-FET Integrated Project SCALA, CT-015714. The work of B.M. Terhal was supported by the NSA and the ARDA through ARO Contract W911NF-04-C-0098. The material in this paper was presented at QIP 2007, Brisbane, Australia, January 2007. R.T. König wishes to thank Ueli Maurer and Renato Renner for interesting discussions about bounded-storage cryptography. He would also like to thank IBM T.J. Watson Research Center for their hospitality during his stay there. B.M. Terhal would like to thank Yevgeniy Dodis and Roberto Oliveira for many discussions on the security of the bounded-storage model. The authors wish to thank Ronald de Wolf for helpful comments, in particular in relation to Remark 1. They also thank Yevgeniy Dodis for the suggestion to consider independent randomizers, and the reviewers for their detailed and helpful comments.
Subject Keywords:Bounded-storage model, cryptography, extractors, locking, privacy amplification, quantum information theory, quantum key distribution, quantum memory, security proofs, universal composability
Issue or Number:2
Record Number:CaltechAUTHORS:KONieeetit08
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:9660
Deposited By: Archive Administrator
Deposited On:23 Feb 2008
Last Modified:08 Nov 2021 21:01

Repository Staff Only: item control page