PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Anne Broadbent, Stacey Jeffery

arXiv:1412.8766v2quant-ph

TL;DR

The paper addresses how to perform quantum computations on encrypted quantum information under computational security. It formally defines quantum homomorphic encryption and proposes schemes built from classical fully homomorphic encryption, with efficiency constrained by non-Clifford complexity. The schemes support Clifford circuits broadly, while EPR and AUX provide different trade-offs for T-gate count and T-depth.

  • Problem

    Computationally secure quantum fully homomorphic encryption remained open, while prior perfect-security results found the trivial scheme optimal.

  • Method

    The paper defines public-key and symmetric-key QHE security and constructs CL, EPR, and AUX using quantum one-time pads, classical fully homomorphic encryption, entanglement, and auxiliary qubits.

  • Results

    The schemes are secure under quantum indistinguishability under chosen-plaintext attacks; CL handles Clifford circuits, EPR handles all quantum circuits with T-gate-dependent decryption, and AUX is efficient for constant T-depth.

  • Takeaways & Limitations

    Quantum homomorphic encryption can support substantial quantum circuit classes under computational assumptions, with efficiency governed by the circuit’s non-Clifford complexity.

  • Takeaways & Limitations

    AUX has complexity doubly exponential in T-depth and therefore is restricted to circuits with constant T-depth.

Abstract

from arXiv · show

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 allows 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, which is 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.

1 Introduction

The paper develops quantum homomorphic encryption as a computational analogue of classical homomorphic encryption, targeting encrypted quantum computation while addressing security and circuit-complexity constraints. It introduces formal security definitions and three schemes whose efficiency depends on Clifford structure and T-gate complexity.

  • Motivation and definitions: Computationally secure QFHE was open after prior work found the trivial scheme optimal under perfect security and correctness.The paper therefore studies computational assumptions as a route toward broader quantum homomorphic functionality.
  • Motivation and definitions: Quantum homomorphic encryption enables quantum circuits to be evaluated on encrypted quantum data.The paper positions QHE as the quantum version of homomorphic encryption.
  • Motivation and definitions: The paper gives the first computational QHE definitions for public-key and symmetric-key systems, including quantum indistinguishability under chosen-plaintext attacks.It also establishes equivalence among several security definitions, including multiple-message security.
  • Scheme construction: CL is homomorphic and compact for Clifford or stabilizer circuits, using a quantum one-time pad combined with classical fully homomorphic encryption.This extends a classical linear-circuit analogue and supports applications such as stabilizer-code encoding and decoding.
  • Scheme construction: EPR evaluates all quantum circuits, but its decryption complexity scales with the square of the number of T-gates and therefore loses compactness.It improves over the trivial scheme when the number of T-gates is less than the square root of the total number of gates.
  • Scheme construction: AUX uses auxiliary qubits in the evaluation key, whose length has polynomial degree exponential in T-gate depth, making it efficient for constant T-depth circuits.EPR and AUX trade off different complexity measures and are incomparable across circuits.

2 Preliminaries and Notation

The preliminaries establish notation for quantum states, registers, channels, measurements, circuits, and the gate structure used throughout the paper. They emphasize Clifford gates as the easy portion of quantum circuits and T-gates as the non-Clifford component governing T-depth.

  • Quantum information notation: A quantum register is modeled by density operators, namely trace-1 positive semidefinite operators on a complex Euclidean space.The notation D(X) denotes the set of density operators on space X.
  • Quantum information notation: Composite quantum systems use tensor products, while reduced states are obtained with the partial trace.Registers of equal dimension may be denoted as equivalent.
  • Quantum information notation: Quantum channels are physically realizable mappings between quantum registers, and an identity channel acts trivially on the specified register.Channels acting on part of a joint state implicitly act as the identity elsewhere.
  • Circuit notation: The gates X, Z, P, CNOT, and H generate the Clifford group, while adding T yields a universal generating set for quantum circuits.The preliminaries record the algebraic relations among these gates.
  • Circuit notation: T-depth is the number of layers containing T-gates in a layered circuit alternating with layers of Clifford gates.Clifford gates serve as the quantum analogue of classical additions, while T-gates correspond to multiplications.
  • Quantum encryption notation: The quantum one-time pad encrypts a single-qubit register using random X and Z operations, with decryption undoing the same operation.Uniformly random pad keys make the encrypted state completely mixed from the adversary’s perspective.

3 Definitions

This section defines quantum homomorphic encryption, its security notions, functionality, and correctness-related properties, including public-key and symmetric-key settings. It also establishes equivalence between single-message and multiple-message quantum CPA security definitions.

  • Quantum-specific considerations: The definitions account for quantum-specific decryption constraints and leave circuit privacy unaddressed.Because auxiliary quantum decryption information cannot be copied, large systems may need to be decrypted as a whole; one scheme is defined in the symmetric-key setting for technical reasons.
  • QHE definitions: The definitions allow classical public and secret keys while permitting the evaluation key to be a quantum state.This choice is made based on the requirements of the proposed schemes.
  • QHE definitions: QHE consists of key generation, encryption, homomorphic evaluation, and decryption algorithms for encrypted quantum information.Key generation outputs classical public and secret keys plus a quantum evaluation key; evaluation transforms encrypted inputs according to a circuit.
  • QHE definitions: The evaluation algorithm maps n encrypted quantum inputs to m encrypted outputs while consuming the evaluation key.For a circuit C inducing channel Φ_C, Eval_C maps an n-fold cipherstate to an m-fold cipherstate.
  • Security definitions: The framework defines quantum CPA indistinguishability for public-key and symmetric-key systems, including adversaries that process quantum messages and environments.The public-key experiment gives the adversary the public and evaluation keys, encrypts one of two chosen quantum messages, and asks the adversary to guess the selected bit.
  • Security definitions: Single-message q-IND-CPA security is equivalent to q-IND-CPA-mult security for quantum homomorphic schemes.The multiple-message experiment encrypts one of two chosen polynomial-size tuples of messages, and the equivalence theorem shows that the simpler definition suffices.

4 Main Contributions

The paper presents quantum homomorphic encryption schemes for Clifford circuits and for universal circuits with constrained T-gate complexity, assuming q-IND-CPA-secure classical FHE.

  • The Clifford scheme is q-IND-CPA secure, compact, and homomorphic for Clifford circuits under a classical q-IND-CPA-secure FHE assumption.
  • The entanglement-based EPR scheme supports universal quantum circuits and has decryption complexity scaling quadratically with the number of T-gates.Its compactness is nontrivial when the squared T-gate count is much smaller than the total gate count.
  • The auxiliary-qubit AUX scheme is compact and homomorphic for circuits whose T-depth is at most a fixed constant L.
  • AUX has complexity polynomial in a degree exponential in L, so its construction requires L to remain constant.
  • EPR and AUX are complementary: EPR loses compactness as T-gate count increases, whereas AUX becomes inefficient as T-depth increases.

5 Scheme CL: Homomorphic Encryption for Clifford Circuits

CL combines quantum one-time-pad encryption with classical fully homomorphic encryption to evaluate Clifford circuits while updating encrypted correction keys without circuit-dependent decryption.

  • CL applies Clifford gates to quantum-one-time-pad-encrypted data while homomorphically evaluating the corresponding key-update functions on encrypted Pauli keys.Clifford conjugation maps Pauli operators to Pauli operators, enabling correction-key updates during evaluation.
  • The scheme tracks linear key-polynomials over F2 and composes gate-specific update rules as the circuit is evaluated.The initial polynomials are fa,i = ai and fb,i = bi; affected wires are updated after each gate.
  • CL encrypts qubits individually using quantum states combined with classical ciphertext strings generated by the underlying classical FHE scheme.
  • Theorem 5.1 establishes that CL is homomorphic for Clifford circuits.
  • Theorem 5.2 establishes compactness: decrypting an output qubit requires decrypting two classical keys and applying the corresponding Pauli corrections.The stated complexity is at most 2p(κ) + 2 when the underlying HE decryption complexity is bounded by p(κ).
  • Theorem 5.3 establishes q-IND-CPA security for CL assuming q-IND-CPA security of the classical FHE scheme.The security argument bounds the contribution of the classical ciphertexts and uses the quantum one-time pad to make the remaining experiment independent of the challenge bit.

6 Scheme EPR: T-gate Computation Using Entanglement

EPR evaluates arbitrary quantum circuits by handling Clifford gates directly and using an entanglement-based T-gate gadget that postpones measurement-dependent corrections to decryption. It is q-IND-CPA secure and all-circuit homomorphic, while decryption complexity grows quadratically with the number of T-gates.

  • T-gate evaluation: The T-gate gadget uses an auxiliary Bell state to delay conditional P corrections until decryption, when the auxiliary measurement results become available.Each T-gate introduces an unknown variable k_t representing a deferred measurement result.
  • Evaluation procedure: Evaluation applies X, Z, P, H, and CNOT gates directly, while T-gates use the entanglement-based gadget and update symbolic key-polynomials.The evaluator processes circuit gates in topological order and homomorphically evaluates the portions depending only on the initial encryption-key variables.
  • Decryption: Decryption measures auxiliary registers sequentially, computes the required correction polynomials, and applies the resulting quantum decryption maps to the output registers.The measurement results k_t are obtained in order, because later correction polynomials may depend on earlier results.
  • Security and homomorphism: EPR is q-IND-CPA secure assuming the underlying classical homomorphic encryption is q-IND-CPA secure.The security statement is given by Theorem 6.1.
  • Security and homomorphism: EPR is homomorphic for all quantum circuits, but its decryption complexity is O(R^2 + Rp(κ) + mp(κ) + mR), where R is the number of T-gates.Accordingly, EPR is R^2-quasi-compact rather than compact, and outperforms the trivial scheme when T-gates are fewer than the square root of total gates.

7 Scheme AUX: T-gate Computation Using Auxiliary States

AUX handles T-gate corrections by supplying auxiliary states encoding possible key-polynomial terms, preserving compactness for circuits with bounded T-depth. Its auxiliary-state requirements grow rapidly with T-depth, while security follows from the underlying classical homomorphic encryption.

  • Auxiliary-state approach: AUX proactively handles T-gate P corrections using auxiliary states that encode parts of the original quantum one-time-pad key.These states are supplied in the evaluation key and support correction during homomorphic evaluation.
  • Auxiliary-state approach: Auxiliary-state addition introduces cross terms, increasing key-polynomial degree and requiring states for every possible term.The construction combines states for sums of terms, but cannot directly construct states for products of terms.
  • Key-polynomial tracking: For each T-depth layer and wire, AUX supplies an auxiliary state for every term that may occur in the incoming key-polynomial.The sets Tℓ capture these possible monomial terms, whose evaluations determine the auxiliary-state labels.
  • Correctness: Clifford gates preserve the relevant term sets because they act additively on the keys, so key-polynomials before the next T-layer remain sums of Tℓ terms.This establishes the inductive structure used in the correctness proof.
  • Efficiency: O(n^(2L−1+1)) auxiliary qubits are required, making the evaluation key the scheme’s bottleneck.Here n bounds encrypted qubits and L denotes the number of T-gate layers.
  • Security and scope: AUX is S-homomorphic and compact for n-wire circuits with T-depth at most L, and q-IND-CPA secure when the underlying HE is q-IND-CPA secure.Correctness relies on encrypted copies of key variables and auxiliary states covering all possible terms at each T-layer.

8 Conclusions and Open Problems

The paper presents three quantum homomorphic encryption schemes with different circuit scopes and efficiency trade-offs. It advances quantum homomorphic encryption but leaves compact, universal quantum fully homomorphic encryption open.

  • Contributions: CL is homomorphic and compact for stabilizer circuits, providing a basis for the EPR and AUX schemes.The paper uses CL as a stepping stone to the two schemes for broader circuit classes.
  • Contributions: EPR supports all quantum circuits, but its compactness degrades as the number of T-gates increases.Its decryption complexity scales with the square of the number of T-gates.
  • Contributions: AUX is compact but its evaluation-key and evaluation complexity scale doubly exponentially with T-depth, restricting its efficient scope to constant T-depth.This makes EPR and AUX incomparable across circuit families.
  • Open problems: A compact quantum fully homomorphic encryption scheme for all quantum circuits remains an open problem.EPR and AUX approach this goal from different directions without providing a full solution.

A Classical Fully Homomorphic Encryption

Classical homomorphic encryption evaluates restricted or arbitrary circuits on encrypted inputs, with compactness requiring decryption complexity independent of the evaluated circuit.

  • Scheme syntax: A homomorphic encryption scheme consists of key-generation, encryption, decryption, and evaluation algorithms.Key generation produces public encryption, public evaluation, and secret decryption keys.
  • Scheme syntax: Encryption maps a bit under the public key to a ciphertext, while decryption maps a ciphertext under the secret key to a plaintext bit.Evaluation applies a classical circuit to ciphertexts using the evaluation key.
  • Homomorphism: A scheme is S-homomorphic when it can evaluate every circuit in a specified class S on encrypted inputs.The evaluated ciphertext decrypts to the circuit output on the underlying plaintext.
  • Compactness: Compactness requires decryption complexity bounded by a security-parameter polynomial regardless of the evaluated circuit.This separates homomorphic evaluation capability from the cost of decrypting its output.
  • Full homomorphism: Fully homomorphic encryption is both compact and homomorphic for all arithmetic circuits over F2.The definition combines unrestricted circuit homomorphism with circuit-independent decryption complexity.

B Equivalence of Definitions for q-IND-CPA

This section introduces quantum IND-CPA-2 as an intermediate security definition and proves its equivalence to both q-IND-CPA and q-IND-CPA-mult. The proofs construct adversaries that reduce between these experiments.

  • Equivalence results: q-IND-CPA and q-IND-CPA-mult are equivalent for quantum homomorphic encryption schemes.The proof first reduces the multi-message experiment to q-IND-CPA-2 and then uses a hybrid sequence across the t message pairs.
  • q-IND-CPA-2 definition: q-IND-CPA-2 security requires every quantum polynomial-time adversary to have only negligible distinguishing advantage.The experiment gives an adversary an encrypted challenge derived from two message systems and asks it to predict the hidden bit.
  • Equivalence results: q-IND-CPA and q-IND-CPA-2 are equivalent for quantum homomorphic encryption schemes.One direction is immediate; the other traces out one message system to construct an adversary for the single-message experiment.
  • Hybrid proof: The hybrid reduction selects a random message position and replaces encryptions one position at a time.For adjacent hybrids, the constructed adversary applies the q-IND-CPA-2 challenge to the selected pair and encrypts the remaining systems directly.
  • Hybrid proof: Because t is polynomially bounded, multiplying a negligible advantage by t remains negligible.This completes the reduction from q-IND-CPA to q-IND-CPA-mult.

C Key Update Rules for Stabilizer Elements

The section gives key-update rules for stabilizer and Clifford operations on quantum data encrypted with a quantum one-time pad. Pauli gates can be handled by key updates, while other gates require physical operations.

  • Key representation: Quantum one-time-pad encryption represents each wire using X- and Z-key polynomials.The key-update rules track how stabilizer and Clifford gates transform these encrypted Pauli corrections.
  • Measurement: Measurement returns a classical bit that is decrypted using the X-key, while the Z-key becomes irrelevant.The measurement protocol performs the measurement directly and applies Xfa,i to recover the bit.
  • Pauli gates: X and Z gates can be implemented either directly on the encrypted state or, alternatively, by updating the corresponding key.The alternative updates are fa,i → fa,i ⊕ 1 for X and the analogous update for Z.
  • Clifford gates: H, P, and CNOT gates are applied to the encrypted state while their key polynomials are updated.The H gate swaps key polynomials; P updates fb,i; CNOT updates fb,i and fa,j.
  • Implementation boundary: Except for Pauli gates, Clifford operations require actual quantum operations on the encrypted data rather than key updates alone.This distinction reflects that the scheme performs quantum computation on encrypted states instead of merely simulating it.

D Correctness of the T-gate Gadget

The T-gate protocol is derived from X-teleportation and circuit identities, using auxiliary-wire operations and classical control to account for encrypted Pauli corrections.

  • Teleportation construction: The correctness proof builds the T-gate gadget from an X-teleportation circuit identity.The construction swaps a qubit with |+⟩, measures one qubit, and classically controls the correction.
  • Circuit identities: The derivation uses commutation and conjugation identities for X, Z, P, and T gates, up to global phase.These identities allow the correction terms to be rearranged and simplified through the gadget.
  • T-gate construction: For encrypted input TXaZb|ψ⟩, the gadget adds Pa and Zk operations on an auxiliary wire before simplifying the output.The added gates and controlled operations are chosen to manipulate the Pauli corrections associated with the input.

E Proof of Lemma 7.6

This section proves Lemma 7.6 by defining the total quantity N from the T-gate layers and establishing the corresponding identities for binary strings and circuit components.

  • Lemma statement: The lemma defines N as n|T1| + ··· + n|TL|.This quantity aggregates contributions from the T-gate layers T1 through TL.
  • Proof setup: The proof first establishes an identity for every binary string s of length |s|.This identity is then used as the building block for the general statement.
  • Proof setup: The string-level identity is extended to arbitrary binary strings a and b of length n.The proof then applies the resulting relation across the indexed circuit terms.
Loading 1412.8766v2…