Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2016 | OriginalPaper | Buchkapitel

Quantum Homomorphic Encryption for Polynomial-Sized Circuits

verfasst von : Yfke Dulek, Christian Schaffner, Florian Speelman

Erschienen in: Advances in Cryptology – CRYPTO 2016

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We present a new scheme for quantum homomorphic encryption which is compact and allows for efficient evaluation of arbitrary polynomial-sized quantum circuits. Building on the framework of Broadbent and Jeffery [BJ15] and recent results in the area of instantaneous non-local quantum computation [Spe15], we show how to construct quantum gadgets that allow perfect correction of the errors which occur during the homomorphic evaluation of T gates on encrypted quantum data. Our scheme can be based on any classical (leveled) fully homomorphic encryption (FHE) scheme and requires no computational assumptions besides those already used by the classical scheme. The size of our quantum gadget depends on the space complexity of the classical decryption function – which aligns well with the current efforts to minimize the complexity of the decryption function.
Our scheme (or slight variants of it) offers a number of additional advantages such as ideal compactness, the ability to supply gadgets “on demand”, and circuit privacy for the evaluator against passive adversaries.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Nächstes Kapitel Adaptive Versus Non-Adaptive Strategies in the Quantum Setting with Applications
Fußnoten
1
Here and throughout the article, we use “classical” to mean “non-quantum”.
 
2
In contrast to blind or delegated quantum computation where some interaction between client and server is usually required, see Sect. 1.2 for references.
 
3
This term is not related to the term ‘instantaneous quantum computation’ [SB08], and instead first was used as a specific form of non-local quantum computation, one where all parties have to act simultaneously.
 
4
A negligible function \(\eta \) is a function such that for every positive integer d, \(\eta (n) < 1/n^d\) for big enough n.
 
5
Note that there various ways to define passive adversaries in the quantum setting [DNS10, BB14]. Here, we are considering adversaries that follow all protocol instructions exactly.
 
6
This can be seen by inserting dummy instructions that always perform the identity permutation between any two consecutive instructions that depend on the same variable. Alternatively, it would be possible to improve the construction by ‘multiplying out’ consecutive instructions whenever they depend on the same variable.
 
Literatur
[ABF+16]
Alagic, G., Broadbent, A., Fefferman, B., Gagliardoni, T., Schaffner, C., St. Jules, M.: Computational security of quantum encryption (2016). arXiv preprint arXiv:​1602.​01441
[ABOE10]
Aharonov, D., Ben-Or, M., Eban, E.: Interactive proofs for quantum computations. In: Proceeding of Innovations in Computer Science (ICS 2010), pp. 453–469 (2010)
[AF16]
[AJLA+12]
Asharov, G., Jain, A., López-Alt, A., Tromer, E., Vaikuntanathan, V., Wichs, D.: Multiparty computation with low communication, computation and interaction via threshold FHE. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 483–501. Springer, Heidelberg (2012)CrossRef
[AS06]
Arrighi, P., Salvail, L.: Blind quantum computation. Int. J. Quantum Inf. 4(05), 883–898 (2006)CrossRefMATH
[Bar89]
Barrington, D.A.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. J. Comput. Syst. Sci. 164, 150–164 (1989)MathSciNetCrossRefMATH
[BB14]
Baumeler, Ä., Broadbent, A.: Quantum private information retrieval has linear communication complexity. J. Cryptol. 28(1), 161–175 (2014)MathSciNetCrossRefMATH
[BCG+06]
Ben-Or, M., Crépeau, C., Gottesman, D., Hassidim, A., Smith, A.: Secure multiparty quantum computation with (only) a strict honest majority. In: 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 249–260 (2006)
[BFK09]
Broadbent, A., Fitzsimons, J., Kashefi, E.: Universal blind quantum computation. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, pp. 517–526. IEEE (2009)
[BFSS13]
Buhrman, H., Fehr, S., Schaffner, C., Speelman, F.: The garden-hose model. In: Proceedings of the 4th Innovations in Theoretical Computer Science Conference, pp. 145–158. ACM (2013)
[BGN05]
Boneh, D., Goh, E.-J., Nissim, K.: Evaluating 2-DNF formulas on ciphertexts. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 325–341. Springer, Heidelberg (2005)CrossRef
[BGV12]
Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pp. 309–325. ACM (2012)
[BJ15]
Broadbent, A., Jeffery, S.: Quantum homomorphic encryption for circuits of low T-gate complexity. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 609–629. Springer, Heidelberg (2015)CrossRef
[Bro15a]
Broadbent, A.: Delegating private quantum computations. Can. J. Phys. 93(9), 941–946 (2015)CrossRef
[Bro15b]
Broadbent, A.: Popescu-Rohrlich correlations imply efficient instantaneous nonlocal quantum computation (2015). arXiv preprint arXiv:​1512.​04930
[BV11]
Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 97–106, October 2011
[CDN01]
Cramer, R., Damgård, I.B., Nielsen, J.B.: Multiparty computation from threshold homomorphic encryption. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 280–300. Springer, Heidelberg (2001)CrossRef
[Chi05]
Childs, A.M.: Secure assisted quantum computation. Quantum Inf. Comput. 5(6), 456–466 (2005)MathSciNetMATH
[CKGS98]
[CSWX14]
Chiu, W.Y., Szegedy, M., Wang, C., Xu, Y.: The garden hose complexity for the equality function. In: Gu, Q., Hell, P., Yang, B. (eds.) AAIM 2014. LNCS, vol. 8546, pp. 112–123. Springer, Heidelberg (2014)
[DNS10]
Dupuis, F., Nielsen, J.B., Salvail, L.: Secure two-party quantum evaluation of unitaries against specious adversaries. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 685–706. Springer, Heidelberg (2010)CrossRef
[FBS+14]
Fisher, K.A.G., Broadbent, A., Shalm, L.K., Yan, Z., Lavoie, J., Prevedel, R., Jennewein, T., Resch, K.J.: Quantum computing on encrypted data. Nat. Commun. 5 (2014). Article number: 3074
[Fil12]
[GC99]
Gottesman, D., Chuang, I.L.: Quantum teleportation is a universal computational primitive. Nature 402, 390–393 (1999)CrossRef
[Gen09]
Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC, vol. 9, pp. 169–178 (2009)
[GGH+13]
Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pp. 40–49. IEEE (2013)
[GHS15]
Gagliardoni, T., Hülsing, A., Schaffner, C.: Semantic security, indistinguishability in the quantum world (2015). arXiv preprint arXiv:​1504.​05255
[GHV10]
Gentry, C., Halevi, S., Vaikuntanathan, V.: A simple BGN-type cryptosystem from LWE. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 506–522. Springer, Heidelberg (2010)CrossRef
[GKP+13a]
Goldwasser, S., Kalai, Y.T., Popa, R.A., Vaikuntanathan, V., Zeldovich, N.: How to run turing machines on encrypted data. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 536–553. Springer, Heidelberg (2013)CrossRef
[GKP+13b]
Goldwasser, S., Kalai, Y., Popa, R.A., Vaikuntanathan, V., Zeldovich, N.: Reusable garbled circuits and succinct functional encryption. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing, STOC 2013, pp. 555–564 (2013)
[GM84]
[Got98]
Gottesman, D.: Theory of fault-tolerant quantum computation. Phys. Rev. A 57, 127–137 (1998)CrossRef
[GVW13]
Gorbunov, S., Vaikuntanathan, V., Wee, H.: Attribute-based encryption for circuits. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing, STOC 2013, pp. 545–554 (2013)
[IP07]
Ishai, Y., Paskin, A.: Evaluating branching programs on encrypted data. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 575–594. Springer, Heidelberg (2007)CrossRef
[KO97]
Kushilevitz, E., Ostrovsky, R.: Replication is not needed: single database, computationally-private information retrieval. In: FOCS, p. 364. IEEE (1997)
[KP14]
Klauck, H., Podder, S.: New bounds for the garden-hose model. In: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, pp. 481–492 (2014)
[Lia13]
Liang, M.: Symmetric quantum fully homomorphic encryption with perfect security. Quantum Inf. Process. 12(12), 3675–3687 (2013)MathSciNetCrossRefMATH
[Lia15]
Liang, M.: Quantum fully homomorphic encryption scheme based on universal quantum circuit. Quantum Inf. Process. 14(8), 2749–2759 (2015)MathSciNetCrossRefMATH
[Mar14]
Margalit, O.: On the riddle of coding equality function in the garden hose model. In: Information Theory and Applications Workshop (ITA), pp. 1–5. IEEE (2014)
[NC00]
Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)MATH
[OTF15]
Ouyang, Y., Tan, S.-H., Fitzsimons, J.: Quantum homomorphic encryption from quantum codes (2015). arXiv preprint arXiv:​1508.​00938
[Pai99]
Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999)CrossRef
[RAD78]
Rivest, R.L., Adleman, L., Dertouzos, M.L.: On data banks, privacy homomorphisms. Found. Secur. Comput. 4(11), 169–180 (1978)MathSciNet
[RFG12]
Rohde, P.P., Fitzsimons, J.F., Gilchrist, A.: Quantum walks with encrypted data. Phys. Rev. Lett. 109(15), 150501 (2012)CrossRef
[RSA78]
Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)MathSciNetCrossRefMATH
[SB08]
[Spe11]
Speelman, F.: Position-based quantum cryptography, the garden-hose game. Master’s thesis, University of Amsterdam. arXiv:​1210.​4353
[Spe15]
[SW14]
Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC 2014, pp. 475–484 (2014)
[SYY99]
Sander, T., Young, A., Yung, M.: Non-interactive cryptocomputing for NC1. In: 40th Annual Symposium on Foundations of Computer Science, pp. 554–566. IEEE (1999)
[TKO+14]
Tan, S.-H., Kettlewell, J.A., Ouyang, Y., Chen, L., Fitzsimons, J.F.: A quantum approach to fully homomorphic encryption (2014). arXiv preprint arXiv:​1411.​5254
[Vai11]
Vaikuntanathan, V.: Computing blindfolded: new developments in fully homomorphic encryption. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 5–16. IEEE (2011)
[VDGHV10]
van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 24–43. Springer, Heidelberg (2010)CrossRef
[VFPR14]
Dunjko, V., Fitzsimons, J.F., Portmann, C., Renner, R.: Composable security of delegated quantum computation. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, Part II. LNCS, vol. 8874, pp. 406–425. Springer, Heidelberg (2014)
[YPDF14]
Li, Y., Pérez-Delgado, C.A., Fitzsimons, J.F.: Limitations on information-theoretically-secure quantum homomorphic encryption. Phys. Rev. A 90, 050303 (2014)CrossRef
Metadaten
Titel
Quantum Homomorphic Encryption for Polynomial-Sized Circuits
verfasst von
Yfke Dulek
Christian Schaffner
Florian Speelman
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Advances in Cryptology – CRYPTO 2016

Print ISBN: 978-3-662-53014-6

Electronic ISBN: 978-3-662-53015-3

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-662-53015-3_1

Premium Partner

    Bildnachweise