For the last few years (2022, 2021 and 2020), around this time of the year, I published a special festive Q# blog post as part of the Q# Holiday Calendar, organized by Mariia Mykhailova from Microsoft Quantum . While this year there is unfortunately no “official” Q# calendar initiative, I would like to keep the 🎄 holiday spirit alive and prepared a special Q# blog post for this occasion.

Today, we are going to have a look at quantum certified deletion, with examples in Q#.

Quantum Encryption with Certified Deletion 🔗

The paper Quantum Encryption with Certified Deletion by Anne Broadbent and Rabib Islam is one of my favorite publications in recent time in the field of quantum cryptography. It introduces an interesting new concept into the field - certified deletion of encrypted data. Due to the fact that you can always freely copy classical bits, this is obviously a feature impossible to achieve with classical encryption methods.

The underlying idea behind enabling certified deletion relies on the well-known no-cloning principle of quantum information, which states that it is generally impossible to create an exact copy of an unknown quantum state. The paper also builds on ideas introduced and explored in many cryptographic applications, such as Wiesner’s conjugate coding (“Wiesner’s money scheme”) and quantum key distribution (QKD), which together form the basis for the proposed quantum encryption scheme.

The encryption scheme presented in the paper is feasible with current quantum technology and only requires quantum devices for single-qubit preparation and measurements, making it accessible and practical. It is also robust against noise in these devices, which is a crucial aspect for real-world application.

The concept of certified deletion in quantum encryption has potential applications in various fields, especially in scenarios requiring secure data handling and privacy, such as complying with data retention regulations and the ‘right to be forgotten’ clause in personal data processing laws. It also raises questions about the composability of the scheme and its security beyond one-time usage, opening avenues for future research in quantum cryptography.

Exploring the concept 🔗

The steps below outline how the protocol plays itself out. We shall refer to the party that would like to encrypt a message as Alice, and the party receiving the message as Bob. Let’s assume that the message has a bit length of $n$.

1. Bit Array Generation

Alice generates two classical bit arrays, $\theta = (\theta_1, \theta_2, \ldots, \theta_{2n})$ and $r = (r_1, r_2, \ldots, r_{2n})$, each of length $2n$.

She also prepares $2n$ qubits $\ket{r}$.

2. Qubit Encoding Using Wiesner’s Scheme

For each index $i$ from 1 to $2n$, Alice encodes the $i$-th bit $r_i$ of $r$ into a $\ket{r}_{i}$ qubit based on the corresponding $i$-th bit $\theta_i$ of $\theta$:

• If $\theta_i = 0$, she encodes $r_i$ in the Z basis:
  • $r_i = 0$ results in the state of $\ket{r}_{i}$ to be $\ket{0}$.
  • $r_i = 1$ results in the state of $\ket{r}_{i}$ to be $\ket{1}$.
• If $\theta_i = 1$, she encodes $r_i$ in the X basis:
  • $r_i = 0$ results in the state of $\ket{r}_{i}$ to be $\ket{+}$.
  • $r_i = 1$ results in the state of $\ket{r}_{i}$ to be $\ket{-}$.

3. Encryption

To encrypt a message $m$ of length $n$, Alice calculates ciphertext $c$ using one-time pad technique:

$c = m \oplus r_Z$

where $r_Z$ is the subsequence of $r$ where $\theta = 0$.

4. Transmission to Bob

Alice then sends the $c$, as well as all of the qubits $\ket{r}$, to Bob. Bob has two mutually exclusive options, he can either decrypt the data (for that he needs to be handed the key $\theta$), or he can delete the data without decrypting, and return the proof of doing that to Alice.

5a. Decryption

If Bob wishes to decrypt the data, he first reconstructs $r_Z$ by measuring only qubits corresponding to $r_i$ where $\theta_i = 0$. This process is done for all indices $i$ where $1 \leq i \leq 2n$ and $\theta_i = 0$.

After obtaining $r_Z$, Bob calculates $m = c \oplus r_Z$ to decrypt the message.

5b. Certified deletion

Bob may also delete the data without decryption. To do that, Bob measures all qubits $\ket{r}$ in the X basis and sends them back to Alice. Alice can certify deletion by comparing the qubits at indices corresponding to $\theta_i = 1$ with her original values of $r_X$, which is the subsequence of $r$ where $\theta = 1$. If they match, she can confirm the deletion.

Note that by deletion we mean irreversible loss of $r_Z$ information from the qubits. By measuring all qubits in the X basis, qubits at indices $r_i$ where $\theta_i = 1$ produced values that matched $r_X$ but at positions $r_i$ where $\theta_i = 0$ yielded random bits.

Example 🔗

Below is a table illustrating the protocol for a random set of $2n = 8$ bits.

In order to now encrypt a 4 bit message, we can use $r_Z = [1, 0, 1, 0]$, while $r_X = [1, 1, 0, 0]$ can be used to certify deletion.

Q# implementation 🔗

To better study the protocol, we can now implement it in Q#. Let’s start with introducing the entrypoint into our application. We wil allow two parameters to be passed in - the test message to be encrypted, and the flag determining whether we want to run the decryption flow, or the certified deletion flow (since they are mutually exclusive).

@EntryPoint()
operation Main(message: Int, decryptFlow: Bool) : Unit {
    // todo
}

Next we will validate the size of the message and determine the algorithm size (so the value of $2n$). Since we want to simulate this on a classical device, we can reasonably only go to as high as 16 bits (32 would be difficult).

let message_bitsize = BitSizeI(message);
Fact(message_bitsize < 8, "We can't simulate for messages of more than 8 bits");
let algorithm_bitsize = 16;

Message($"Running the algorithm for message: {message}");
Message("");

Next, we will generate the random arrays for $\theta$ and $r$. To keep things manageable and simple, we also want equal distributions of true and false in our $\theta$. This will allow us to have $r_Z$ and $r_X$ of equal length.

let theta = CreateRandomBoolArrayWithEqualDistribution(algorithm_bitsize);
let r = DrawMany(() => DrawRandomBool(0.5), algorithm_bitsize, ());

As a helper, we shall use the array shuffling logic which we introduced in a recent post.

operation CreateRandomBoolArrayWithEqualDistribution(size: Int) : Bool[] {
    Fact(size % 2 == 0, "Size must be divisble by 2");
    
    let array = [true, size = size/2];
    return Shuffled(Padded(-size, false, array));
}

Next, we need to initalize the qubit array, and perform the encoding of $r$ into the qubits using Wiesner’s scheme. We can also simultaneously collect the arrays $r_Z$ and $r_X$ as they will be useful later on.

use qubits = Qubit[algorithm_bitsize];
mutable r_z = [];
mutable r_x = [];

for i in 0..algorithm_bitsize-1 {
    // X basis
    if theta[i] { 
        if r[i] { // 1 is |-⟩
            X(qubits[i]);
            H(qubits[i]); 
        } else { //0 is |+⟩
            H(qubits[i]);
        }
        // save the r value to r_x
        set r_x += [r[i]]; 
    } else {  // Z basis
        if r[i] { // 1 is |1⟩
            X(qubits[i]);
        } else { // 0 is |0⟩
            I(qubits[i]);
        }
        // save the r value to r_z
        set r_z += [r[i]];
    }
}

Message($"θ: {BoolArrayAsBinaryString(theta)}");
Message($"R: {BoolArrayAsBinaryString(r)}");
Message($"R_z: {BoolArrayAsBinaryString(r_z)}");
Message($"R_x: {BoolArrayAsBinaryString(r_x)}");
Message("");

For illustration purposes we can now print out all of the bit arrays - $\theta$, $r$, $r_Z$ and $r_X$. Since Q# does not have a built-in bool array to a binary string converter, we use the following helper function:

function BoolArrayAsBinaryString(arr : Bool[]) : String {
    mutable output = "";
    for entry in arr {
        set output += entry ? "1" | "0";
    }
    return output;
}

Next, we perform the encryption step. For that, we convert the input message into binary array using the built-in IntAsBoolArray function, and then calculate XOR with the $r_z$ using the Xor function. The MappedByIndex array function is helpful here - it allows us to perform an elegant projection of the results into a new array representing the encrypted message.

 let binaryMessage = IntAsBoolArray(message, algorithm_bitsize / 2);
 Message($"Binary message: {BoolArrayAsBinaryString(binaryMessage)}");

 // encrypt by doing XOR between the message and r_z
 let encrypted = MappedByIndex((i, x) -> Xor(binaryMessage[i], x), r_z);
 Message($"Encrypted message: {BoolArrayAsBinaryString(encrypted)}");
 Message("");

From here we have two paths - decryption or certified deletion. Let’s tackle decryption first. We will introduce a Decrypt operation, in which we will use $\theta$ as the key. This allows us to measure the qubits encoded in the Z basis, thus retrieving $r_Z$. With $r_Z$ in our possession, the decryption is simply XOR between the ciphertext bits and the $r_Z$ bits.

operation Decrypt(qubits: Qubit[], theta: Bool[], encrypted: Bool[]) : Bool[] {
    // decrypt using theta as key
    // first obtain r_z by measuring only the qubits that were encoded in the Z basis
    mutable r_z_from_measurement = [];
    for i in 0..Length(theta)-1 {
        if not theta[i] { 
            set r_z_from_measurement += [M(qubits[i]) == One];
        }
    }
    Message($"R_z from qubits: {BoolArrayAsBinaryString(r_z_from_measurement)}");
    
    // now perform XOR between the encrypted data and the r_z
    let decrypted = MappedByIndex((i, x) -> Xor(encrypted[i], x), r_z_from_measurement);
    
    // the decrypted data should be identical to raw message
    Message($"Decrypted binary message: {BoolArrayAsBinaryString(decrypted)}");
    Message($"Decrypted message: {BoolArrayAsInt(decrypted)}");
    return decrypted;
}

The other possibility is to delete and certify that. For that, we will introduce two operations - the first one is Delete, which constitutes measuring the qubits in the X basis.

operation Delete(qubits: Qubit[]) : Bool[] {
    mutable deletion_proof = [];
    for i in 0..Length(qubits)-1 {
        set deletion_proof += [MResetX(qubits[i]) == One];
    }

    return deletion_proof;
}

The second one is the verification operation called VerifyDeletion, which compares the deletion results, for indices where $\theta = 1$, with the original $r_X$:

operation VerifyDeletion(theta: Bool[], r_x: Bool[], d: Bool[]) : Unit {
    mutable d_x = [];
    for i in 0..Length(theta)-1 {
        if theta[i] {
            set d_x += [d[i]];
        }
    }

    // now verify the deletion by comparing d_x to r_x - they must be identical
    Message($"R_x from qubits: {BoolArrayAsBinaryString(d_x)}");
    AllEqualityFactB(d_x, r_x, "R_x obtained from measuring the qubits is different than the original one!");
}

AllEqualityFactB is a helper function from the Microsoft.Quantum.Diagnostics namespace, which asserts that two arrays of boolean values are equal. This is very useful here, as the program will panic if the assertion fails.

The final thing left to do is to invoke and orchestrate the operations we introduced above, based on the value of the decrypt flag that is passed into the program.

if decryptFlow {
    // decrypt flow
    let decrypted = Decrypt(qubits, theta, encrypted);
    AllEqualityFactB(decrypted, binaryMessage, "The decrypted message is different than the original one!");
} else {
    // delete and verify flow
    let deletion_proof = Delete(qubits);
    VerifyDeletion(theta, r_x, deletion_proof);
}

ResetAll(qubits);

This is everything - we are ready to try the program out.

Trying out Q# certified deletion 🔗

We will first run it for the decryption flow. Let’s pass 4 as our message.

dotnet run --message 4 --decrypt-flow true 

The output would differ from run to run - since the $\theta$ and $r$ arrays involved are random - but it should resemble this:

Running the algorithm for message: 4

θ: 1101011010001001

R: 0101011001000011

R_z: 00010001

R_x: 01111001

Binary message: 00100000

Encrypted message: 00110001

R_z from qubits: 00010001

Decrypted binary message: 00100000

Decrypted message: 4

Most importantly, because of the asserts we included, we know the logic was successful, otherwise the program would have panicked. As we can see from the log above, the input message and the resulting message are the same - 4.

Finally, we can also try the certified deletion flow:

dotnet run --message 4 --decrypt-flow false

This should produce the output similar to:

Running the algorithm for message: 4

θ: 1111000001010101

R: 1001001100000011

R_z: 00110001

R_x: 10010001

Binary message: 00100000

Encrypted message: 00010001

R_x from qubits: 10010001

In this case, we also know that the algorithm was successful because otherwise the assert would have caused a panic. The $r_X$ obtained from the measurement of the qubits is the same as the initial one.

Conclusion 🔗

This concludes this edition of our traditional holiday celebration with a Q# blog post. I hope this article was enjoyable - and I encourage you to explore the full source code on Github and the original paper by Broadbent and Islam.

As the holiday season is coming up, I want to wish everyone happy holidays. I hope you get to spend some great time with your family and friends. Here’s to a new year that brings good health, happiness, and success in whatever you do. 🎅🏻