2026-08-16T04:36:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5550 2024-03-06T10:36:39Z ddc:004 open_access

Semidefinite Programs for Randomness Extractors Berta, Mario Fawzi, Omar Scholz, Volkher B. Randomness Extractors Quantum adversaries Semidefinite programs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mario Berta and Omar Fawzi and Volkher B. Scholz 2015 Is Part Of LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2015.73 urn:nbn:de:0030-drops-55507 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.73 eng https://creativecommons.org/licenses/by/3.0/legalcode