DROPS

Document

DOI: 10.4230/LIPIcs.TQC.2016.2

Quantum-Proof Multi-Source Randomness Extractors in the Markov Model

Authors: Rotem Arnon-Friedman, Christopher Portmann, and Volkher B. Scholz

Published in: LIPIcs, Volume 61, 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)

Abstract

Randomness extractors, widely used in classical and quantum cryptography and other fields of computer science, e.g., derandomization, are functions which generate almost uniform randomness from weak sources of randomness. In the quantum setting one must take into account the quantum side information held by an adversary which might be used to break the security of the extractor. In the case of seeded extractors the presence of quantum side information has been extensively studied. For multi-source extractors one can easily see that high conditional min-entropy is not sufficient to guarantee security against arbitrary side information, even in the classical case. Hence, the interesting question is under which models of (both quantum and classical) side information multi-source extractors remain secure. In this work we suggest a natural model of side information, which we call the Markov model, and prove that any multi-source extractor remains secure in the presence of quantum side information of this type (albeit with weaker parameters). This improves on previous results in which more restricted models were considered or the security of only some types of extractors was shown.

Cite as

Rotem Arnon-Friedman, Christopher Portmann, and Volkher B. Scholz. Quantum-Proof Multi-Source Randomness Extractors in the Markov Model. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 61, pp. 2:1-2:34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{arnonfriedman_et_al:LIPIcs.TQC.2016.2,
  author =	{Arnon-Friedman, Rotem and Portmann, Christopher and Scholz, Volkher B.},
  title =	{{Quantum-Proof Multi-Source Randomness Extractors in the Markov Model}},
  booktitle =	{11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)},
  pages =	{2:1--2:34},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-019-4},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{61},
  editor =	{Broadbent, Anne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2016.2},
  URN =		{urn:nbn:de:0030-drops-66830},
  doi =		{10.4230/LIPIcs.TQC.2016.2},
  annote =	{Keywords: Quantum proof randomness extractors, multisource extractors, device independent quantum cryptography}
}

Document

DOI: 10.4230/LIPIcs.TQC.2015.73

Semidefinite Programs for Randomness Extractors

Authors: Mario Berta, Omar Fawzi, and Volkher B. Scholz

Published in: LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)

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.

Cite as

Mario Berta, Omar Fawzi, and Volkher B. Scholz. Semidefinite Programs for Randomness Extractors. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 73-91, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{berta_et_al:LIPIcs.TQC.2015.73,
  author =	{Berta, Mario and Fawzi, Omar and Scholz, Volkher B.},
  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 =	{Beigi, Salman and K\"{o}nig, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.73},
  URN =		{urn:nbn:de:0030-drops-55507},
  doi =		{10.4230/LIPIcs.TQC.2015.73},
  annote =	{Keywords: Randomness Extractors, Quantum adversaries, Semidefinite programs}
}

Search Results

Documents authored by Scholz, Volkher B.

Quantum-Proof Multi-Source Randomness Extractors in the Markov Model

Abstract

Cite as

Semidefinite Programs for Randomness Extractors

Abstract

Cite as

Thanks for your feedback!

Could not send message