The trap code is a quantum message authentication code first introduced in the context of quantum one-time programs [BGS12]. Its security is further explored in [BW16]. The trap code ensures integrity of the data by combining a CSS code to 'spread out' the data with the insertion of check qubits ('traps') at random locations, and a quantum one-time pad on the entire state.

 

Key features: authentication, approximate information-theoretic security

 

 

Definition

Let \(E\) be an encoding operation for a \([[m,1,d]]\) quantum error-correcting code (QECC) (TODO link), implemented by a Clifford circuit. Furthermore, it is required that the code is a CSS code (which allows transversal CNOT) and self-dual (which allows transversal Hadamard).

Key generation
  1.  Pick a random permutation \(\pi\) of size \(3m\).
  2. For every qubit that will be encoded, generate \(6m\) bits of classical randomness.
Encoding

 Qubit-by-qubit:

  1. Apply \(E\).
  2. Append \(2m\) traps: half \(|0\rangle\) (the X-traps), half \(|+\rangle\) (the Z-traps).
  3. Permute the qubits according to \(\pi\).
  4. Apply a quantum one-time pad using the classical randomness in the key.
Decoding
  1.  Remove the quantum one-time pad, and unpermute.
  2. Measure the X-traps in the computational basis and the Z-traps in the Hadamard basis. If they are not in their original state, reject.
  3. Decode the QECC.

 

Delegated computation (with interaction)

Performing computations on qubits encoded by the trap code is a form of QCAD (quantum computing on authenticated data). Here is how to do it:

 

Measurement in the computational basis

The server measures all qubits separately in the computational basis, and sends the measurement results to the client. The client:

 

Paulis

Client updates the keys (for the data qubits only), while server does nothing.

 

CNOT

Any CSS code is transversal for CNOT gates, so CNOT is applied to every qubit separately. Note that \(CNOT|0\rangle|0\rangle = |0\rangle|0\rangle\) and \(CNOT|+\rangle|+\rangle = |+\rangle|+\rangle\), so the traps remain unchanged. Afterwards, the client updates the QOTP keys

 

P

The client encodes a magic state \(P|+\rangle\) according to the encryption procedure above. The server then entangles with this magic state and measures. Depending on the measurement outcome, the client applies a \(Y\) correction to the data qubit (by updating the keys, see above).

 

T

The client encodes a magic state \(T|+\rangle\) according to the encryption procedure above. The server then entangles with this magic state and measures. Depending on the measurement outcome (which can be decoded by the client), the procedure for a corrective P gate may be started.

Note that the server is allowed to know the logical measurement outcome, since it is independent of the encryption. Therefore, the client can tell the server in the clear whether or not such a correction should happen.

 

H

Even though the CSS code is transversal for H, the H gate swaps the roles of the X-traps and the Z-traps. This is fine as long as the H gate is only (directly) applied right before a measurement (in that case, the client should discard the X-trap measurements and check the Z traps instead). The Hadamard is then implemented by having the client encode a magic state \((H \otimes I)(|00\rangle + |11\rangle)\), and having the server perform a bell measurement on the second qubit of the magic state, together with the data qubit. This involves applying an H gate right before measurement, but this is not a problem. Conditioned on the measurement outcomes, the client performs a Pauli correction.

 

All quantum communication can be done before and after the computation (the magic states are not dependent on the computation). For all gates except the T gate, the classical communication can be postponed until the end of the computation (or until the next T gate).

 

Security

The security of the trap code depends on the distance \(d\) of the underlying QECC. It is \((2/3)^{d/2}\)-secure against Pauli attacks, meaning that the probability (taken over all possible permutations / QOTPs) that a fixed Pauli attack \(Q\) acts nontrivially on the logical data without revealing an error in the traps ('error syndrome') is at most \((2/3)^{d/2}\).

 

The trap code is a so-called encode-encrypt scheme, where the data is first encoded using a random encoding (in this case, a CSS code plus a random permutation), and then encrypted using a quantum-one time pad. This allows arguing security using the Pauli twirl, to show that any attack on the encoded-encrypted state is equivalent to a probabilistic mixture of Pauli attacks.

 

It is important to use the same permutation on all the input qubits, because otherwise traps and data will mix at the application of a CNOT gate. Even though this seems insecure, it does not matter as long as the QOTP keys are fresh for all input qubits.

 

TODO: rigorous security proof can be extracted from section 6 of [BGS12] or from [BW16].

 

 

Efficiency

Depending on the blowup \(m\) of the CSS code (which depends on the desired security parameter), there is considerable overhead in the size of the quantum state that needs to be handled. It should be noted, however, that compared to the Clifford code (where every party adds its own check qubits), the trap code does not grow as the number of parties grow: every player in a multi-party setting can apply his/her own permutation and quantum one-time pad on top of the others.

 

Classical interaction is needed for the evaluation of every type of gate (except Paulis). Quantum interaction is needed for P, H and T. The auxiliary states that the client prepare are encoded, so they are again relatively big (again, depending on \(m\)).

 

 

 

 

See also