Document Open Access Logo

New Constructions for Quantum Money

Authors Marios Georgiou, Iordanis Kerenidis

PDF
Thumbnail PDF

File

LIPIcs.TQC.2015.92.pdf
  • Filesize: 0.49 MB
  • 19 pages

Document Identifiers

Author Details

Marios Georgiou
Iordanis Kerenidis

Cite As Get BibTex

Marios Georgiou and Iordanis Kerenidis. New Constructions for Quantum Money. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 92-110, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.TQC.2015.92

Abstract

We propose an information theoretically secure secret-key quantum money scheme in which the verification of a coin is classical and consists of only one round; namely, a classical query from the user to the bank and an accept/reject answer from the bank to the user. A coin can be verified polynomially (on the number of its qubits) many times before it expires. Our scheme is an improvement on Gavinsky's scheme [Gavinsky, Computational Complexity, 2012], where three rounds of interaction are needed and is based on the notion of quantum retrieval games. Moreover, we propose a public-key quantum money scheme which uses one-time memories as a building block and is computationally secure in the random oracle model. This construction is derived naturally from our secret-key scheme using the fact that one-time memories are a special case of quantum retrieval games.

Subject Classification

Keywords
  • Quantum Money
  • Quantum Cryptography
  • Quantum Retrieval Games

Metrics

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

References

  1. Scott Aaronson and Paul Christiano. Quantum money from hidden subspaces. In Proceedings of the 44th Symposium on Theory of Computing, pages 41-60. ACM, 2012. Google Scholar
  2. Ziv Bar-Yossef, Thathachar S Jayram, and Iordanis Kerenidis. Exponential separation of quantum and classical one-way communication complexity. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 128-137. ACM, 2004. Google Scholar
  3. Anne Broadbent, Gus Gutoski, and Douglas Stebila. Quantum one-time programs. Advances in Cryptology-CRYPTO 2013, pages 344-360, 2013. Google Scholar
  4. Edward Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, and Peter Shor. Quantum money from knots. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pages 276-289. ACM, 2012. Google Scholar
  5. Dmitry Gavinsky. Quantum money with classical verification. In Computational Complexity (CCC), 2012 IEEE 27th Annual Conference on, pages 42-52. IEEE, 2012. Google Scholar
  6. 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 Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 516-525. ACM, 2007. Google Scholar
  7. Shafi Goldwasser, Yael Tauman Kalai, and Guy N Rothblum. One-time programs. Advances in Cryptology-CRYPTO 2008, pages 39-56, 2008. Google Scholar
  8. Yi-Kai Liu. Building one-time memories from isolated qubits. In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 269-286. ACM, 2014. Google Scholar
  9. Yi-Kai Liu. Privacy amplification in the isolated qubits model. arXiv preprint arXiv:1410.3918, 2014. Google Scholar
  10. Yi-Kai Liu. Single-shot security for one-time memories in the isolated qubits model. arXiv preprint arXiv:1402.0049, 2014. Google Scholar
  11. Abel Molina, Thomas Vidick, and John Watrous. Optimal counterfeiting attacks and generalizations for wiesner’s quantum money. In Theory of Quantum Computation, Communication, and Cryptography, pages 45-64. Springer, 2013. Google Scholar
  12. Michele Mosca and Douglas Stebila. Quantum coins. Error-Correcting Codes, Finite Geometries and Cryptography. Contemporary Mathematics, volume 523, pages 35-47. American Mathematical Society, 2010, 2009. Google Scholar
  13. Daniel Nagaj and Or Sattath. An adaptive attack on wiesner’s quantum money based on interaction-free measurement. arXiv preprint arXiv:1404.1507, 2014. Google Scholar
  14. Marta Conde Pena, Jean-Charles Faugère, and Ludovic Perret. Algebraic cryptanalysis of a quantum money scheme the noise-free case. In Public-Key Cryptography-PKC 2015, pages 194-213. Springer, 2015. Google Scholar
  15. Stephen Wiesner. Conjugate coding. ACM Sigact News, 15(1):78-88, 1983. Google Scholar
  16. Norman Yao, Fernando Pastawski, Liang Jiang, Mikhail Lukin, and Ignacio Cirac. Unforgeable noise-tolerant quantum tokens. Bulletin of the American Physical Society, 57, 2012. 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 About DROPS Imprint Privacy Contact