A Caltech Library Service

Trevisan's Extractor in the Presence of Quantum Side Information

De, Anindya and Portmann, Christopher and Vidick, Thomas and Renner, Renato (2012) Trevisan's Extractor in the Presence of Quantum Side Information. SIAM Journal on Computing, 41 (4). pp. 915-940. ISSN 0097-5397. doi:10.1137/100813683.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Vidick, Thomas0000-0002-6405-365X
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.
Funding AgencyGrant Number
Wiener-, Wissenschafts-, Forschungs- und Technologiefonds (WWTF)ICT10-067
Swiss National Science Foundation (SNSF)200021-119868
Swiss National Science Foundation (SNSF)200020-135048
University of California, BerkeleyUNSPECIFIED
European Research Council (ERC)258932
Subject Keywords:randomness extractors, quantum information, quantum cryptography, smooth min-entropy
Issue or Number:4
Classification Code:AMS subject classifications. 68Q01, 81P45, 81P94, 94A17
Record Number:CaltechAUTHORS:20160322-084353163
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:65573
Deposited By: Ruth Sustaita
Deposited On:30 Mar 2016 23:55
Last Modified:10 Nov 2021 23:47

Repository Staff Only: item control page