Quantum Money from Hidden Subspaces

by Scott Aaronson and Paul Christiano

Theory of Computing, Volume 9(9), pp. 349-401, 2013

Bibliography with links to cited articles

[1]   Scott Aaronson: Quantum lower bound for the collision problem. In Proc. 34th STOC, pp. 635–642. ACM Press, 2002. Preprint at arXiv. [doi:10.1145/509907.509999]

[2]   Scott Aaronson: Limitations of quantum advice and one-way communication. Theory of Computing, 1(1):1–28, 2005. Preliminary version in CCC’04. Preprint at arXiv. [doi:10.4086/toc.2005.v001a001]

[3]   Scott Aaronson: Quantum copy-protection and quantum money. In Proc. 24th IEEE Conf. on Computational Complexity (CCC’09), pp. 229–242. IEEE Comp. Soc. Press, 2009. [doi:10.1109/CCC.2009.42]

[4]   Scott Aaronson: On the security of private-key quantum money, 2013. In preparation.

[5]   Scott Aaronson and Greg Kuperberg: Quantum versus classical proofs and advice. Theory of Computing, 3(7):129–157, 2007. Preliminary version in CCC’07. Preprint at arXiv. [doi:10.4086/toc.2007.v003a007]

[6]   Scott Aaronson and Yaoyun Shi: Quantum lower bounds for the collision and the element distinctness problems. J. ACM, 51(4):595–605, 2004. [doi:10.1145/1008731.1008735]

[7]   Martin R. Albrecht and Carlos Cid: Cold boot key recovery by solving polynomial systems with noise. In Proc. 9th Internat. Conf. on Applied Cryptography and Network Security (ACNS’11), pp. 57–72. Springer, 2011. Available in preprint. [doi:10.1007/978-3-642-21554-4_4]

[8]   Noga Alon, Michael Krivelevich, and Benny Sudakov: Finding a large hidden clique in a random graph. Random Structures & Algorithms, 13(3-4):457–466, 1998. Preliminary version in SODA’98. [doi:10.1002/(SICI)1098-2418(199810/12)13:3/4¡457::AID-RSA14¿3.0.CO;2-W]

[9]   Andris Ambainis: Quantum lower bounds by quantum arguments. J. Comput. System Sci., 64(4):750–767, 2002. Preliminary version in STOC’00. Preprint at arXiv. [doi:10.1006/jcss.2002.1826]

[10]   Andris Ambainis, Loïck Magnin, Martin Roetteler, and Jérémie Roland: Symmetry-assisted adversaries for quantum state generation. In Proc. 26th IEEE Conf. on Computational Complexity (CCC’11), pp. 167–177. IEEE Comp. Soc. Press, 2011. Preprint at arXiv. [doi:10.1109/CCC.2011.24]

[11]   Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang: On the (im)possibility of obfuscating programs. J. ACM, 59(2):6, 2012. Preliminary versions in CRYPTO’01 and ECCC. [doi:10.1145/2160158.2160159]

[12]   Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf: Quantum lower bounds by polynomials. J. ACM, 48(4):778–797, 2001. Preliminary version in FOCS’98. Preprint at arXiv. [doi:10.1145/502090.502097]

[13]   Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh V. Vazirani: Strengths and weaknesses of quantum computing. SIAM J. Comput., 26(5):1510–1523, 1997. Preprint at arXiv. [doi:10.1137/S0097539796300933]

[14]   Charles H. Bennett and Gilles Brassard: Quantum cryptography: public key distribution and coin tossing. In Proc. IEEE Internat. Conf. on Computers, Systems and Signal Processing, pp. 175–179, 1984.

[15]   Charles H. Bennett, Gilles Brassard, Seth Breidbart, and Stephen Wiesner: Quantum cryptography, or unforgeable subway tokens. In Proceedings of CRYPTO, pp. 267–275. Plenum Press, 1982.

[16]   Niels Bohr: Atomic Physics and Human Knowledge. Dover, 2010. First published 1961.

[17]   Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry: Random oracles in a quantum world. In 17th Internat. Conf. on the Theory and Application of Cryptology and Information Security (ASIACRYPT’11), pp. 41–69, 2011. Preprint at arXiv. [doi:10.1007/978-3-642-25385-0_3]

[18]   Charles Bouillaguet, Jean-Charles Faugère, Pierre-Alain Fouque, and Ludovic Perret: Practical cryptanalysis of the identification scheme based on the isomorphism of polynomial with one secret problem. In 14th Internat. Conf. on Practice and Theory in Public Key Cryptography (PKC’11), pp. 473–493. Springer, 2011. [doi:10.1007/978-3-642-19379-8_29]

[19]   Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp: Quantum amplitude amplification and estimation. In Jr. Samuel J. Lomonaco and Howard E. Brandt, editors, Quantum Computation and Information, Contemporary Mathematics Series. AMS, 2002. Preprint at arXiv.

[20]   David Cash, Dennis Hofheinz, Eike Kiltz, and Chris Peikert: Bonsai trees, or how to delegate a lattice basis. J. Cryptology, 25(4):601–639, 2012. Preliminary version in EUROCRYPT’10. [doi:10.1007/s00145-011-9105-2]

[21]   Sourav Chakraborty, Jaikumar Radhakrishnan, and Nandakumar Raghunathan: Bounds for error reduction with few quantum queries. In Proc. 9th Internat. Workshop on Randomization and Computation (RANDOM’05), pp. 245–256. Springer, 2005. [doi:10.1007/11538462_21]

[22]   Jintai Ding and Bo-Yin Yang: Multivariate public key cryptography. In Daniel J. Bernstein, Johannes Buchmann, and Erik Dahmen, editors, Post-Quantum Cryptography, pp. 193–241. Springer, 2009. [doi:10.1007/978-3-540-88702-7_6]

[23]   Edward Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, Daniel Nagaj, and Peter Shor: Quantum state restoration and single-copy tomography for ground states of Hamiltonians. Phys. Rev. Lett., 105(19):190503, 2010. Preprint at arXiv. [doi:10.1103/PhysRevLett.105.190503]

[24]   Edward Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, and Peter W. Shor: Quantum money from knots. In Proc. 3rd Innovations in Theoretical Comput. Sci. (ITCS’12), pp. 276–289. ACM Press, 2012. Preprint at arXiv. [doi:10.1145/2090236.2090260]

[25]   Dmitry Gavinsky: Quantum money with classical verification. In Proc. 27th IEEE Conf. on Computational Complexity (CCC’12), pp. 42–52. IEEE Comp. Soc. Press, 2012. Preprint at arXiv. [doi:10.1109/CCC.2012.10]

[26]   Willi Geiselmann, Willi Meier, and Rainer Steinwandt: An attack on the isomorphisms of polynomials problem with one secret. Int. J. Inf. Sec., 2(1):59–64, 2003. [doi:10.1007/s10207-003-0025-5]

[27]   Lov K. Grover: A fast quantum mechanical algorithm for database search. In Proc. 28th STOC, pp. 212–219. ACM Press, 1996. Preprint at arXiv. [doi:10.1145/237814.237866]

[28]   Christopher J. Hillar and Lek-Heng Lim: Most tensor problems are NP-hard. Technical report, 2009. [arXiv:0911.1393]

[29]   Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, and Mario Szegedy: Quantum query complexity of state conversion. In Proc. 52nd FOCS, pp. 344–353. IEEE Comp. Soc. Press, 2011. Preprint at arXiv. [doi:10.1109/FOCS.2011.75]

[30]   Andrew Lutomirski: An online attack against Wiesner’s quantum money. Technical report, 2010. [arXiv:1010.0256]

[31]   Andrew Lutomirski: Component mixers and a hardness result for counterfeiting quantum money. Technical report, 2011. [arXiv:1107.0321]

[32]   Andrew Lutomirski, Scott Aaronson, Edward Farhi, David Gosset, Jonathan A. Kelner, Avinatan Hassidim, and Peter W. Shor: Breaking and making quantum money: Toward a new quantum cryptographic protocol. In Proc. Innovations in Comput. Sci. (ICS’10), pp. 20–31. Tsinghua University Press, 2010. ICS’10. Preprint at arXiv.

[33]   Abel Molina, Thomas Vidick, and John Watrous: Optimal counterfeiting attacks and generalizations for Wiesner’s quantum money. In Proc. 7th Conf. Theory of Quantum Computation, Communication, and Cryptography (TQC’12), pp. 45–64, 2012. Preprint at arXiv. [doi:10.1007/978-3-642-35656-8_4]

[34]   Michele Mosca and Douglas Stebila: Quantum coins. In Error-Correcting Codes, Finite Geometries and Cryptography, volume 523, pp. 35–47. Amer. Math. Soc., 2010. Preprint at arXiv.

[35]   Moni Naor and Moti Yung: Universal one-way hash functions and their cryptographic applications. In Proc. 21st STOC, pp. 33–43. ACM Press, 1989. [doi:10.1145/73007.73011]

[36]   Michael Nielsen and Isaac Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2000. [ACM:544199]

[37]   Fernando Pastawski, Norman Y. Yao, Liang Jiang, Mikhail D. Lukin, and J. Ignacio Cirac: Unforgeable noise-tolerant quantum tokens. Technical report, 2011. [arXiv:1112.5456]

[38]   Jacques Patarin, Louis Goubin, and Nicolas Courtois: Improved algorithms for isomorphisms of polynomials. In Proc. Internat. Conf. on the Theory and Application of Cryptographic Techniques (EUROCRYPT’98), pp. 184–200. Springer, 1998. [doi:10.1007/BFb0054126]

[39]   Oded Regev: On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6):34, 2009. Preliminary version in STOC’05. [doi:10.1145/1568318.1568324]

[40]   John Rompel: One-way functions are necessary and sufficient for secure signatures. In Proc. 22nd STOC, pp. 387–394. ACM Press, 1990. [doi:10.1145/100216.100269]

[41]   Tathagat Tulsi, Lov K. Grover, and Apoorva Patel: A new algorithm for fixed point quantum search. Quantum Inf. Comput., 6(6):483–494, 2006. QIC. [ACM:2011693]

[42]   Stephen Wiesner: Conjugate coding. SIGACT News, 15(1):78–88, 1983. Original manuscript written circa 1970. [doi:10.1145/1008908.1008920]