Document Open Access Logo

Semidefinite Programs for Randomness Extractors

Authors Mario Berta, Omar Fawzi, Volkher B. Scholz

PDF
Thumbnail PDF

File

LIPIcs.TQC.2015.73.pdf
  • Filesize: 0.51 MB
  • 19 pages

Document Identifiers

Author Details

Mario Berta
Omar Fawzi
Volkher B. Scholz

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.TQC.2015.73

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.
Keywords
  • Randomness Extractors
  • Quantum adversaries
  • Semidefinite programs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon, Sanjeev Arora, Rajsekar Manokaran, Dana Moshkovitz, and Omri Weinstein. Inapproximability of densest k-subgraph from average case hardness. Manuscript, available at http://www.csc.kth.se/~rajsekar/papers/dks.pdf, 2011.
  2. Avraham Ben-Aroya and Amnon Ta-Shma. Better short-seed quantum-proof extractors. Theoretical Computer Science, 419:17-25, 2012. Google Scholar
  3. Charles H. Bennett and Gilles Brassard. Quantum cryptography: Public key distribution and coin tossing. In Proc. International Conference on Computers, Systems and Signal Processing, 1984. Google Scholar
  4. Charles H. Bennett, Gilles Brassard, Claude Crépeau, and Ueli M. Maurer. Generalized privacy amplification. Information Theory, IEEE Transactions on, 41:1915-1923, 1995. Google Scholar
  5. Charles H. Bennett, Gilles Brassard, and Jean-Marc Robert. Privacy amplification by public discussion. SIAM journal on Computing, 17:210-229, 1988. Google Scholar
  6. Mario Berta, Omar Fawzi, and Volkher B. Scholz. Quantum-proof randomness extractors via operator space theory. arXiv preprint arXiv:1409.3563, 2014. Google Scholar
  7. Mario Berta, Omar Fawzi, and Volkher B. Scholz. Quantum bilinear programs. arXiv preprint arXiv:1506.08810, 2015. Google Scholar
  8. Mario Berta, Omar Fawzi, Volkher B. Scholz, and Oleg Szehr. Variations on classical and quantum extractors. In Information Theory (ISIT), 2014 IEEE International Symposium on, pages 1474-1478, 2014. Google Scholar
  9. Aditya Bhaskara, Venkatesan Guruswami, Moses Charikar, Aravindan Vijayaraghavan, and Yuan Zhou. Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph. In Proc. of the 23rd Annual ACM-SIAM Symp. on Discrete Algorithms (SODA'12), 2012. Google Scholar
  10. R. Bhatia. Matrix Analysis. Springer, 1997. Google Scholar
  11. Kai-Min Chung, Yaoyun Shi, and Xiaodi Wu. Physical randomness extractors. arXiv preprint arXiv:1402.4797, 2014. Google Scholar
  12. Roger Colbeck and Adrian Kent. Private randomness expansion with untrusted devices. Journal of Physics A: Mathematical and Theoretical, 44:095305, 2011. Google Scholar
  13. Matthew Coudron and Henry Yuen. Infinite randomness expansion and amplification with a constant number of devices. In Proc. of the 46th Annual ACM Symp. on Theory of Computing, STOC'14, pages 427-436. ACM, 2014. Google Scholar
  14. A. De, C. Portmann, T. Vidick, and R. Renner. Trevisan’s extractor in the presence of quantum side information. SIAM Journal on Computing, 41:915-940, 2012. Google Scholar
  15. Uriel Feige and Michael Seltser. On the densest k-subgraph problem. Algorithmica, 29:2001, 1997. Google Scholar
  16. Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf. Exponential separations for one-way quantum communication complexity, with applications to cryptography. In Proc. of the 39th Annual ACM Symp. on Theory of Computing, STOC'07, pages 516-525. ACM, 2007. Google Scholar
  17. Johan Håstad, Russell Impagliazzo, Leonid A Levin, and Michael Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28:1364-1396, 1999. Google Scholar
  18. R. König and R. Renner. Sampling of min-entropy relative to quantum knowledge. Information Theory, IEEE Transactions on, 57:4760-4787, 2011. Google Scholar
  19. R. König and B. Terhal. The bounded-storage model in the presence of a quantum adversary. Information Theory, IEEE Transactions on, 54:749-762, 2008. Google Scholar
  20. R. König, S. Wehner, and J. Wullschleger. Unconditional security from noisy quantum storage. Information Theory, IEEE Transactions on, 58:1962-1984, 2012. Google Scholar
  21. Carl A. Miller and Yaoyun Shi. Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices. arXiv preprint arXiv:1402.0489, 2014. Google Scholar
  22. Noam Nisan and Amnon Ta-Shma. Extracting randomness: a survey and new constructions. Journal of Computer and System Sciences, 58:148-173, 1999. Google Scholar
  23. Noam Nisan and David Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 51:43-52, 1996. Google Scholar
  24. Stefano Pironio, Antonio Acín, Serge Massar, A Boyer de La Giroday, Dzimitry N Matsukevich, Peter Maunz, Steven Olmschenk, David Hayes, Le Luo, T Andrew Manning, et al. Random numbers certified by bell’s theorem. Nature, 464:1021-1024, 2010. Google Scholar
  25. J. Radhakrishnan and A. Ta-Shma. Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM Journal on Discrete Mathematics, 13:2-24, 2000. Google Scholar
  26. Renato Renner. Security of Quantum Key Distribution. PhD thesis, ETH Zurich, 2005. Google Scholar
  27. Renato Renner and Robert König. Universally composable privacy amplification against quantum adversaries. In Joe Kilian, editor, Theory of Cryptography, volume 3378 of Lecture Notes in Computer Science, pages 407-425. Springer Berlin Heidelberg, 2005. Google Scholar
  28. Ronen Shaltiel. Recent developments in explicit constructions of extractors. Bulletin of the EATCS, 77:67-95, 2002. Google Scholar
  29. Michael Sipser. Expanders, randomness, or time versus space. Journal of Computer and System Sciences, 36:379 - 383, 1988. Google Scholar
  30. Oleg Szehr. Decoupling theorems. Master’s thesis, ETH Zurich, 2011. Google Scholar
  31. Amnon Ta-Shma. Extractors against classical and quantum adversaries. Tutorial QCrypt, 2013. Google Scholar
  32. M. Tomamichel, C. Schaffner, A. Smith, and R. Renner. Leftover hashing against quantum side information. Information Theory, IEEE Transactions on, 57:5524-5535, 2011. Google Scholar
  33. Luca Trevisan. Construction of extractors using pseudo-random generators (extended abstract). In Proc. of the 31st Annual ACM Symposium on Theory of Computing, STOC'99, pages 141-148. ACM, 1999. Google Scholar
  34. Salil P. Vadhan. Pseudorandomness. Now Publishers Inc., Hanover, MA, USA, 2012. Google Scholar
  35. Umesh Vazirani and Thomas Vidick. Certifiable quantum dice: Or, true random number generation secure against quantum adversaries. In Proc. of the 44th Annual ACM Symp. on Theory of Computing, STOC'12, pages 61-76, New York, NY, USA, 2012. ACM. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact