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 August 21, 2012 | Published + Submitted
Journal Article Open

Trevisan's Extractor in the Presence of Quantum Side Information

Abstract

Randomness extraction involves the processing of purely classical information and is therefore usually studied with in the framework of classical probability theory. However, such a classical treatment is generally too restrictive for applications where side information about the values taken by classical random variables may be represented by the state of a quantum system. This is particularly relevant in the context of cryptography, where an adversary may make use of quantum devices. Here, we show that the well-known construction paradigm for extractors proposed by Trevisan is sound in the presence of quantum side information. We exploit the modularity of this paradigm to give several concrete extractor constructions, which, e.g., extract all the conditional (smooth) min-entropy of the source using a seed of length polylogarithmic in the input, or only require the seed to be weakly random.

Additional Information

© 2012 Society for Industrial and Applied Mathematics. Received by the editors November 3, 2010; accepted for publication (in revised form) June 5, 2012; published electronically August 21, 2012. A preliminary version of this work [5] appeared at STOC '10. This author's work was supported by the Berkeley fellowship for graduate study and by NSF-CCF-1017403. The second author's work was supported in part by the Vienna Science and Technology Fund (WWTF) through project ICT10-067 (HiPANQ). These authors' work was supported by the Swiss National Science Foundation (via grants 200021-119868 and 200020-135048, and the National Centre of Competence in Research "Quantum Science and Technology") and by the European Research Council—ERC (grant 258932). This author's work was supported by the National Science Foundation under grant 0844626.

Attached Files

Published - 100813683.pdf

Submitted - Key_recycling_in_authentication.pdf

Files

Key_recycling_in_authentication.pdf
Files (743.9 kB)
Name Size Download all
md5:d667b5de7b4cfe737ed00930e43ef084
422.9 kB Preview Download
md5:04b320d76558db1973ef3e6b3cffe30e
321.1 kB Preview Download

Additional details

Created:
September 15, 2023
Modified:
October 23, 2023