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]