Paper 2015/551

Quantum homomorphic encryption for circuits of low $T$-gate complexity

Anne Broadbent and Stacey Jeffery

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 \emph{quantum} homomorphic encryption, which is the encryption of \emph{quantum} information such that \emph{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 ``$\pi/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 \emph{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 \emph{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 \emph{multiplication} gates. Historically, such results appeared as precursors to the breakthrough result establishing classical fully homomorphic encryption.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2015
Keywords
quantum cryptographypublic-key cryptographysecret-key cryptographyhomomorphic encryption
Contact author(s)
smjeffery @ gmail com
History
2015-06-12: received
Short URL
https://ia.cr/2015/551
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/551,
      author = {Anne Broadbent and Stacey Jeffery},
      title = {Quantum homomorphic encryption for circuits of low $T$-gate complexity},
      howpublished = {Cryptology ePrint Archive, Paper 2015/551},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/551}},
      url = {https://eprint.iacr.org/2015/551}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.