The scheme EPR (presented in [BJ15]) is a quantum encryption scheme that is homomorphic for Clifford circuits and a limited number of T gates. As the number of T gates in the circuit grows, the decryption function becomes less efficient. EPR can only be considered compact (a requirement for homomorphic schemes) if the number of T gates is constant. EPR extends the simpler scheme CL.

 

Key features: homomorphic, computational security.

 

 

Definition

Let HE be the classical (fully) homomorphic encryption scheme.

Key generation
Same as CL (run HE.KeyGen)
Encryption
Same as CL (apply a quantum one-time pad, and classically encrypt the keys to that)
Decryption

For every T gate that was applied during the computation, the client is sent a helper qubit (see below):

  1. Decrypt the information about the quantum one-time pad (sent by the server).
  2. Combine this information with any previous measurement results in order to determine whether to apply \(H\) or \(HP\) on the helper qubit, and apply.
  3. Measure the helper qubit (this information is used in step 2 for the next helper qubit).

Using all the measurement results, the QOTP on the output state can be computed, which can then be removed.

Note that the decryption does not happen qubit-by-qubit, so the scheme is indivisible [BJ15]

 

Security

See CL for notes on impossibility of perfectly secure homomorphic encryption.

 

The security of EPR follows directly from (and is identical to) that of CL: it is q-IND-CPA secure, based on the computational assumptions of the classical homomorphic encryption scheme.

 

 

Efficiency

Key generation (classical) and encryption (using Paulis) are identical to CL. In the evaluation phase, the evaluator needs to generate some extra EPR pairs (one for every T gate), but otherwise he acts the same as in CL. The decryption procedure depends on the number of T gates, \(t\), the number of output qubits, \(m\), and the complexity of the classical homomorphic encryption function, \(O(p(\kappa))\); the complexity is \(O(t^2 + tp(\kappa) + mp(\kappa) + mt)\). Hence, the decryption function depends quadratically on \(t\), and is called \(t^2\)-quasi-compact.

 

 

Homomorphic computation (without interaction)

As in CL, an indefinite number of Clifford gates can be homomorphically applied. The procedure is exactly the same. Thus, we only focus on how to evaluate a T gate:

  1. Apply the T gate to the data qubit \(X^aZ^b|\psi\rangle\)
  2. Entangle the data qubit with one half of an EPR pair (using only CNOT, targeting the data qubit).
  3. Measure the data qubit.

The qubit from the EPR pair now possibly has a phase error on int. Afterwards, during decryption, the client can remove this phase error by acting on the other  qubit from the EPR pair (in a way that depends on \(a\), which information is given after the evaluation phase).

 

 

See also