Quantum Homomorphic Encryption for Polynomial-Size Circuits

by Yfke Dulek, Christian Schaffner, and Florian Speelman

Theory of Computing, Volume 14(7), pp. 1-45, 2018

Bibliography with links to cited articles

[1]   Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu, and Elham Kashefi: On the implausibility of classical client blind quantum computing, 2017. [arXiv:1704.08482]

[2]   Dorit Aharonov, Michael Ben-Or, and Elad Eban: Interactive proofs for quantum computations. In Proc. 1st Innovations in Computer Science Conf. (ICS’10), pp. 453–469, 2010. [arXiv:1704.04487]

[3]   Gorjan Alagic, Anne Broadbent, Bill Fefferman, Tommaso Gagliardoni, Christian Schaffner, and Michael St. Jules: Computational security of quantum encryption. In Proc. 9th Internat. Conf. on Information Theoretic Security (ICITS’16), pp. 47–71. Springer, 2016. [doi:10.1007/978-3-319-49175-2_3, arXiv:1602.01441]

[4]   Gorjan Alagic and Bill Fefferman: On quantum obfuscation, 2016. [arXiv:1602.01771]

[5]   Pablo Arrighi and Louis Salvail: Blind quantum computation. Internat. J. Quantum Information, 4(5):883–898, 2006. [doi:10.1142/S0219749906002171, arXiv:quant-ph/0309152]

[6]   Gilad Asharov, Abhishek Jain, Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan, and Daniel Wichs: Multiparty computation with low communication, computation and interaction via threshold FHE. In Proc. 31st Internat. Conf. on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’12), pp. 483–501. Springer, 2012. Cryptology Archive. [doi:10.1007/978-3-642-29011-4_29]

[7]   David A. Barrington: Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. J. Comput. System Sci., 38(1):150–164, 1989. Preliminary version in STOC’86. [doi:10.1016/0022-0000(89)90037-8]

[8]   Ämin Baumeler and Anne Broadbent: Quantum private information retrieval has linear communication complexity. Journal of Cryptology, 28(1):161–175, 2015. [doi:10.1007/s00145-014-9180-2, arXiv:1304.5490]

[9]   Michael Ben-Or, Claude Crépeau, Daniel Gottesman, Avinatan Hassidim, and Adam Smith: Secure multiparty quantum computation with (only) a strict honest majority. In Proc. 47th FOCS, pp. 249–260. IEEE Comp. Soc. Press, 2006. [doi:10.1109/FOCS.2006.68, arXiv:0801.1544]

[10]   Dan Boneh, Eu-Jin Goh, and Kobbi Nissim: Evaluating 2-DNF formulas on ciphertexts. In Proc. 2nd Theory of Cryptography Conf. (TCC’05), pp. 325–341. Springer, 2005. [doi:10.1007/978-3-540-30576-7_18]

[11]   Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan: (Leveled) fully homomorphic encryption without bootstrapping. ACM Trans. Comput. Theory, 6(3):13:1–13:36, 2014. Preliminary version in ITCS’12. Cryptology Archive. [doi:10.1145/2633600]

[12]   Zvika Brakerski and Vinod Vaikuntanathan: Efficient fully homomorphic encryption from (standard) LWE. SIAM J. Comput., 43(2):831–871, 2014. Preliminary version in FOCS’11. Cryptology Archive. [doi:10.1137/120868669]

[13]   Anne Broadbent: Delegating private quantum computations. Canadian Journal of Physics, 93(9):941–946, 2015. [doi:10.1139/cjp-2015-0030, arXiv:1506.01328]

[14]   Anne Broadbent: Popescu-Rohrlich correlations imply efficient instantaneous nonlocal quantum computation. Phys. Rev. A, 94(2):022318, 2016. [doi:10.1103/PhysRevA.94.022318, arXiv:1512.04930]

[15]   Anne Broadbent, Joseph Fitzsimons, and Elham Kashefi: Universal blind quantum computation. In Proc. 50th FOCS, pp. 517–526. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.36, arXiv:0807.4154]

[16]   Anne Broadbent and Stacey Jeffery: Quantum homomorphic encryption for circuits of low T-gate complexity. In Proc. 35th Ann. Internat. Cryptology Conf. (CRYPTO’15), pp. 609–629. Springer, 2015. [doi:10.1007/978-3-662-48000-7_30, arXiv:1412.8766]

[17]   Harry Buhrman, Serge Fehr, Christian Schaffner, and Florian Speelman: The garden-hose model. In Proc. 4th Innovations in Theoretical Computer Science Conf. (ITCS’13), pp. 145–158. ACM Press, 2013. [doi:10.1145/2422436.2422455, arXiv:1109.2563]

[18]   Andrew M. Childs: Secure assisted quantum computation. Quantum Inf. Comput., 5(6):456–466, 2005. ACM DL link. [arXiv:quant-ph/0111046]

[19]   Well Y. Chiu, Mario Szegedy, Chengu Wang, and Yixin Xu: The garden hose complexity for the equality function. In Proc. 10th Internat. Conf. on Algorithmic Aspects in Information and Management (AAIM’14), pp. 112–123. Springer, 2014. [doi:10.1007/978-3-319-07956-1_11, arXiv:1312.7222]

[20]   Benny Chor, Eyal Kushilevitz, Oded Goldreich, and Madhu Sudan: Private information retrieval. J. ACM, 45(6):965–981, 1998. Preliminary version in FOCS’95. [doi:10.1145/293347.293350]

[21]   Ronald Cramer, Ivan Damgård, and Jesper Buus Nielsen: Multiparty computation from threshold homomorphic encryption. In Proc. 20th Internat. Conf. on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’01), pp. 280–299. Springer, 2001. Cryptology Archive. [doi:10.1007/3-540-44987-6_18]

[22]   Yfke Dulek, Christian Schaffner, and Florian Speelman: Quantum homomorphic encryption for polynomial-sized circuits. In Proc. 36th Ann. Internat. Cryptology Conf. (CRYPTO’16), pp. 3–32. Springer, 2016. [doi:10.1007/978-3-662-53015-3_1, arXiv:1603.09717]

[23]   Frédéric Dupuis, Jesper Buus Nielsen, and Louis Salvail: Secure two-party quantum evaluation of unitaries against specious adversaries. In Proc. 30th Ann. Internat. Cryptology Conf. (CRYPTO’10), pp. 685–706. Springer, 2010. [doi:10.1007/978-3-642-14623-7_37, arXiv:1009.2096]

[24]   Maximilian Fillinger: Lattice based cryptography and fully homomorphic encryption, 2012. Available here.

[25]   Kent A. G. Fisher, Anne Broadbent, Lynden K. Shalm, Zhenya Yan, Jonathan Lavoie, Robert Prevedel, Thomas Jennewein, and Kevin J. Resch: Quantum computing on encrypted data. Nature Communications, 5(3074), 2014. [doi:10.1038/ncomms4074, arXiv:1309.2586]

[26]   Joseph F. Fitzsimons: Private quantum computation: An introduction to blind quantum computing and related protocols. npj Quantum Information, 3(23), 2017. [doi:10.1038/s41534-017-0025-3, arXiv:1611.10107]

[27]   Tommaso Gagliardoni, Andreas Hülsing, and Christian Schaffner: Semantic security and indistinguishability in the quantum world. In Proc. 36th Ann. Internat. Cryptology Conf. (CRYPTO’16), pp. 60–89. Springer, 2016. [doi:10.1007/978-3-662-53015-3_3, arXiv:1504.05255]

[28]   Shelly Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Anant Sahai, and Brent Waters: Candidate indistinguishability obfuscation and functional encryption for all circuits. SIAM J. Comput., 45(3):882–929, 2016. Preliminary version in FOCS’13. Cryptology Archive. [doi:10.1137/14095772X]

[29]   Craig Gentry: Fully homomorphic encryption using ideal lattices. In Proc. 41st STOC, pp. 169–178. ACM Press, 2009. [doi:10.1145/1536414.1536440]

[30]   Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan: A simple BGN-type cryptosystem from LWE. In Proc. 29th Internat. Conf. on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’10), pp. 506–522. Springer, 2010. Cryptology Archive. [doi:10.1007/978-3-642-13190-5_26]

[31]    Shafi Goldwasser, Yael Kalai, Raluca Ada Popa, Vinod Vaikuntanathan, and Nickolai Zeldovich: How to run Turing machines on encrypted data. In Proc. 33rd Ann. Internat. Cryptology Conf. (CRYPTO’13), pp. 536–553. Springer, 2013. [doi:10.1007/978-3-642-40084-1_30]

[32]   Shafi Goldwasser, Yael Kalai, Raluca Ada Popa, Vinod Vaikuntanathan, and Nickolai Zeldovich: Reusable garbled circuits and succinct functional encryption. In Proc. 45th STOC, pp. 555–564. ACM Press, 2013. Cryptology Archive. [doi:10.1145/2488608.2488678]

[33]    Shafi Goldwasser and Silvio Micali: Probabilistic encryption. J. Comput. System Sci., 28(2):270–299, 1984. [doi:10.1016/0022-0000(84)90070-9]

[34]   Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee: Attribute-based encryption for circuits. J. ACM, 62(6):45:1–45:33, 2015. Preliminary version in STOC’13. Cryptology Archive. [doi:10.1145/2824233]

[35]   Daniel Gottesman: Theory of fault-tolerant quantum computation. Phys. Rev. A, 57(1):127–137, 1998. [doi:10.1103/PhysRevA.57.127, arXiv:quant-ph/9702029]

[36]   Daniel Gottesman and Isaac L. Chuang: Quantum Teleportation is a Universal Computational Primitive. Nature, 402:390–393, 1999. [doi:10.1038/46503, arXiv:quant-ph/9908010]

[37]   Yuval Ishai and Anat Paskin: Evaluating branching programs on encrypted data. In Proc. 4th Theory of Cryptography Conf. (TCC’07), pp. 575–594. Springer, 2007. Cryptology Archive. [doi:10.1007/978-3-540-70936-7_31]

[38]   Hartmut Klauck and Supartha Podder: New bounds for the garden-hose model. In Proc. 34th IARCS Ann. Conf. on Foundations of Software Tech. and Theor. Comput. Sci. (FSTTCS’14), pp. 481–492. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2014. [doi:10.4230/LIPIcs.FSTTCS.2014.481, arXiv:1412.4904]

[39]   Eyal Kushilevitz and Rafail Ostrovsky: Replication is not needed: Single database, computationally-private information retrieval. In Proc. 38th FOCS, pp. 364–373. IEEE Comp. Soc. Press, 1997. [doi:10.1109/SFCS.1997.646125]

[40]   Min Liang: Symmetric quantum fully homomorphic encryption with perfect security. Quantum Information Processing, 12(12):3675–3687, 2013. [doi:10.1007/s11128-013-0626-5, arXiv:1304.5087]

[41]   Min Liang: Quantum fully homomorphic encryption scheme based on universal quantum circuit. Quantum Information Processing, 14(8):2749–2759, 2015. [doi:10.1007/s11128-015-1034-9, arXiv:1410.2435]

[42]   Oded Margalit: On the riddle of coding equality function in the garden hose model. In Proc. 2014Information Theory and Applications Workshop (ITA’14), pp. 1–5. IEEE Comp. Soc. Press, 2014. [doi:10.1109/ITA.2014.6804262]

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

[44]   Yingkai Ouyang, Si-Hui Tan, and Joseph Fitzsimons: Quantum homomorphic encryption from quantum codes, 2015. [arXiv:1508.00938]

[45]   Pascal Paillier: Public-key cryptosystems based on composite degree residuosity classes. In Proc. 18th Internat. Conf. on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’99), pp. 223–238. Springer, 1999. [doi:10.1007/3-540-48910-X_16]

[46]   Ronald L. Rivest, Len Adleman, and Michael L. Dertouzos: On data banks and privacy homomorphisms. Foundations of Secure Computation, 4(11):169–180, 1978. LINK.

[47]   Ronald L. Rivest, Adi Shamir, and Len Adleman: A method for obtaining digital signatures and public-key cryptosystems. Comm. ACM, 21(2):120–126, 1978. [doi:10.1145/359340.359342]

[48]   Peter P. Rohde, Joseph F. Fitzsimons, and Alexei Gilchrist: Quantum walks with encrypted data. Phys. Rev. Lett., 109(15):150501, 2012. [doi:10.1103/PhysRevLett.109.150501, arXiv:1204.3370]

[49]    Amit Sahai and Brent Waters: How to use indistinguishability obfuscation: Deniable encryption, and more. In Proc. 46th STOC, pp. 475–484. ACM Press, 2014. Cryptology Archive. [doi:10.1145/2591796.2591825]

[50]   Tomas Sander, Adam Young, and Moti Yung: Non-interactive cryptocomputing for NC1. In Proc. 40th FOCS, pp. 554–566. IEEE Comp. Soc. Press, 1999. [doi:10.1109/SFFCS.1999.814630]

[51]   Dan Shepherd and Michael J. Bremner: Temporally unstructured quantum computation. Proc. Royal Soc. A, 465(2105):1413–1439, 2009. [doi:10.1098/rspa.2008.0443]

[52]   Florian Speelman: Position-Based Quantum Cryptography and the Garden-Hose Game. Master’s thesis, University of Amsterdam, 2011. [arXiv:1210.4353]

[53]   Florian Speelman: Instantaneous non-local computation of low T-depth quantum circuits. In Proc. 11th Conf. Theory of Quantum Comput., Communic. and Cryptography (TQC’16), pp. 9:1–9:24. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.TQC.2016.9, arXiv:1511.02839]

[54]   Si-Hui Tan, Joshua A. Kettlewell, Yingkai Ouyang, Lin Chen, and Joseph F. Fitzsimons: A quantum approach to homomorphic encryption. Scientific Reports, 6, 2016. [doi:10.1038/srep33467, arXiv:1411.5254]

[55]   Vinod Vaikuntanathan: Computing blindfolded: New developments in fully homomorphic encryption. In Proc. 52nd FOCS, pp. 5–16. IEEE Comp. Soc. Press, 2011. [doi:10.1109/FOCS.2011.98]

[56]   Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan: Fully homomorphic encryption over the integers. In Proc. 29th Internat. Conf. on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’10), volume 6110, pp. 24–43. Springer, 2010. Cryptology Archive. [doi:10.1007/978-3-642-13190-5_2]

[57]   Dunjko Vedran, Joseph F. Fitzsimons, Christopher Portmann, and Renato Renner: Composable security of delegated quantum computation. In Proc. 20th Internat. Conf. on the Theory and Application of Cryptology and Information Security (ASIACRYPT’14), pp. 406–425. Springer, 2014. [doi:10.1007/978-3-662-45608-8_22, arXiv:1301.3662]

[58]   Li Yu, Carlos A. Pérez-Delgado, and Joseph F. Fitzsimons: Limitations on information-theoretically secure quantum homomorphic encryption. Phys. Rev. A, 90(5), 2014. [doi:10.1103/PhysRevA.90.050303, arXiv:1406.2456]