Two-Source Extractors Secure Against Quantum Adversaries

by Roy Kasher and Julia Kempe

Theory of Computing, Volume 8(21), pp. 461-486, 2012

Bibliography with links to cited articles

[1]   John Stewart Bell: On the Einstein-Podolsky-Rosen paradox. Physics, 1(3):195–200, 1964.

[2]   Avraham Ben-Aroya and Amnon Ta-Shma: Better short-seed quantum-proof extractors. Theoretical Computer Science, 419:17 – 25, 2012. [doi:10.1016/j.tcs.2011.11.036, arXiv:1004.3737]

[3]   Charles H. Bennett and Stephen J. Wiesner: Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states. Phys. Rev. Lett., 69(20):2881–2884, 1992. [doi:10.1103/PhysRevLett.69.2881]

[4]   Jean Bourgain: More on the sum-product phenomenon in prime fields and its applications. Internat. J. Number Theory, 1(1):1–32, 2005. [doi:10.1142/S1793042105000108]

[5]   Benny Chor and Oded Goldreich: Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM J. Comput., 17(2):230–261, 1988. Preliminary version in FOCS’85. [doi:10.1137/0217015]

[6]   Richard Cleve, Wim van Dam, Michael Nielsen, and Alain Tapp: Quantum entanglement and the communication complexity of the inner product function. In 1st NASA Internat. Conf. Quantum Computing and Quantum Communications (QCQC’98), pp. 61–74. Springer, 1999. To appear in TCS. [doi:10.1007/3-540-49208-9_4]

[7]   Anindya De, Christopher Portmann, Thomas Vidick, and Renato Renner: Trevisan’s extractor in the presence of quantum side information. SIAM J. Comput., 41(4):915–940, 2012. [doi:10.1137/100813683, arXiv:0912.5514]

[8]   Anindya De and Thomas Vidick: Near-optimal extractors against quantum storage. In Proc. 42nd STOC, pp. 161–170. ACM Press, 2010. [doi:10.1145/1806689.1806713]

[9]   Ronald de Wolf: 2010. personal communication.

[10]   Yevgeniy Dodis, Ariel Elbaz, Roberto Oliveira, and Ran Raz: Improved randomness extraction from two independent sources. In Proc. 8th Internat. Workshop on Randomization and Computation (RANDOM’04), pp. 334–344. Springer, 2004. [doi:10.1007/978-3-540-27821-4_30]

[11]   Yevgeniy Dodis and Roberto Oliveira: On extracting private randomness over a public channel. In Proc. 7th Internat. Workshop on Randomization and Computation (RANDOM’03), pp. 252–263, 2003. [doi:10.1007/978-3-540-45198-3_22]

[12]   Serge Fehr and Christian Schaffner: Randomness extraction via δ -biased masking in the presence of a quantum attacker. In 5th Theory of Cryptography Conf. (TCC’08), pp. 465–481, 2008. [doi:10.1007/978-3-540-78524-8_26]

[13]   Dmitry Gavinsky, Julia Kempe, and Ronald de Wolf: Strengths and weaknesses of quantum fingerprinting. In Proc. 21st IEEE Conf. on Computational Complexity (CCC’06), pp. 288–298. IEEE Comp. Soc. Press, 2006. [doi:10.1109/CCC.2006.39]

[14]   Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf: Exponential separation for one-way quantum communication complexity, with applications to cryptography. SIAM J. Comput., 38(5):1695–1708, 2008. Preliminary version in STOC’07. [doi:10.1137/070706550]

[15]   Dmitry Gavinsky, Julia Kempe, Oded Regev, and Ronald de Wolf: Bounded-error quantum state identification and exponential separations in communication complexity. SIAM J. Comput., 39(1):1–24, 2009. Preliminary version in STOC’06. [doi:10.1137/060665798]

[16]   Oded Goldreich: Three XOR-lemmas - an exposition. In Oded Goldreich, editor, Studies in Complexity and Cryptography: Miscellanea on the Interplay between Randomness and Computation, volume 6650 of Lecture Notes in Computer Science, pp. 248–272. Springer, 2011. ECCC. [doi:10.1007/978-3-642-22670-0_22]

[17]   Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby: A pseudorandom generator from any one-way function. SIAM J. Comput., 28(4):1364–1396, 1999. Preliminary version in STOC’89. [doi:10.1137/S0097539793244708]

[18]   Paul Hausladen and William K. Wootters: A ‘pretty good’ measurement for distinguishing quantum states. J. Modern Optics, 41(12):2385–2390, 1994. [doi:10.1080/09500349414552221]

[19]   Russell Impagliazzo, Leonid A. Levin, and Michael Luby: Pseudo-random generation from one-way functions (extended abstract). In Proc. 21st STOC, pp. 12–24. ACM Press, 1989. [doi:10.1145/73007.73009]

[20]   Yael Tauman Kalai, Xin Li, and Anup Rao: 2-source extractors under computational assumptions and cryptography with defective randomness. In Proc. 50th FOCS, pp. 617–626. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.61]

[21]   Roy Kasher and Julia Kempe: Two-source extractors secure against quantum adversaries. In Proc. 14th Internat. Workshop on Randomization and Computation (RANDOM’10), pp. 656–669. Springer, 2010. [doi:10.1007/978-3-642-15369-3_49]

[22]   Robert König, Ueli Maurer, and Renato Renner: On the power of quantum memory. IEEE Trans. Inform. Theory, 51(7):2391–2401, 2005. [doi:10.1109/TIT.2005.850087]

[23]   Robert König, Renato Renner, and Christian Schaffner: The operational meaning of min- and max-entropy. IEEE Trans. Inform. Theory, 55(9):4337–4347, 2009. [doi:10.1109/TIT.2009.2025545]

[24]   Robert T. König and Barbara M. Terhal: The bounded-storage model in the presence of a quantum adversary. IEEE Trans. Inform. Theory, 54(2):749–762, 2008. [doi:10.1109/TIT.2007.913245]

[25]   Ashwin Nayak and Julia Salzman: Limits on the ability of quantum states to convey classical messages. J. ACM, 53(1):184–206, 2006. Preliminary versions in FOCS’99 and CCC’02. [doi:10.1145/1120582.1120587]

[26]   Michael A. Nielsen and Isaac L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 1st edition, 2000.

[27]   Ran Raz: Extractors with weak random seeds. In Proc. 37th STOC, pp. 11–20. ACM Press, 2005. [doi:10.1145/1060590.1060593]

[28]   Renato Renner: Security of Quantum Key Distribution. PhD thesis, ETH Zurich, 2005. [arXiv:quant-ph/0512258v2]

[29]   Renato Renner and Robert König: Universally composable privacy amplification against quantum adversaries. In 2nd Theory of Cryptography Conf. (TCC’05), pp. 407–425. Springer, 2005. [doi:10.1007/978-3-540-30576-7_22]

[30]   Miklos Santha and Umesh V. Vazirani: Generating quasi-random sequences from semi-random sources. J. Comput. System Sci., 33(1):75–87, 1986. Preliminary version in FOCS’84. [doi:10.1016/0022-0000(86)90044-9]

[31]   Ronen Shaltiel: Recent Developments in Explicit Constructions of Extractors, volume 1 of Current Trends in Theoretical Computer Science:The Challenge of the New Century, chapter 13, pp. 189–228. World Scientific, 2004. Preliminary version in Bull. EATCS, v.77, 2002. [doi:10.1142/9789812562494_0013]

[32]   Amnon Ta-Shma: Short seed extractors against quantum storage. SIAM J. Comput., 40(3):664–677, 2011. Preliminary version in STOC’09. [doi:10.1137/09076787X]

[33]   Marco Tomamichel, Christian Schaffner, Adam Smith, and Renato Renner: Leftover hashing against quantum side information. IEEE Trans. Inform. Theory, 57(8):5524–5535, 2011. Preliminary version in ISIT’10. [doi:10.1109/TIT.2011.2158473]

[34]   Luca Trevisan: Extractors and pseudorandom generators. J. ACM, 48(4):860–879, 2001. Preliminary version in STOC’99. [doi:10.1145/502090.502099]

[35]   Umesh V. Vazirani: Strong communication complexity or generating quasirandom sequences from two communicating semi-random sources. Combinatorica, 7(4):375–392, 1987. Preliminary version in STOC’85. [doi:10.1007/BF02579325]

[36]   Andrew C. Yao: Theory and applications of trapdoor functions (extended abstract). In Proc. 23rd FOCS, pp. 80–91. IEEE Comp. Soc. Press, 1982. [doi:10.1109/SFCS.1982.45]

[37]   David Zuckerman: General weak random sources. In Proc. 31st FOCS, pp. 534–543. IEEE Comp. Soc. Press, 1990. [doi:10.1109/FSCS.1990.89574]