CaltechAUTHORS
  A Caltech Library Service

Quantum homomorphic encryption for circuits of low T-gate complexity

Broadbent, Anne and Jeffery, Stacey (2015) Quantum homomorphic encryption for circuits of low T-gate complexity. In: Advances in Cryptology. Lecture Notes in Computer Science. No.9216. Springer , Berlin, pp. 609-629. ISBN 978-3-662-47999-5. http://resolver.caltech.edu/CaltechAUTHORS:20150521-152945536

[img] PDF - Submitted Version
See Usage Policy.

731Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20150521-152945536

Abstract

Fully homomorphic encryption is an encryption method with the property that any computation on the plaintext can be performed by a party having access to the ciphertext only. Here, we formally define and give schemes for quantum homomorphic encryption, which is the encryption of quantum information such that quantum computations can be performed given the ciphertext only. Our schemes allow for arbitrary Clifford group gates, but become inefficient for circuits with large complexity, measured in terms of the non-Clifford portion of the circuit (we use the “π/8” non-Clifford group gate, also known as the T-gate). More specifically, two schemes are proposed: the first scheme has a decryption procedure whose complexity scales with the square of the number of T-gates (compared with a trivial scheme in which the complexity scales with the total number of gates); the second scheme uses a quantum evaluation key of length given by a polynomial of degree exponential in the circuit’s T-gate depth, yielding a homomorphic scheme for quantum circuits with constant T-depth. Both schemes build on a classical fully homomorphic encryption scheme. A further contribution of ours is to formally define the security of encryption schemes for quantum messages: we define quantum indistinguishability under chosen plaintext attacks in both the public- and private-key settings. In this context, we show the equivalence of several definitions. Our schemes are the first of their kind that are secure under modern cryptographic definitions, and can be seen as a quantum analogue of classical results establishing homomorphic encryption for circuits with a limited number of multiplication gates. Historically, such results appeared as precursors to the breakthrough result establishing classical fully homomorphic encryption.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/1412.8766arXivDiscussion Paper
https://www.iacr.org/conferences/crypto2015/acceptedpapers.htmlOrganizationConference Website
http://dx.doi.org/10.1007/978-3-662-48000-7_30DOIArticle
http://link.springer.com/chapter/10.1007%2F978-3-662-48000-7_30PublisherArticle
Additional Information:© 2015 International Association for Cryptologic Research. The authors would like to thank Fang Song for helpful discussions about this paper, in particular regarding security definitions. A. B. acknowledges support from the Canadian Institute for Advanced Research (Cifar); A. B. and S. J. acknowledge support from the Natural Sciences and Engineering Research Council of Canada (Nserc). Part of this work was done while the authors were visitors at the Simons Institute for the Theory of Computing.
Group:IQIM, Institute for Quantum Information and Matter
Funders:
Funding AgencyGrant Number
Canadian Institute for Advanced Research (CIfAR)UNSPECIFIED
Natural Sciences and Engineering Research Council of Canada (NSERC)UNSPECIFIED
Record Number:CaltechAUTHORS:20150521-152945536
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20150521-152945536
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:57750
Collection:CaltechAUTHORS
Deposited By: Stacey Jeffery
Deposited On:05 Jun 2015 18:29
Last Modified:08 Dec 2015 21:48

Repository Staff Only: item control page