The scheme AUX (presented in [BJ15]) is a quantum homomorphic encryption scheme that is homomorphic for Clifford circuits and a limited number of T gates, by providing auxiliary states in the evaluation key that will get rid of the phase error after applying a T gate. As the number of layers of T gates in the circuit, \(L\), grows, the evaluation key grows exponentially. Therefore, AUX can only deal with a constant number of T gates. AUX extends the simpler scheme CL.

 

Key features: homomorphic, computational security

 

 

Definition

Key generation

Contrary to CL, AUX is a symmetric-key scheme.

  1. Use HE.KeyGen to generate pk, sk, and evk.
  2. Generate auxiliary states of the form \(Z^bP^a|+\rangle\), that will later be used to correct any phase errors caused by the evaluation of a T gate. Because the evaluator needs to be able to correct for any polynomial \(a\) (with variables being measurement outcomes and QOTP keys), the evaluation key needs to contain enough of these auxiliary states, for every monomial that can possibly arise. The evaluator can later combine two of these 'ingredient' auxiliary states \(Z^{b_1}P^{a_1}|+\rangle\) and \(Z^{b_2}P^{a_2}|+\rangle\) into \(Z^{b'}P^{a_1 \oplus a_2}|+\rangle\), where \(b'\) is a straightforward (but not linear) update of the \(Z\) key.
  3. Secret key = sk + random QOTP keys for the input + random Z-keys for the auxiliary states.
  4. Evaluation key = pk + evk + encrypted QOTP keys + auxiliary states (see 2).
Encryption
use the provided QOTP keys to apply the right Paulis. If more input states are given than Pauli keys, abort.
Decryption
 as in CL.

 

 

Security

See CL for a discussion of the impossibility of information-theoretic security of homomorphic encryption. Like CL, EPR and TP, it can be shown that AUX inherits q-IND-CPA security from the classical homomorphic encryption scheme.

 

 

Efficiency

The efficiency bottleneck for AUX lies in the number of auxiliary states that need to be generated. In [BJ15] it was shown that this number grows roughly as \(O(2^{n^{L}})\), where \(n\) is the number of input qubits and \(L\) is the number of T gate layers in the circuit. This means that only circuits with a constant number of T gate layers can be efficiently be evaluated.

The other steps (encryption, evaluation, decryption) are similarly efficient to CL.

 

 

Homomorphic computation (without interaction)

For Clifford group gates, evaluation is the same as in CL. Therefore, we focus on the evaluation of a T gate in this section.

 

In order to evaluate a T gate, the server needs to compute the (homomorphically encrypted) current keys to the quantum one-time pad, directly apply the T gate, and construct (from the ingredient auxiliary states) the appropriate auxiliary states. Then use those (by entangling and measuring) to remove the phase error.

 

 

See also