Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-32009-5_45
Title: Quantum to classical randomness extractors
Authors: Berta, M.
Fawzi, O.
Wehner, S. 
Keywords: entropic uncertainty relations
mutually unbiased bases
noisy-storage model
quantum side information
randomness expansion
randomness extractors
two-party quantum cryptography
Issue Date: 2012
Source: Berta, M.,Fawzi, O.,Wehner, S. (2012). Quantum to classical randomness extractors. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7417 LNCS : 776-793. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-32009-5_45
Abstract: The goal of randomness extraction is to distill (almost) perfect randomness from a weak source of randomness. When the source outputs a classical string X, many extractor constructions are known. Yet, when considering a physical randomness source, X is itself ultimately the result of a measurement on an underlying quantum system. When characterizing the power of a source to supply randomness it is hence a natural question to ask, how much classical randomness we can extract from a quantum system. To tackle this question we here take on the study of quantum-to-classical randomness extractors (QC-extractors). We provide constructions of QC-extractors based on measurements in a full set of mutually unbiased bases (MUBs), and certain single qubit measurements. The latter are particularly appealing since they are not only easy to implement, but appear throughout quantum cryptography. We proceed to prove an upper bound on the maximum amount of randomness that we could hope to extract from any quantum state. Some of our QC-extractors almost match this bound. We show two applications of our results. First, we show that any QC-extractor gives rise to entropic uncertainty relations with respect to quantum side information. Such relations were previously only known for two measurements. In particular, we obtain strong relations in terms of the von Neumann (Shannon) entropy as well as the min-entropy for measurements in (almost) unitary 2-designs, a full set of MUBs, and single qubit measurements in three MUBs each. Second, we finally resolve the central open question in the noisy-storage model [Wehner et al., PRL 100, 220502 (2008)] by linking security to the quantum capacity of the adversary's storage device. More precisely, we show that any two-party cryptographic primitive can be implemented securely as long as the adversary's storage device has sufficiently low quantum capacity. Our protocol does not need any quantum storage to implement, and is technologically feasible using present-day technology. © 2012 International Association for Cryptologic Research.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/40898
ISBN: 9783642320088
ISSN: 03029743
DOI: 10.1007/978-3-642-32009-5_45
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

12
checked on Dec 13, 2017

Page view(s)

68
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.