PaperlayerView exact revision on arXiv

Source-linked AI summary

Classical Homomorphic Encryption for Quantum Circuits

Urmila Mahadev

arXiv:1708.02130v5quant-phcs.CR

TL;DR

The paper addresses how a classical client can delegate quantum computation while hiding the computation from a quantum server. It constructs a quantum-capable scheme from classical homomorphic encryption and shows that learning with errors supplies the needed foundation, yielding leveled fully homomorphic encryption with classical keys.

  • Problem

    Classical encryption hides data but does not directly support computing on encrypted quantum data, leaving classical-client blind delegation of quantum computations unresolved.

  • Method

    The paper lifts suitable quantum-secure classical homomorphic encryption into the quantum setting using Pauli-masked states and encrypted CNOT operations.

  • Results

    The construction yields a quantum leveled fully homomorphic encryption scheme with classical keys under quantum hardness of learning with errors with superpolynomial noise ratio.

  • Takeaways & Limitations

    The scheme enables a classical client to blindly delegate quantum computation to a quantum server while preserving the classical homomorphic encryption framework’s properties.

  • Takeaways & Limitations

    The construction assumes learning with errors hardness against quantum polynomial-time adversaries with a superpolynomial noise ratio and requires specific quantum-capable ciphertext structure.

Abstract

from arXiv · show

We present the first leveled fully homomorphic encryption scheme for quantum circuits with classical keys. The scheme allows a classical client to blindly delegate a quantum computation to a quantum server: an honest server is able to run the computation while a malicious server is unable to learn any information about the computation. We show that it is possible to construct such a scheme directly from a quantum secure classical homomorphic encryption scheme with certain properties. Finally, we show that a classical homomorphic encryption scheme with the required properties can be constructed from the learning with errors problem.

1 Introduction

The paper introduces quantum homomorphic encryption with a classical client, addressing the challenge of hiding quantum computations from a remote server. It constructs the scheme by combining Pauli masking, encrypted CNOT operations, and suitable classical homomorphic encryption.

  • Motivation: Classical homomorphic encryption handles encrypted classical computation but does not directly support computation in superposition.Different encryptions of the same bit can prevent the interference required by quantum algorithms.
  • Motivation: Blind quantum computation and earlier delegated protocols either require a quantum client, multiple interaction rounds, or do not claim blindness against malicious servers for general computations.The proposed homomorphic model uses one round and retains classical-client operation.
  • Contribution: The paper provides the first quantum homomorphic encryption scheme enabling a classical client to delegate quantum computations to a quantum server.The scheme is also presented as the first classical-client blind quantum computation protocol for general quantum computations.
  • Construction: The construction reduces blind quantum computation to an encrypted CNOT operation controlled by a classically encrypted bit.The key step is extracting the encrypted bit into a quantum superposition while keeping the output suitably encrypted.
  • Construction: Trapdoor claw-free function pairs enable a hidden bit to be stored in superposition and support the encrypted CNOT operation.Their shared-image structure and hard-to-find matching preimages provide the relevant quantum mechanism.
  • Construction: The scheme uses a Pauli one-time pad for quantum states and classically encrypts the Pauli keys to obtain computational security.A single l-qubit state uses 2l classical Pauli-key bits, while the encrypted state contains both the masked quantum state and encrypted keys.
  • Result: Under quantum hardness of learning with errors with superpolynomial noise ratio, the paper obtains a quantum leveled fully homomorphic encryption scheme with classical keys.The required classical quantum-capable scheme is constructed from learning with errors.

2 Overview

The overview builds quantum homomorphic encryption from Pauli-masked states and homomorphic updates to their keys. Clifford gates are handled in parallel, while Toffoli gates require encrypted CNOT operations because their corrections are not merely Pauli operators.

  • Pauli encryption: Pauli one-time padding encrypts an l-qubit state with random keys z and x retained by the client.The client later applies (ZzXx)† to decode the server’s output.
  • Pauli encryption: For standard-basis states, Pauli encryption and decoding reduce to classical one-time-pad operations.The encoded state uses bitwise XOR with the Pauli key x.
  • Security: The server’s blindness follows from the Pauli-masked state being information-theoretically hidden without knowledge of the client’s keys.The resulting state is equivalent to a maximally mixed state from the server’s perspective.
  • Computational security: Computational security is obtained by including classical homomorphic encryptions of the Pauli keys alongside the masked quantum state.The server evaluates on the state while updating encrypted keys homomorphically.
  • Clifford gates: Clifford gates are applied through parallel quantum execution and homomorphic Pauli-key updates.Conjugation preserves the Pauli group, allowing the server to update the keys from Enc(z,x) to Enc(z′,x′).
  • Toffoli gate: Toffoli gates cannot use the same parallel procedure because they do not preserve Pauli operators under conjugation.Their correction includes Clifford components such as Hadamard and key-controlled CNOT gates, which cannot be removed by a simple Pauli-key update.
  • Toffoli gate: The Toffoli correction is completed by removing a CNOT controlled by a bit derived from the encrypted Pauli keys.This reduces the remaining task to applying CNOTs controlled by a classically encrypted bit.

2.2 Encrypted CNOT Operation

The encrypted CNOT operation converts a classical encryption of a control bit into a quantum superposition, enabling the server to apply CNOTs homomorphically. The construction uses trapdoor claw-free functions and extends to suitable classical homomorphic encryption schemes, with weaker statistical conditions handling unequal function images.

  • Encrypted CNOT mechanism: The key step is extracting an encrypted bit from a classical ciphertext and storing it in a quantum superposition.A trapdoor claw-free function pair hides the bit through the XOR of the two preimage bits.
  • Encrypted CNOT mechanism: The server entangles the superposition over a random claw with the first qubit, then XORs a preimage bit into the second register to implement the CNOT.The relation µ0 ⊕µ1 = s supplies the required control value a·s.
  • Classical encryption construction: For a classical homomorphic encryption scheme, f0 is the encryption function and f1 is f0 shifted by the homomorphic XOR of the ciphertext encrypting s.Randomness recoverability makes the functions injective, while efficient public-key inversion of homomorphic XOR is also required.
  • Classical encryption construction: Because the constructed functions may have unequal images, the scheme replaces equal-image behavior with a distribution whose two images are statistically close.Measuring the final register then yields matching preimages with high probability, recovering the superposition needed for the operation.
  • Remaining requirement: The requirements must continue to hold for ciphertexts arising during computation, but many classical schemes change ciphertext format as evaluation proceeds.The paper addresses this issue by weakening the requirements while preserving encrypted CNOT functionality.

2.3 Quantum-Capable Classical Homomorphic Encryption Schemes

Quantum-capable homomorphic encryption schemes adapt classical leveled fully homomorphic encryption to quantum-circuit evaluation. They use an alternative encryption representation to combine stable ciphertext structure with an efficiently invertible, natural homomorphic XOR.

  • Definition: A quantum-capable scheme is a classical leveled fully homomorphic encryption scheme that can evaluate quantum circuits.The definition is motivated by preserving ciphertext structure while noise grows during computation.
  • Required properties: The construction requires ciphertext-form invariance and a natural XOR operation whose output noise is the sum of the input noise terms.Under these conditions, a distribution over ciphertexts can remain approximately unchanged after shifting by a ciphertext.
  • Alternative representation: Because no known classical scheme satisfies both properties directly, the paper introduces an alternative encryption scheme AltHE.HE ciphertexts are converted to AltHE while preserving their decrypted values; AltHE provides natural, efficiently invertible XOR and supports the required superpositions.
  • Alternative representation: During encrypted CNOT, the server converts an HE ciphertext to AltHE, performs the quantum operation there, and re-encrypts the results under HE for homomorphic processing.Encrypted AltHE secret-key and trapdoor information enables recovery of randomness and decrypted values through HE.

2.4 Example of a Quantum-Capable Classical Encryption Scheme

The paper instantiates its framework by modifying the GSW-based scheme into DualHE, using Dual as the alternative encryption scheme. It proves quantum capability under learning with errors and describes the circular-security and leveled structure required for evaluation.

  • DualHE construction: The paper modifies the GSW-based leveled fully homomorphic encryption scheme by replacing its underlying scheme with the randomness-recoverable Dual construction.The resulting scheme is called DualHE, while the underlying GPV-based scheme is called Dual.
  • DualHE construction: Dual serves as AltHE because DualHE ciphertexts can be converted to Dual, whose natural XOR operation is preserved after leaving the matrix representation.Matrix extension compromises XOR by performing addition over a larger field.
  • Security and capability: The paper proves that DualHE is a classical leveled fully homomorphic encryption scheme and quantum-capable after a small parameter modification.Both constructions rely on the hardness of learning with errors with a superpolynomial noise ratio.
  • Security and capability: The quantum homomorphic scheme requires circular security because the server receives encrypted secret-key and trapdoor information to update encrypted Pauli keys.The paper's circular-security notion is stronger than standard circular security because it also encrypts trapdoor information.
  • Leveled evaluation: In the leveled computation, each quantum level combines Clifford gates, nonintersecting Toffoli gates, and a layer of nonintersecting encrypted CNOT operations.Classical homomorphic processing recovers randomness and updates Pauli keys between successive levels.
  • Leveled evaluation: Security is argued from the final level backward by replacing encryptions under the next public key with encryptions of 0 when no corresponding trapdoor or secret-key information is provided.The argument uses semantic security under independent public keys.

3 Preliminaries

The paper states that it borrows notation and definitions from earlier works, with parts of later sections also drawn from those sources.

  • Preliminaries: The paper reuses notation and definitions from, [ABOEM17], and.It also states that parts of the following sections are taken from these sources.

3.1 Notation

This section establishes notation for modular arithmetic, vectors, matrices, distributions, distances, and computational indistinguishability used throughout the paper.

  • Modular and norm notation: Elements of Z_q are represented by canonical integers modulo q, with norms applied entrywise to vectors and matrices.The notation also permits binary vectors to be viewed as elements of Z_q^n.
  • Asymptotic terminology: A function is polynomially bounded, negligible, or super-polynomial according to its asymptotic growth or decay relative to polynomials.
  • Distributions and densities: Distributions are represented by densities over finite domains, with U denoting uniform sampling and SUPP(f) denoting a density's support.
  • Distribution distances: The section defines Hellinger distance and total variation distance for comparing densities over a common finite domain.
  • Indistinguishability: Computational indistinguishability requires every quantum polynomial-time attacker to have only negligible distinguishing advantage between distribution families.

3.2 Learning with Errors and Discrete Gaussians

This section introduces the discrete Gaussian and LWE foundations used by the construction, including trapdoor sampling and quantum-hardness assumptions.

  • Discrete Gaussians: The truncated discrete Gaussian over Z_q is supported on elements with bounded norm, while truncation changes the corresponding non-truncated distribution by exponentially small statistical distance.
  • Gaussian shifts: Shifted truncated Gaussian distributions remain close to the original distribution under the stated bounded-error conditions.
  • Learning with Errors: LWE distinguishes noisy linear samples (A, As + e) from uniformly random samples under a quantum polynomial-time hardness assumption.The secret and error vectors are sampled from specified distributions, and the number of samples may be polynomially bounded.
  • Hardness assumption: For suitable Gaussian width σ = αq, LWE-related hardness is connected through a quantum reduction to approximating SIVP within γ = eO(n/α) in dimension n.The construction assumes hardness against quantum polynomial-time adversaries when γ is super-polynomial in n.
  • Trapdoors: A trapdoor generator produces an almost-uniform matrix A and trapdoor t_A that enables recovery of s and e from As + e when the error norm is sufficiently bounded.The required condition is ∥e∥ ≤ q/(C_T√(n log q)), with overwhelming recovery probability.

3.3 Quantum Computation Preliminaries

This section supplies the quantum-circuit tools used later: Pauli and Clifford operators, universal gates, operator decompositions, and trace-distance relations.

  • Pauli operators: Pauli operators form a basis for matrices on qubits, and operators on composite spaces can be decomposed into Pauli components acting on one subsystem.
  • Clifford and universal gates: Clifford operations map Pauli operators to Pauli operators up to phase, while Clifford gates together with Toffoli form a universal gate set.
  • Gate definitions: The controlled-NOT and controlled-phase gates are defined explicitly, including the controlled-phase decomposition using CNOT and Hadamard gates.
  • Toffoli decomposition: Conjugating Pauli operators by Toffoli yields Clifford operators that can be split into a Clifford component and a Pauli component.
  • Key dependence: The resulting Clifford component uses CNOT and Hadamard gates, with only the CNOT gates depending on the Pauli keys.
  • Distance measures: The section develops trace-distance tools for density matrices and relates Hellinger distance between distributions to trace distance between their superpositions.
  • Quantum indistinguishability: Quantum computational indistinguishability is defined through the negligible distinguishing advantage of efficiently computable completely positive trace-preserving maps.

3.4 Homomorphic Encryption

This section defines classical homomorphic encryption, its security and correctness requirements, and the compactness conditions distinguishing leveled from fully homomorphic schemes.

  • Scheme algorithms: A homomorphic encryption scheme consists of key generation, encryption, decryption, and homomorphic evaluation algorithms for encrypted classical bits.
  • Correctness: Evaluation applies an encrypted function to ciphertexts and produces a ciphertext that decrypts to the function's output except with negligible probability.
  • Security: IND-CPA security requires that an efficient adversary cannot distinguish encryptions of 0 and 1 with more than negligible advantage.
  • Quantum extension: Although the formal definitions use classical inputs and outputs, the paper states that they extend to quantum encryption and quantum input/output, and that its scheme satisfies those extended definitions.
  • Compactness and homomorphism: Compactness bounds the evaluation output length by a polynomial independent of the function or number of inputs.
  • Compactness and homomorphism: A compact scheme is fully homomorphic when it evaluates every efficiently computable Boolean function, and leveled fully homomorphic when it evaluates circuits only up to a supplied depth L.

4 Quantum-Capable Classical Homomorphic Encryption Schemes

The section defines quantum-capable classical homomorphic encryption schemes through an alternative encryption scheme supporting conversion, homomorphic XOR, and related recoverability properties. These properties enable an encrypted CNOT operation whose output remains suitably encrypted and is correct up to negligible trace distance.

  • Definition: Quantum capability requires an alternative encryption scheme AltHE for every ciphertext that can occur during a leveled computation.The classical scheme must support conversion to AltHE while preserving the encrypted value.
  • Definition: AltHE must support homomorphic XOR whose result can be efficiently inverted using only its public key.Given a ciphertext and the XOR result, the other input ciphertext must be recoverable.
  • Encrypted CNOT: A BQP server can use a quantum-capable ciphertext and a two-qubit state to produce an AltHE ciphertext, auxiliary string, and state negligibly close to the ideal encrypted-CNOT state.The construction first converts the ciphertext and then applies the encrypted CNOT procedure.

5 Example of a Quantum-Capable Classical Encryption Scheme

The paper instantiates quantum-capable classical encryption using Dual and its leveled homomorphic extension DualHE. DualHE preserves a structured ciphertext form through evaluation, supports conversion to Dual, and is shown to be secure, leveled fully homomorphic, and quantum-capable under LWE-based assumptions.

  • Construction: Dual ciphertexts are naturally additively homomorphic: adding encryptions of µ0 and µ1 produces an encryption of µ0 ⊕ µ1.This property supplies the homomorphic XOR behavior needed by the quantum-capability framework.
  • Construction: DualHE extends the Dual encryption scheme into a leveled fully homomorphic scheme by mapping ciphertexts to matrices and encrypting bits in matrix form.Its evaluation procedure applies NAND using G and G^-1, while conversion outputs the final column as a Dual ciphertext.
  • Ciphertext structure: Throughout depth-L Boolean evaluation, DualHE ciphertexts retain the form A′S + E + µG with ||E||∞ ≤ βinit(N + 1)^L.The NAND operation preserves this structure while increasing the error bound by at most a factor of N + 1 per level.
  • Security and homomorphism: DualHE is IND-CPA secure and leveled fully homomorphic under the hardness of LWE with a superpolynomial noise ratio.The proof uses ciphertext indistinguishability and bootstrapping after correctness through a logarithmic-depth decryption circuit.
  • Quantum capability: Under the same LWE-based assumption, DualHE is quantum-capable, with only an additive logarithmic increase in circuit depth.The paper states that this parameter change does not alter the underlying computational hardness assumption.

6 Extension to Quantum Leveled Fully Homomorphic Encryption

The paper lifts a quantum-capable classical leveled FHE scheme into a quantum leveled FHE scheme using Pauli-encrypted states and encrypted Pauli keys. The resulting construction supports universal quantum circuits, is IND-CPA secure, and evaluates circuits with negligible correctness error.

  • Construction: The quantum scheme encrypts a standard-basis quantum state with a Pauli one-time pad and encrypts the Pauli keys under a quantum-capable classical FHE scheme.Evaluation keys include fresh public keys and encrypted secret-key and trapdoor information for successive circuit levels.
  • Gate evaluation: Clifford gates update encrypted Pauli keys homomorphically, while Toffoli gates use three encrypted CNOT operations to correct the padded state.Clifford and Toffoli gates together form the universal gate set used by the construction.
  • Security: The scheme is IND-CPA secure.The proof replaces encrypted secret keys and trapdoors with encryptions of zero through a sequence of hybrids.
  • Correctness and homomorphism: The scheme is a quantum leveled fully homomorphic encryption scheme.Correctness follows from the encrypted CNOT claim and the final state is negligibly close to the ideal state for polynomially many Toffoli gates.
  • Encrypted CNOT: Each encrypted CNOT transforms the padded quantum state and carries forward encrypted Pauli keys under the next level's public key.The server converts the control ciphertext, performs the encrypted CNOT, and re-encrypts the resulting key material.
Loading 1708.02130v5…