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.
Category / Keywords: cryptographic protocols / quantum cryptography, public-key cryptography, secret-key cryptography, homomorphic encryption Original Publication (with major differences): IACR-CRYPTO-2015 Date: received 4 Jun 2015 Contact author: smjeffery at gmail com Available format(s): PDF | BibTeX Citation Version: 20150612:191847 (All versions of this report) Short URL: ia.cr/2015/551 Discussion forum: Show discussion | Start new discussion