Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published February 1, 2008 | public
Journal Article Open

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

Abstract

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.

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.

Files

KOEieeetit08.pdf
Files (338.3 kB)
Name Size Download all
md5:c0ab993f5f007fcfe384002f84647fe8
338.3 kB Preview Download

Additional details

Created:
August 22, 2023
Modified:
October 16, 2023