PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum homomorphic encryption for polynomial-sized circuits

Yfke Dulek, Christian Schaffner, Florian Speelman

arXiv:1603.09717v2quant-phcs.CR

TL;DR

Quantum homomorphic encryption faces the challenge of evaluating polynomial-sized circuits on encrypted quantum data, particularly across T gates. TP uses quantum gadgets based on instantaneous non-local computation techniques to correct T-gate errors. The paper concludes that TP is compact and supports arbitrary polynomial-sized circuits, with security inherited from the classical FHE scheme's assumptions.

  • Problem

    The paper asks whether quantum homomorphic encryption can evaluate polynomial-sized circuits, while T gates remain a challenge for evaluation on encrypted data.

    Source: §1 · p. 2

  • Method

    TP uses quantum gadgets grounded in instantaneous non-local computation techniques to enable homomorphic evaluation of T gates on encrypted quantum data.

    Source: §5.1 · p. 24, §6 · p. 27

  • Results

    Assuming polynomially many evaluation wires, TP is compact, evaluates arbitrary polynomial-sized circuits with polynomially many T gates, and is q-IND-CPA secure when its classical HE is q-IND-CPA secure.

    Source: §4 · p. 17, §6 · p. 27

  • Takeaways & Limitations

    Log-depth classical decryption yields TP gadgets of polynomial size in the security parameter.

    Source: §5.1 · p. 23

    The paper focuses on TP's construction and security proof; more concrete applications, including the proposed multiparty direction, are left for future work.

    Source: §1.1 · p. 4

Abstract

from arXiv · show

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 and recent results in the area of instantaneous non-local quantum computation, 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", circuit privacy for the evaluator against passive adversaries, and a three-round scheme for blind delegated quantum computation which puts only very limited demands on the quantum abilities of the client.

1 Introduction

The introduction frames homomorphic evaluation of arbitrary polynomial-sized quantum circuits as an open problem, especially because non-Clifford T gates obstruct evaluation on encrypted data. It presents TP, a compact scheme using quantum gadgets to correct T-gate errors, and outlines its security, resource, and application properties.

1 Introduction

  • The paper asks whether quantum homomorphic encryption can evaluate polynomial-sized quantum circuits, a challenge rooted in T gates that disrupt one-time-pad encryption.Prior schemes described here handle arbitrary Clifford operations, while the T-gate approaches of Broadbent and Jeffery support only a limited number of T gates.Source: §1 · p. 2

1.1 Our Contributions

  • TP is compact and efficient for circuits with polynomially many T gates, and is q-IND-CPA secure against quantum adversaries.The security notion is the one defined by Broadbent and Jeffery [BJ15].Source: §1.1 · p. 3
  • TP extends the Clifford scheme CL with evaluation-key gadgets for T gates, whose size depends on the classical FHE decryption function's space complexity.For the Brakerski–Vaikuntanathan scheme [BV11], each gadget has polynomially many qubits in the security parameter; teleportation through the gadget removes the unwanted phase caused by a T gate.Source: §1.1 · p. 3
  • A T gate uses one gadget without accumulating quantum-state errors, and gadgets can be supplied on demand while the evaluated state retains its initial form.The secret-key holder can provide more gadgets when the evaluator runs out.Source: §1.1 · pp. 3–4
  • TP needs only space-efficient decryption and quantum-secure leveled FHE, requires no circular-security assumption, and supports passive circuit privacy when the classical scheme is circuit-private.For circuit privacy, the evaluator adds a random one-time-pad layer to the output.Source: §1.1 · p. 4
  • TP also yields a constant-round blind delegated-computation scheme with restricted client quantum memory or operations; concrete multiparty applications remain future work.The proposed multiparty direction uses distributed-key FHE, but the paper focuses on TP's construction and security proof.Source: §1.1 · p. 4

1.2 Related Work

  • Information-theoretic QFHE faces exponential-size or restricted-evaluation trade-offs, while AUX is limited to constant T-depth and TP's key grows linearly with T gates.The related-work discussion attributes AUX's limitation to doubly exponential growth of its auxiliary states with T depth.Source: §1.2 · pp. 5–6

1.3 Structure of this paper

  • The paper covers preliminaries, TP and its compactness, security and circuit privacy, gadget rationale, and then conclusions and future directions.Source: §1.3 · p. 6

2 Preliminaries

The preliminaries establish the quantum and homomorphic-encryption conventions used to describe TP, define its security target, and introduce garden-hose complexity as a tool for gadget construction.

2.1 Quantum computation

  • Clifford gates preserve Pauli encryption, but the non-Clifford T gate introduces a key-dependent phase that obstructs homomorphic evaluation.The T gate is used as the non-Clifford gate that, together with Clifford gates, suffices to simulate arbitrary quantum circuits efficiently.Source: §2.1 · pp. 6–7

2.2 Homomorphic encryption

  • Homomorphic encryption lets an evaluator apply a circuit to ciphertexts so that decryption yields the circuit's output on the original inputs.Classical schemes use public, secret, and evaluation keys and algorithms for key generation, encryption, evaluation, and decryption.Source: The classical setting · p. 8

The classical setting

  • Classical compactness bounds decryption complexity independently of the evaluated circuit, while leveled FHE supports circuits up to a key-generation-specified depth.With multiple key sets, recryption homomorphically evaluates decryption to move an encrypted message from one key to another.Source: The classical setting · pp. 8–9

The quantum setting

  • Quantum homomorphic encryption uses classical public and secret keys but may use a consumable quantum evaluation key, and this work requires subsystem-by-subsystem decryption.Its messages are qubits and its evaluator applies quantum circuits to them.Source: The quantum setting · pp. 9–10

Quantum security

  • q-IND-CPA security tests whether a quantum adversary can distinguish an encryption of its chosen state from an encryption of the zero state with more than negligible advantage.The adversary may retain a quantum working register across the challenge.Source: Quantum security · pp. 10–11, Figure 1 · p. 10

2.3 Garden-hose complexity

  • Garden-hose protocols compute a two-party function by routing water through input-dependent pipes; in TP, their teleportation correspondence ties gadget size to decryption complexity.Pipes correspond to EPR pairs and hoses to Bell measurements; log-space-computable decryption permits efficiently constructable polynomial-size gadgets.Source: §2.3 · p. 11

3 The TP scheme

TP extends the Clifford-based scheme CL with quantum gadgets that correct the possible phase error after a T gate. It evaluates circuits gate by gate, carrying encrypted one-time-pad keys through successive classical key sets, and is compact when its classical FHE scheme is compact.

3 The TP scheme

  • TP extends CL: it encrypts qubits with a quantum one-time pad and evaluates Clifford gates by updating the encrypted pad keys.For each T gate, the evaluation key includes a gadget that corrects any P error; one gadget is provided per supported T gate.Source: §3 · pp. 11–12

3.1 Gadget

  • Because the evaluator knows only an encryption of the pad key, it cannot tell whether a T gate introduced a P error and should be corrected.The key generator instead creates a gadget that corrects the state conditioned on the key, without revealing whether the P error was present; its size depends on the decryption function’s space complexity.Source: §3.1 · p. 12

Specification of gadget.

  • The gadget’s classical information is encrypted under a fresh, independent public key, avoiding a circular-security requirement.The specification also states that the gadget property is important to the security proof and intuitively prevents leakage of the secret key when x and z are encrypted securely.Source: Specification of gadget · pp. 13–14

Usage of gadget.

  • The evaluator uses encrypted key information to choose Bell measurements on the gadget and input qubit, leaving an output qubit with updated Pauli corrections.The measurement path passes through an inverse phase gate when the encrypted key decrypts to 1, and avoids those gates when it decrypts to 0.Source: Usage of gadget · p. 14

3.2 Key generation

  • Key generation creates L+1 independent classical keysets and an evaluation key with L gadgets, supporting circuits with up to L T gates.Each gadget depends on a different secret key, and its classical information is encrypted with the next public key.Source: §3.2 · pp. 14–15

3.3 Encryption

  • TP encrypts each qubit separately with a quantum one-time pad and appends a classical encryption of its pad key.The encryption procedure uses the first public key.Source: §3.3 · p. 15

3.4 Circuit evaluation

  • For a T gate, the evaluator applies T, consumes a gadget to remove the possible P error, and transfers the encrypted pad keys to the next keyset.After a circuit with k T gates, the evaluator holds the encrypted output state and pad keys under the kth key, then recrypts the keys into the final key before sending them with the state.Source: §3.4 · pp. 15–16

3.5 Decryption

  • If the classical HE scheme is compact, TP is compact: decryption complexity is polynomial in the security parameter and independent of the evaluated circuit.Decryption recovers the pad keys and removes the one-time pad from the output state.Source: §3.5 · p. 17

4 Security of TP

The section proves that TP is q-IND-CPA secure for polynomially many T gates when its classical FHE scheme is q-IND-CPA secure. It also shows that circuit privacy follows, in the semi-honest setting, if the classical scheme has circuit privacy.

4 Security of TP

  • If HE is q-IND-CPA secure, TP is q-IND-CPA secure for circuits with polynomially many T gates.The proof compares TP with successively fewer usable gadgets, then reduces the base case TP(0) to the CL scheme.Source: §4 · pp. 17, 18, 21
  • Replacing real gadget information with encryptions of zero changes an efficient adversary’s distinguishing advantage only negligibly, and iterating this hybrid over polynomially many gadgets preserves that bound.Each hybrid step is based on the q-IND-CPA security of HE.Source: §4 · pp. 17, 18, 20, 21

4.1 Circuit privacy

  • If HE has circuit privacy, a slight TP modification provides circuit privacy against passive adversaries.The evaluator re-randomizes the output with a quantum one-time pad and updates its classical encrypted keys.Source: §4.1 · p. 22

5 Constructing the gadgets

The section constructs polynomial-size gadgets from decryption functions of limited complexity, then gives an LWE example and delegated-computation variants with restricted client resources.

5.1 For log-depth decryption circuits

  • A fan-in-2 decryption circuit of depth O(log κ) yields polynomial-size gadgets by encoding its computation as a width-5 permutation branching program.Bell-measurement and EPR-pair connections implement the program; running its inverse returns the teleported qubit to a known output location.Source: §5.1 · pp. 22–24

5.2 For log-space computable decryption functions

  • If HE.Dec is computable in space O(log κ), TP has polynomial-size gadgets.The garden-hose model links log-space computation to gadget construction and can guide more efficient constructions for specific functions.Source: §5.2 · p. 26

5.3 Specific case: Learning With Errors

  • The decryption function of the Brakerski–Vaikuntanathan scheme yields polynomial-size gadgets for quantum homomorphic encryption.The paper presents this scheme as an example based on Learning With Errors.Source: §5.3 · p. 26

5.4 Constructing gadgets using limited quantum resources

  • TP supports three-round delegated quantum computation when the client is limited to Pauli and swap operations.With EPR pairs supplied by the server or another untrusted source, the client can generate the evaluation key using only those operations.Source: §5.4 · p. 27
  • If HE.Dec is in NC1, TP also gives a two-round delegated protocol for a client with arbitrary Clifford operations and constant-sized quantum memory.The client can construct gadgets in ten-qubit parts, or reduce memory to four qubits by decomposing 5-cycles into 2-cycles.Source: §5.4 · p. 27

6 Conclusion

The conclusion presents TP as a compact scheme for arbitrary polynomial-sized quantum circuits, built from classical FHE and gadgets inspired by instantaneous non-local quantum computation. It identifies open questions about non-leveled schemes, evaluation-key lower bounds, stronger circuit privacy, and other uses of QFHE.

6 Conclusion

  • TP is compact and evaluates arbitrary polynomial-sized circuits, assuming the evaluation circuit’s wire count is polynomially related to the security parameter.Its security requires only the computational assumptions of the classical FHE scheme used as a black box.Source: §6 · p. 27
  • The construction connects instantaneous non-local quantum computation and quantum homomorphic encryption through garden-hose-based gadgets for homomorphic T-gate evaluation.The paper identifies techniques based on the garden-hose model as crucial to its construction.Source: §6 · p. 27

6.1 Future work

  • Future work includes non-leveled QFHE, lower bounds on compact schemes’ evaluation-key size, and circuit privacy against active adversaries.The paper also raises other cryptographic tasks, including quantum indistinguishability obfuscation, as possible applications.Source: §6.1 · p. 28

A.1 Applying Clifford group gates

This appendix gives the quantum one-time-pad key updates for applying Hadamard and CNOT gates to encrypted states.

A.1 Applying Clifford group gates

  • These update rules apply to states encrypted with the quantum one-time pad.Source: §A.1 · p. 32
  • Applying H on wire i swaps its one-time-pad keys, (a_i, b_i) → (b_i, a_i).Source: §A.1 · p. 32
  • For CNOT with control i and target j, the updated keys are (a_i, b_i ⊕ b_j; a_i ⊕ a_j, b_j).Source: §A.1 · p. 32

A.2 Using the gadget

The evaluator tracks the qubit’s location, Pauli keys, and possible phase while homomorphically processing the gadget’s encrypted structure and measurement outcomes. Repeating this bookkeeping across the gadget yields the updated one-time-pad keys.

A.2 Using the gadget

  • The evaluator starts with encrypted pad keys, gadget-structure data, and Bell-measurement pairs and outcomes, then performs the key-update calculation using encrypted information.The classical homomorphic scheme handles the calculation because the relevant information can be encrypted under the same public key.Source: §A.2 · p. 32
  • At each step, the evaluator follows the qubit’s path through a measurement pair, updates its keys from the Bell outcomes, and applies the pair’s encoded teleportation corrections.The tracked state includes its current location, X and Z corrections, and whether it has an extra phase gate.Source: §A.2 · p. 33
  • The evaluator homomorphically computes updated one-time-pad keys by repeating location, correction, and phase bookkeeping across the gadget’s 2m steps.Temporary variables can then be discarded; only the updated keys are needed to continue the protocol.Source: §A.2 · pp. 32–33

B Circuit privacy

The paper shows that TP can provide circuit privacy in the semi-honest setting when its classical FHE scheme has circuit privacy. The evaluator randomizes the output with a quantum one-time pad, and the proof uses classical simulation to show the evaluated and simulated states are negligibly close.

B Circuit privacy

  • Key switching through recryption does not degrade circuit privacy: evaluation with key switching is statistically close to simulation using only the last key set.The result is stated for polynomial L and follows from the classical circuit-privacy property.Source: B Circuit privacy · p. 34
  • If the classical scheme HE has circuit privacy in the semi-honest setting, TP can be adapted to a quantum homomorphic scheme with circuit privacy.The modification preserves compactness and correctness by having the evaluator apply a random quantum one-time pad to the output and update the encrypted keys.Source: B Circuit privacy · p. 35
  • The final random pad makes the quantum pad keys independent of the evaluated circuit, while HE circuit privacy hides their classical encryptions from the decryptor.The simulator applies a uniform quantum one-time pad and uses the classical simulator on the pad keys.Source: B Circuit privacy · p. 35
  • The simulator’s state is transformed into the evaluation state with negligible trace distance, establishing quantum circuit privacy.The proof bounds the distance by 4n·η(κ), which is negligible when η is negligible.Source: B Circuit privacy · pp. 35, 37

C Gadget construction using the garden-hose model

The gadget construction translates the classical decryption function into a garden-hose task, then uses its protocol to create the entangled resources used by the evaluator. The gadget size is governed by the garden-hose complexity of decryption, which is polynomial when decryption is log-space computable.

C Gadget construction using the garden-hose model

  • The construction models Alice as gadget creator holding sk and Bob as evaluator holding encrypted key ea and a qubit with phase P^a, where a = HE.Dec_sk(ea).Their goal is to leave Bob with the input state under updated Pauli keys, using local Bell measurements and inverse phase gates without communication.Source: C Gadget construction using the… · p. 38
  • The gadget’s quantum component is Bob’s reduced state, while Alice’s measurement choices and outcomes provide the accompanying classical information for the evaluator’s measurements.The evaluator’s Bell-measurement pairs depend on encrypted information and are generated by TP.GenMeasurement.Source: C Gadget construction using the… · p. 38
  • For log-space-computable decryption, GH(HE.Dec) is polynomial, so the garden-hose complexity gives a polynomial gadget-size bound.The paper also notes that a player can determine the strategy for a specific input in polynomial time for log-space decryption.Source: C Gadget construction using the… · pp. 38–39
  • A garden-hose protocol for decryption yields an instantaneous no-communication procedure using 2GH(HE.Dec) EPR pairs and leaves Bob’s qubit with Pauli corrections determined by local inputs and measurement outcomes.The garden-hose lemma also bounds the complexities of the resulting correction functions linearly in the complexity of the phase function.Source: C Gadget construction using the… · p. 39

C.1 Toy example

The toy example illustrates how a garden-hose protocol for decryption becomes a gadget that corrects a possible phase error without revealing its hidden connections to the evaluator. Teleportation adds Pauli corrections, which Alice supplies in encrypted form so the evaluator can update the keys.

C.1 Toy example

  • The TOY.Dec protocol uses three EPR pairs to route a qubit according to c and sk, with its output side encoding the decryption bit.The example is illustrative only; TOY is not claimed to be homomorphic.Source: §C.1 · pp. 39–40
  • Running the garden-hose protocol again in reverse after Alice applies P† returns the corrected qubit to Bob’s ‘out’ position without needing to know its intermediate location.The example caption shows the c = 0, sk = 1 path through EPR pairs 1 and 4 with P† applied between them.Source: §C.1 · pp. 40–41, Figure 6 · p. 41
  • The gadget removes the possible P error, but teleportation also introduces Pauli transformations that Alice reports in encrypted form for the evaluator’s key updates.The two gadget variants order 2GH(TOY.Dec) EPR pairs according to sk, and the evaluator cannot tell whether the input traverses a P† transformation.Source: §C.1 · pp. 41–42, Figure 7 · p. 42

D Gadget construction for Learning With Errors

For small modulus, permutation gadgets route a qubit according to the decryption computation and yield a gadget of size at most 4κp log p. For large modulus, a low-depth decryption circuit gives a polynomial-sized gadget via a garden-hose protocol.

Small modulus.

  • The small-modulus construction routes the qubit through permutation gadgets according to ciphertext bits, then applies an inverse phase gate when the resulting parity is 1.Each gadget simulates addition by q over Zp; the construction routes the unknown qubit back to a known location.Source: Small modulus · p. 43
  • The total small-modulus gadget size is bounded by 4κp log p.Source: Small modulus · p. 43

Large modulus.

  • For superpolynomially large modulus, the decryption function has depth O(log κ + log log p), so Theorem 5 converts it into a polynomial-sized garden-hose gadget.Unlike the small-modulus construction, this approach does not exploit the decryption function's structure for greater efficiency.Source: Large modulus · p. 43

E Constructing gadgets using swap and Paulis

The gadget-generation procedure can be carried out with only X, Z, and CNOT gates using supplied entangled-pair resources. Independent random Paulis protect the key generator's secret even if the supplier is malicious.

E Constructing gadgets using swap and Paulis

Loading 1603.09717v2…