Document Open Access Logo

Indistinguishability Obfuscation of Null Quantum Circuits and Applications

Authors James Bartusek, Giulio Malavolta

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.15.pdf
  • Filesize: 0.61 MB
  • 13 pages

Document Identifiers

Author Details

James Bartusek
  • University of California, Berkeley, CA, USA
Giulio Malavolta
  • Max Planck Institute for Security and Privacy, Bochum, Germany

Cite AsGet BibTex

James Bartusek and Giulio Malavolta. Indistinguishability Obfuscation of Null Quantum Circuits and Applications. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.15

Abstract

We study the notion of indistinguishability obfuscation for null quantum circuits (quantum null-iO). We present a construction assuming: - The quantum hardness of learning with errors (LWE). - Post-quantum indistinguishability obfuscation for classical circuits. - A notion of "dual-mode" classical verification of quantum computation (CVQC). We give evidence that our notion of dual-mode CVQC exists by proposing a scheme that is secure assuming LWE in the quantum random oracle model (QROM). Then we show how quantum null-iO enables a series of new cryptographic primitives that, prior to our work, were unknown to exist even making heuristic assumptions. Among others, we obtain the first witness encryption scheme for QMA, the first publicly verifiable non-interactive zero-knowledge (NIZK) scheme for QMA, and the first attribute-based encryption (ABE) scheme for BQP.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • Obfuscation
  • Witness Encryption
  • Classical Verification of Quantum Computation

Metrics

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

Related Versions

References

  1. Scott Aaronson. Ten semi-grand challenges for quantum computing theory, 2005. URL: https://www.scottaaronson.com/writings/qchallenge.html.
  2. Scott Aaronson and Paul Christiano. Quantum money from hidden subspaces. In Howard J. Karloff and Toniann Pitassi, editors, 44th ACM STOC, pages 41-60. ACM Press, May 2012. URL: https://doi.org/10.1145/2213977.2213983.
  3. Gorjan Alagic, Zvika Brakerski, Yfke Dulek, and Christian Schaffner. Impossibility of quantum virtual black-box obfuscation of classical circuits, 2020. URL: http://arxiv.org/abs/2005.06432.
  4. Gorjan Alagic, Andrew M. Childs, Alex B. Grilo, and Shih-Han Hung. Non-interactive classical verification of quantum computation. In TCC 2020, Part III, LNCS, pages 153-180. Springer, Heidelberg, March 2020. URL: https://doi.org/10.1007/978-3-030-64381-2_6.
  5. Gorjan Alagic and Bill Fefferman. On quantum obfuscation. CoRR, abs/1602.01771, 2016. URL: http://arxiv.org/abs/1602.01771.
  6. Gorjan Alagic, Stacey Jeffery, and Stephen Jordan. Circuit Obfuscation Using Braids. In Steven T. Flammia and Aram W. Harrow, editors, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014), volume 27 of Leibniz International Proceedings in Informatics (LIPIcs), pages 141-160, Dagstuhl, Germany, 2014. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.TQC.2014.141.
  7. Ryan Amos, Marios Georgiou, Aggelos Kiayias, and Mark Zhandry. One-shot signatures and applications to hybrid quantum/classical authentication. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, 52nd ACM STOC, pages 255-268. ACM Press, June 2020. URL: https://doi.org/10.1145/3357713.3384304.
  8. Prabhanjan Ananth and Rolando L. La Placa. Secure software leasing, 2020. URL: http://arxiv.org/abs/2005.05289.
  9. Saikrishna Badrinarayanan, Rex Fernando, Aayush Jain, Dakshita Khurana, and Amit Sahai. Statistical ZAP arguments. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part III, volume 12107 of LNCS, pages 642-667. Springer, Heidelberg, May 2020. URL: https://doi.org/10.1007/978-3-030-45727-3_22.
  10. Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. In Joe Kilian, editor, CRYPTO 2001, volume 2139 of LNCS, pages 1-18. Springer, Heidelberg, August 2001. URL: https://doi.org/10.1007/3-540-44647-8_1.
  11. James Bartusek and Giulio Malavolta. Indistinguishability obfuscation of null quantum circuits and applications, 2021. URL: http://arxiv.org/abs/2106.06094.
  12. Nir Bitansky, Omer Paneth, and Alon Rosen. On the cryptographic hardness of finding a Nash equilibrium. In Venkatesan Guruswami, editor, 56th FOCS, pages 1480-1498. IEEE Computer Society Press, October 2015. URL: https://doi.org/10.1109/FOCS.2015.94.
  13. Manuel Blum, Paul Feldman, and Silvio Micali. Non-interactive zero-knowledge and its applications (extended abstract). In 20th ACM STOC, pages 103-112. ACM Press, May 1988. URL: https://doi.org/10.1145/62212.62222.
  14. Dan Boneh and Brent Waters. Constrained pseudorandom functions and their applications. In Kazue Sako and Palash Sarkar, editors, ASIACRYPT 2013, Part II, volume 8270 of LNCS, pages 280-300. Springer, Heidelberg, December 2013. URL: https://doi.org/10.1007/978-3-642-42045-0_15.
  15. Elette Boyle, Shafi Goldwasser, and Ioana Ivan. Functional signatures and pseudorandom functions. In Hugo Krawczyk, editor, PKC 2014, volume 8383 of LNCS, pages 501-519. Springer, Heidelberg, March 2014. URL: https://doi.org/10.1007/978-3-642-54631-0_29.
  16. Zvika Brakerski. Quantum FHE (almost) as secure as classical. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part III, volume 10993 of LNCS, pages 67-95. Springer, Heidelberg, August 2018. URL: https://doi.org/10.1007/978-3-319-96878-0_3.
  17. Zvika Brakerski, Nico Döttling, Sanjam Garg, and Giulio Malavolta. Candidate iO from homomorphic encryption schemes. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part I, volume 12105 of LNCS, pages 79-109. Springer, Heidelberg, May 2020. URL: https://doi.org/10.1007/978-3-030-45721-1_4.
  18. Zvika Brakerski, Nico Döttling, Sanjam Garg, and Giulio Malavolta. Factoring and pairings are not necessary for io: Circular-secure lwe suffices. Cryptology ePrint Archive, Report 2020/1024, 2020. URL: https://eprint.iacr.org/2020/1024.
  19. Anne Broadbent and Alex B. Grilo. Zero-knowledge for qma from locally simulatable proofs, 2019. URL: http://arxiv.org/abs/1911.07782.
  20. Anne Broadbent and Raza Ali Kazmi. Indistinguishability obfuscation for quantum circuits of low t-count. Cryptology ePrint Archive, Report 2020/639, 2020. URL: https://eprint.iacr.org/2020/639.
  21. Nai-Hui Chia, Kai-Min Chung, and Takashi Yamakawa. Classical verification of quantum computations with efficient verifier. In TCC 2020, Part III, LNCS, pages 181-206. Springer, Heidelberg, March 2020. URL: https://doi.org/10.1007/978-3-030-64381-2_7.
  22. Andrea Coladangelo, Thomas Vidick, and Tina Zhang. Non-interactive zero-knowledge arguments for QMA, with preprocessing. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part III, volume 12172 of LNCS, pages 799-828. Springer, Heidelberg, August 2020. URL: https://doi.org/10.1007/978-3-030-56877-1_28.
  23. Cynthia Dwork and Moni Naor. Zaps and their applications. In 41st FOCS, pages 283-293. IEEE Computer Society Press, November 2000. URL: https://doi.org/10.1109/SFCS.2000.892117.
  24. Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. In 54th FOCS, pages 40-49. IEEE Computer Society Press, October 2013. URL: https://doi.org/10.1109/FOCS.2013.13.
  25. Sanjam Garg, Craig Gentry, Amit Sahai, and Brent Waters. Witness encryption and its applications. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, 45th ACM STOC, pages 467-476. ACM Press, June 2013. URL: https://doi.org/10.1145/2488608.2488667.
  26. Romain Gay and Rafael Pass. Indistinguishability obfuscation from circular security. Cryptology ePrint Archive, Report 2020/1010, 2020. URL: https://eprint.iacr.org/2020/1010.
  27. Shafi Goldwasser, S. Dov Gordon, Vipul Goyal, Abhishek Jain, Jonathan Katz, Feng-Hao Liu, Amit Sahai, Elaine Shi, and Hong-Sheng Zhou. Multi-input functional encryption. In Phong Q. Nguyen and Elisabeth Oswald, editors, EUROCRYPT 2014, volume 8441 of LNCS, pages 578-602. Springer, Heidelberg, May 2014. URL: https://doi.org/10.1007/978-3-642-55220-5_32.
  28. Shafi Goldwasser, Yael Tauman Kalai, Raluca A. Popa, Vinod Vaikuntanathan, and Nickolai Zeldovich. Reusable garbled circuits and succinct functional encryption. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, 45th ACM STOC, pages 555-564. ACM Press, June 2013. URL: https://doi.org/10.1145/2488608.2488678.
  29. Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee. Predicate encryption for circuits from LWE. In Rosario Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part II, volume 9216 of LNCS, pages 503-523. Springer, Heidelberg, August 2015. URL: https://doi.org/10.1007/978-3-662-48000-7_25.
  30. Rishab Goyal, Venkata Koppula, and Brent Waters. Lockable obfuscation. In Chris Umans, editor, 58th FOCS, pages 612-621. IEEE Computer Society Press, October 2017. URL: https://doi.org/10.1109/FOCS.2017.62.
  31. Vipul Goyal, Abhishek Jain, Zhengzhong Jin, and Giulio Malavolta. Statistical zaps and new oblivious transfer protocols. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part III, volume 12107 of LNCS, pages 668-699. Springer, Heidelberg, May 2020. URL: https://doi.org/10.1007/978-3-030-45727-3_23.
  32. Vipul Goyal, Omkant Pandey, Amit Sahai, and Brent Waters. Attribute-based encryption for fine-grained access control of encrypted data. In Ari Juels, Rebecca N. Wright, and Sabrina De Capitani di Vimercati, editors, ACM CCS 2006, pages 89-98. ACM Press, October / November 2006. Available as Cryptology ePrint Archive Report 2006/309. URL: https://doi.org/10.1145/1180405.1180418.
  33. Satoshi Hada. Zero-knowledge and code obfuscation. In Tatsuaki Okamoto, editor, ASIACRYPT 2000, volume 1976 of LNCS, pages 443-457. Springer, Heidelberg, December 2000. URL: https://doi.org/10.1007/3-540-44448-3_34.
  34. Ariel Hamlin, Justin Holmgren, Mor Weiss, and Daniel Wichs. On the plausibility of fully homomorphic encryption for RAMs. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part I, volume 11692 of LNCS, pages 589-619. Springer, Heidelberg, August 2019. URL: https://doi.org/10.1007/978-3-030-26948-7_21.
  35. Yael Tauman Kalai, Dakshita Khurana, and Amit Sahai. Statistical witness indistinguishability (and more) in two messages. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part III, volume 10822 of LNCS, pages 34-65. Springer, Heidelberg, April / May 2018. URL: https://doi.org/10.1007/978-3-319-78372-7_2.
  36. Aggelos Kiayias, Stavros Papadopoulos, Nikos Triandopoulos, and Thomas Zacharias. Delegatable pseudorandom functions and applications. In Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung, editors, ACM CCS 2013, pages 669-684. ACM Press, November 2013. URL: https://doi.org/10.1145/2508859.2516668.
  37. Ilan Komargodski, Moni Naor, and Eylon Yogev. Secret-sharing for NP. In Palash Sarkar and Tetsu Iwata, editors, ASIACRYPT 2014, Part II, volume 8874 of LNCS, pages 254-273. Springer, Heidelberg, December 2014. URL: https://doi.org/10.1007/978-3-662-45608-8_14.
  38. Urmila Mahadev. Classical homomorphic encryption for quantum circuits. In Mikkel Thorup, editor, 59th FOCS, pages 332-338. IEEE Computer Society Press, October 2018. URL: https://doi.org/10.1109/FOCS.2018.00039.
  39. Urmila Mahadev. Classical verification of quantum computations. In Mikkel Thorup, editor, 59th FOCS, pages 259-267. IEEE Computer Society Press, October 2018. URL: https://doi.org/10.1109/FOCS.2018.00033.
  40. Tomoyuki Morimae and Takashi Yamakawa. Classically verifiable (dual-mode) nizk for qma with preprocessing, 2021. URL: http://arxiv.org/abs/2102.09149.
  41. Moni Naor and Moti Yung. Public-key cryptosystems provably secure against chosen ciphertext attacks. In 22nd ACM STOC, pages 427-437. ACM Press, May 1990. URL: https://doi.org/10.1145/100216.100273.
  42. Amit Sahai and Brent Waters. How to use indistinguishability obfuscation: deniable encryption, and more. In David B. Shmoys, editor, 46th ACM STOC, pages 475-484. ACM Press, May / June 2014. URL: https://doi.org/10.1145/2591796.2591825.
  43. Amit Sahai and Brent R. Waters. Fuzzy identity-based encryption. In Ronald Cramer, editor, EUROCRYPT 2005, volume 3494 of LNCS, pages 457-473. Springer, Heidelberg, May 2005. URL: https://doi.org/10.1007/11426639_27.
  44. Omri Shmueli. Multi-theorem (malicious) designated-verifier nizk for qma. Cryptology ePrint Archive, Report 2020/928, 2020. Google Scholar
  45. Hoeteck Wee and Daniel Wichs. Candidate obfuscation via oblivious lwe sampling. Cryptology ePrint Archive, Report 2020/1042, 2020. URL: https://eprint.iacr.org/2020/1042.
  46. Daniel Wichs and Giorgos Zirdelis. Obfuscating compute-and-compare programs under LWE. In Chris Umans, editor, 58th FOCS, pages 600-611. IEEE Computer Society Press, October 2017. URL: https://doi.org/10.1109/FOCS.2017.61.
  47. Mark Zhandry. Quantum lightning never strikes the same state twice. In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, Part III, volume 11478 of LNCS, pages 408-438. Springer, Heidelberg, May 2019. URL: https://doi.org/10.1007/978-3-030-17659-4_14.
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