The quantum one-time pad (QOTP) [MTdW00] is a symmetric-key encryption scheme that serves as an ingredient for many other encryption schemes. It works analogously to the classical one-time pad.

 

Key features: simple, efficient, information-theoretic security

 

TODO See https://arxiv.org/abs/quant-ph/0111046 and compare.

 

 

Definition

Key generation
For every \(i \in [1,n]\), pick \(a_i,b_i \in_R \{0,1\}\).
Encryption
(qubit-by-qubit) apply \(X^{a_i}Z^{b_i}\) to the \(i\)th qubit.
Decryption
(qubit-by-qubit) apply \(X^{a_i}Z^{b_i}\) to the \(i\)th qubit.

 

 

Security

The QOTP provides information-theoretic security: to a party that does not know the key, the ciphertext seems completely mixed. This is proven by averaging over all possible keys [BJ15] [Dul16].

 

 

Efficiency

The key generation is a strictly classical procedure that requires a source of true randomness (to sample \(2n\) classical bits). Encryption and decryption are both very simple and efficient, requiring only \(n\) Pauli operations each.

 

 

Homomorphic computation (without interaction)

An indefinite number of Paulis can be homomorphically applied as follows: say we have a single-qubit ciphertext \(X^aZ^b|\psi\rangle\) and want to apply a Pauli \(X^cZ^d\) to the plaintext \(|\psi\rangle\). This can be done by just applying it to the ciphertext, since \(X^cZ^dX^aZ^b|\psi\rangle = X^aZbX^cZ^d|\psi\rangle\). The keys do not change.

 

Circuit privacy

In principle, all Paulis can be applied privately (the decryptor cannot tell the difference between e.g. \(XX\) and \(I\)). Since no other gates can be applied homomorphically, this technically meets the definition of circuit privacy. However, the concept of circuit privacy is not very meaningful for such a limited class of operations.

 

 

Delegated computation (with interaction)

Extension of the QOTP to allow for delegated computation is possible, with classical communication rounds after every Clifford gate, or quantum communication after every \(T\) gate. This is not part of the original scheme. It is the most basic form of delegated quantum computation, requiring a lot of communication and still relatively much quantum power from the client.

Paulis
No communication needed (homomorphic)
Cliffords
Apply the gate, then use one-way communication from evaluator to client to communicate which gate was applied. The client updates the keys according to the Pauli-Clifford commutation rules.
\(T\) gates

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

  1. Evaluator applies \(T\) gate to encrypted state, and tells the client he has done so.
  2. Client determines whether or not a phase correction \(P\) needs to be applied by analyzing the current key to the quantum one-time pad, and sends an (QOTP-encrypted) magic state, either \(P|+\rangle\) or \(|+\rangle\).
  3. The evaluator teleports the state through the magic state, and sends the measurement outcomes to the client.
  4. The client updates the current keys to the quantum one-time pad.

 

 

 

Multiparty computation

Multiple parties can put their own QOTP on the same state. The result is an encryption that is passively secure against any coalition of \(n-1\) parties (there is no information about the key in their \(n-1\) individual keys). All parties hold additive shares of the key. Application of Clifford gates would be straightforward (all parties can update their keys individually), but the application of T gate is already more involved.