Document Open Access Logo

Quantum Proofs of Deletion for Learning with Errors

Author Alexander Poremba

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.90.pdf
  • Filesize: 0.83 MB
  • 14 pages

Document Identifiers

Author Details

Alexander Poremba
  • California Institute of Technology, Pasadena, CA, USA

Funding

  • Poremba, Alexander: Partially supported by AFOSR YIP award number FA9550-16-1-0495 and the Institute for Quantum Information and Matter (an NSF Physics Frontiers Center; NSF Grant PHY-1733907).

Acknowledgements

I would like to thank Urmila Mahadev, Thomas Vidick, Prabhanjan Ananth and Vinod Vaikuntanathan for many insightful discussions.

Cite AsGet BibTex

Alexander Poremba. Quantum Proofs of Deletion for Learning with Errors. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 90:1-90:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.90

Abstract

Quantum information has the property that measurement is an inherently destructive process. This feature is most apparent in the principle of complementarity, which states that mutually incompatible observables cannot be measured at the same time. Recent work by Broadbent and Islam (TCC 2020) builds on this aspect of quantum mechanics to realize a cryptographic notion called certified deletion. While this remarkable notion enables a classical verifier to be convinced that a (private-key) quantum ciphertext has been deleted by an untrusted party, it offers no additional layer of functionality. In this work, we augment the proof-of-deletion paradigm with fully homomorphic encryption (FHE). We construct the first fully homomorphic encryption scheme with certified deletion - an interactive protocol which enables an untrusted quantum server to compute on encrypted data and, if requested, to simultaneously prove data deletion to a client. Our scheme has the desirable property that verification of a deletion certificate is public; meaning anyone can verify that deletion has taken place. Our main technical ingredient is an interactive protocol by which a quantum prover can convince a classical verifier that a sample from the Learning with Errors (LWE) distribution in the form of a quantum state was deleted. As an application of our protocol, we construct a Dual-Regev public-key encryption scheme with certified deletion, which we then extend towards a (leveled) FHE scheme of the same type. We introduce the notion of Gaussian-collapsing hash functions - a special case of collapsing hash functions defined by Unruh (Eurocrypt 2016) - and we prove the security of our schemes under the assumption that the Ajtai hash function satisfies a certain strong Gaussian-collapsing property in the presence of leakage.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • Learning with errors
  • certified deletion
  • fully homomorphic encryption

Metrics

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

Related Versions

References

  1. Miklós Ajtai. Generating hard instances of lattice problems (extended abstract). In Gary L. Miller, editor, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 99-108. ACM, 1996. URL: https://doi.org/10.1145/237814.237838.
  2. Gorjan Alagic, Stacey Jeffery, Maris Ozols, and Alexander Poremba. On quantum chosen-ciphertext attacks and learning with errors. Cryptography, 4(1), 2020. URL: https://doi.org/10.3390/cryptography4010010.
  3. Dan Boneh, Craig Gentry, Sergey Gorbunov, Shai Halevi, Valeria Nikolaenko, Gil Segev, Vinod Vaikuntanathan, and Dhinakaran Vinayagamurthy. Fully key-homomorphic encryption, arithmetic circuit abe, and compact garbled circuits. Cryptology ePrint Archive, Paper 2014/356, 2014. URL: https://eprint.iacr.org/2014/356.
  4. Raphael Bost, Raluca Ada Popa, Stephen Tu, and Shafi Goldwasser. Machine learning classification over encrypted data. IACR Cryptology ePrint Archive, 2014:331, 2014. URL: https://eprint.iacr.org/2014/331.
  5. Zvika Brakerski and Vinod Vaikuntanathan. Efficient fully homomorphic encryption from (standard) lwe. In Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS '11, pages 97-106, USA, 2011. IEEE Computer Society. URL: https://doi.org/10.1109/FOCS.2011.12.
  6. Zvika Brakerski and Vinod Vaikuntanathan. Efficient fully homomorphic encryption from (standard) lwe. Cryptology ePrint Archive, Paper 2011/344, 2011. URL: https://eprint.iacr.org/2011/344.
  7. Anne Broadbent and Rabib Islam. Quantum encryption with certified deletion. Lecture Notes in Computer Science, pages 92-122, 2020. URL: https://doi.org/10.1007/978-3-030-64381-2_4.
  8. Ran Canetti, Uri Feige, Oded Goldreich, and Moni Naor. Adaptively secure multi-party computation. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC '96, pages 639-648, New York, NY, USA, 1996. Association for Computing Machinery. URL: https://doi.org/10.1145/237814.238015.
  9. Yilei Chen, Qipeng Liu, and Mark Zhandry. Quantum algorithms for variants of average-case lattice problems via filtering, 2021. URL: http://arxiv.org/abs/2108.11015.
  10. Xavier Coiteux-Roy and Stefan Wolf. Proving erasure. 2019 IEEE International Symposium on Information Theory (ISIT), July 2019. URL: https://doi.org/10.1109/isit.2019.8849661.
  11. Stefan Dziembowski, Tomasz Kazana, and Daniel Wichs. One-time computable self-erasing functions. In Theory of Cryptography - 8th Theory of Cryptography Conference, TCC 2011, volume 6597 of Lecture Notes in Computer Science, page 125. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-19571-6_9.
  12. Sanjam Garg, Shafi Goldwasser, and Prashant Nalini Vasudevan. Formalizing data deletion in the context of the right to be forgotten. IACR Cryptol. ePrint Arch., page 254, 2020. URL: https://eprint.iacr.org/2020/254.
  13. Craig Gentry. A fully homomorphic encryption scheme. PhD thesis, Stanford University, 2009. URL: https://crypto.stanford.edu/craig.
  14. Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. Cryptology ePrint Archive, Report 2007/432, 2007. URL: https://eprint.iacr.org/2007/432.
  15. Craig Gentry, Amit Sahai, and Brent Waters. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. Cryptology ePrint Archive, Report 2013/340, 2013. URL: https://ia.cr/2013/340.
  16. Alex B. Grilo, Iordanis Kerenidis, and Timo Zijlstra. Learning-with-errors problem is easy with quantum samples. Physical Review A, 99(3), March 2019. URL: https://doi.org/10.1103/physreva.99.032314.
  17. Taiga Hiroka, Tomoyuki Morimae, Ryo Nishimaki, and Takashi Yamakawa. Certified everlasting zero-knowledge proof for qma, 2021. URL: http://arxiv.org/abs/2109.14163.
  18. Taiga Hiroka, Tomoyuki Morimae, Ryo Nishimaki, and Takashi Yamakawa. Quantum encryption with certified deletion, revisited: Public key, attribute-based, and classical communication, 2021. URL: http://arxiv.org/abs/2105.05393.
  19. Stanisław Jarecki and Anna Lysyanskaya. Adaptively secure threshold cryptography: Introducing concurrency, removing erasures. In Proceedings of the 19th International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT'00, pages 221-242, Berlin, Heidelberg, 2000. Springer-Verlag. Google Scholar
  20. Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa. Secure software leasing from standard assumptions, 2021. URL: http://arxiv.org/abs/2010.11186.
  21. Qipeng Liu and Mark Zhandry. Revisiting post-quantum fiat-shamir. Cryptology ePrint Archive, Paper 2019/262, 2019. URL: https://eprint.iacr.org/2019/262.
  22. Urmila Mahadev. Classical verification of quantum computations, 2018. URL: http://arxiv.org/abs/1804.01082.
  23. Daniele Micciancio and Oded Regev. Worst-case to average-case reductions based on gaussian measures. SIAM J. Comput., 37(1):267-302, 2007. URL: https://doi.org/10.1137/S0097539705447360.
  24. Jörn Müller-Quade and Dominique Unruh. Long-term security and universal composability. In Salil P. Vadhan, editor, Theory of Cryptography, pages 41-60, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. Google Scholar
  25. Daniele Perito and Gene Tsudik. Secure code update for embedded devices via proofs of secure erasure. Cryptology ePrint Archive, Report 2010/217, 2010. URL: https://ia.cr/2010/217.
  26. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM, 56(6):34:1-34:40, 2005. URL: https://doi.org/10.1145/1568318.1568324.
  27. R L Rivest, L Adleman, and M L Dertouzos. On data banks and privacy homomorphisms. Foundations of Secure Computation, Academia Press, pages 169-179, 1978. Google Scholar
  28. Bhaskar Roberts. Toward secure quantum money. Princeton University Senior Thesis, 2019. URL: http://arks.princeton.edu/ark:/88435/dsp01nc580q51r.
  29. Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, and Keita Xagawa. Efficient public key encryption based on ideal lattices. Cryptology ePrint Archive, Paper 2009/285, 2009. URL: https://eprint.iacr.org/2009/285.
  30. Dominique Unruh. Computationally binding quantum commitments. Cryptology ePrint Archive, Paper 2015/361, 2015. URL: https://eprint.iacr.org/2015/361.
  31. W. K. Wootters and W. H. Zurek. A single quantum cannot be cloned. Nature, 299(5886):802-803, October 1982. URL: https://doi.org/10.1038/299802a0.
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