Open access
Date
2015Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
Abstract
Randomness extractors are an important building block for classical and quantum cryptography. However, for many applications it is crucial that the extractors are quantum-proof, i.e., that they work even in the presence of quantum adversaries. In general, quantum-proof extractors are poorly understood and we would like to argue that in the same way as Bell inequalities (multiprover games) and communication complexity, the setting of randomness extractors provides a operationally useful framework for studying the power and limitations of a quantum memory compared to a classical one. We start by recalling how to phrase the extractor property as a quadratic program with linear constraints. We then construct a semidefinite programming (SDP) relaxation for this program that is tight for some extractor constructions. Moreover, we show that this SDP relaxation is even sufficient to certify quantum-proof extractors. This gives a unifying approach to understand the stability properties of extractors against quantum adversaries. Finally, we analyze the limitations of this SDP relaxation. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000111764Publication status
publishedExternal links
Book title
10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)Journal / series
Leibniz International Proceedings in Informatics (LIPIcs)Volume
Pages / Article No.
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für InformatikEvent
Subject
Randomness Extractors; Quantum adversaries; Semidefinite programsOrganisational unit
03781 - Renner, Renato / Renner, Renato
Funding
258932 - Generalized (quantum) information theory (EC)
More
Show all metadata
ETH Bibliography
yes
Altmetrics