The scheme CL (folklore, formalized in [BJ15]) is a quantum encryption scheme that is homomorphic for Clifford circuits. It is based on any classical fully homomorphic encryption scheme and inherits the (computational) security properties from that scheme. CL is extended in different ways to schemes that are homomorphic for larger classes of circuits (see EPR, AUX, TP).

Key features: homomorphic for Clifford circuits, simple, computational security.

Definition

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

Key generation	Run HE.KeyGen to get classical secret key, public key and evaluation key: \(sk, pk, evk\). These are the keys for CL.
Encryption	Encrypt the state using a randomly selected quantum one-time pad, and encrypt all the keys separately using \(HE.Enc_{pk}\).
Decryption	Decrypt all the quantum one-time pad keys using \(HE.Enc_{sk}\) and decrypt the quantum state according to the procedure for the quantum one-time pad.

Security

In the quantum case, perfectly secure homomorphic encryption is not possible without serious efficiency issues [YPF14]. Even when the security requirement is relaxed to approximate information-theoretic security, homomorphic encryption is not possible in the quantum case (draft from Michael Newman and Yaoyun Shi, 2016, no preprint yet TODO). Therefore, the best one can hope for is computational security under some quantum-safe assumptions. CL achieves this.

The security of CL depends on the security of the quantum one-time pad (which is information-theoretic / perfect) and on the security of the classical homomorphic encryption scheme. The latter cannot have information-theoretic security while also being efficient, but there exist classical schemes which are safe against quantum attackers, specifically they are q-IND-CPA secure. The CL scheme inherits this security. It is proven through an indistinguishability game.

Efficiency

The key generation is a strictly classical procedure, the efficiency of which depends on the classical scheme HE (improvements to this scheme will benefit CL directly). The encryption procedure requires a source of true randomness (to sample \(2n\) classical bits for the QOTP), plus the resources required for the classical scheme. Decryption is again dependent on the classical homomorphic decryption procedure (which is typically in NC1), plus the \(n\) Pauli operations required for the decryption of the quantum one-time pad.

Homomorphic computation (without interaction)

An indefinite number of Clifford gates can be homomorphically applied, by applying the gate directly to the encrypted data, followed by a (classical) homomorphic update of the keys to the quantum one-time pad. Below are the update rules for applying \(P\), \(H\), and \(CNOT\).

Hadamard gate

Directly applying \(H\) to a single-qubit state \(X^aZ^b|\psi\rangle\) results in

\(HX^aZ^b|\psi\rangle = X^bZ^aH|\psi\rangle\),

which is a valid QOTP encryption of the state \(H|\psi\rangle\). The evaluator now only needs to update the keys \((a,b)\) to \((b,a)\). Since the evaluator holds the classical homomorphic encryption of \(a\) and \(b\), this update can be performed homomorphically by the evaluator.

Phase gate

Directly applying \(P\) to a single-qubit state \(X^aZ^b|\psi\rangle\) results in

\(PX^aZ^b|\psi\rangle = X^aZ^{a\oplus b}P|\psi\rangle\),

which is a valid QOTP encryption of the state \(P|\psi\rangle\). The evaluator updates the keys homomorphically.

CNOT gate

Directly applying \(CNOT\) to a two-qubit state \((X^aZ^b \otimes X^cZ^d) |psi\rangle\) (where the first qubit is the control wire) results in

\(CNOT (X^aZ^b \otimes X^cZ^d)|\psi\rangle = (X^a Z^{b \oplus d} \otimes X^{a \oplus c}Z^d)CNOT|\psi\rangle\),

which is a valid QOTP encryption of the state \(CNOT|\psi\rangle\). The evaluator updates the keys homomorphically.

Circuit privacy

All Clifford gates can be applied privately, as long as the classical homomorphic encryption scheme allows for circuit privacy. This is achieved by letting the evaluator apply a random Pauli at the very end of the computation (and undoing it by updating the key to the quantum one-time pad appropriately). This effectively randomizes the QOTP key, so that it does not reveal the circuit that was applied. See [DSS16] for the proof.

Delegated computation (with interaction)

Delegated computation is possible, with quantum communication after every \(T\) gate.

Paulis

No communication needed (homomorphic)

Cliffords

No communication needed (homomorphic)

\(T\) gates

An example of a two-way quantum communication scheme (with two rounds) would be:

Evaluator applies \(T\) gate to encrypted state, and tells the client he has done so. The evaluator also sends the client the current (encrypted) keys to the quantum one-time pad.
Client decrypts the keys and determines whether or not a phase correction \(P\) needs to be applied, and sends an (QOTP-encrypted) magic state, either \(P|+\rangle\) or \(|+\rangle\). The client also sends encrypted classical information that will help update the key (which magic state was sent, which QOTP key was used to encrypt it).
The evaluator teleports the state through the magic state, and uses the measurement outcomes to homomorphically update the keys.

This extension was not in the original presentation of the scheme [BJ15], but instead is based on rather straightforward/standard techniques.

TODO:

The CL scheme might allow for verification (using trap codes, for example).

The CL scheme might be blind, depending on what class the universal circuits falls into if one wants it to execute a Clifford circuit. A fully homomorphic encryption method might be needed.

Open questions

If we plug in a CCA secure classical scheme, will CL become CCA secure? (There was a paper on this, but it is not on the Arxiv yet: Chosen-Ciphertext Secure Fully Homomorphic Encryption. - Ran Canetti (TAU, BU), Srinivasan Raghuraman (MIT), Silas Richelson (TAU, BU), Vinod Vaikuntanathan (MIT))