License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TQC.2015.73
URN: urn:nbn:de:0030-drops-55507
Go to the corresponding LIPIcs Volume Portal

Berta, Mario ; Fawzi, Omar ; Scholz, Volkher B.

Semidefinite Programs for Randomness Extractors

6.pdf (0.5 MB)


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.

BibTeX - Entry

  author =	{Mario Berta and Omar Fawzi and Volkher B. Scholz},
  title =	{{Semidefinite Programs for Randomness Extractors}},
  booktitle =	{10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)},
  pages =	{73--91},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-96-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{44},
  editor =	{Salman Beigi and Robert Koenig},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-55507},
  doi =		{10.4230/LIPIcs.TQC.2015.73},
  annote =	{Keywords: Randomness Extractors, Quantum adversaries, Semidefinite programs}

Keywords: Randomness Extractors, Quantum adversaries, Semidefinite programs
Collection: 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)
Issue Date: 2015
Date of publication: 04.11.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI