Summary

In the last blog post, I introduced my plan to make the safest cryptographic box in the world, and to make it widely available. This would, in theory, make it possible to run infinitely dangerous programs (including superintelligences) safely. This cryptographic box was supposed to use a scheme that is fully homomorphic and perfectly secret at the same time. However, in the last four months, something has changed:

• I discovered that the symmetric Quantum Fully Homomorphic Encryption scheme with perfect secrecy that I was using has a flaw.
• I managed to find a partial fix for the scheme and to implement it. I will prove that this fix enables us to safely evaluate every Clifford gate. But this fix still doesn't enable us to safely evaluate every quantum gate.
• However, not all hope is lost. Although this specific scheme, made by Min Liang, has a flaw, there is another QFHE scheme with perfect secrecy made by the same researcher. In the future, I will try to implement this second QFHE scheme instead, hoping that it does not have any flaw.

This post explains in more details these points. I will also raise concerns about whether such QFHE scheme could help malevolent actors hide the training of superintelligences. If you know about any other FHE or QFHE scheme with perfect secrecy than the ones I have cited, please let me know.

Prerequisites to understand this post

In quantum computing, quantum gates are represented by matrices, and quantum states are either represented as vectors or as density matrices. If we want to apply a gate $G$ on a state $s$ in the vector paradigm, we compute $G\cdot s$, whereas if we want to do so in the density matrix paradigm, we compute $G\cdot s\cdot G^{-1}$. I will use the density matrix paradigm, as it gives more information, and because it is the paradigm used in the article that introduced this QFHE scheme. To understand this post, we need to know about the following quantum gates and quantum states:

• $X=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$, $Y=\left(\begin{array}{cc}0& -i\\ i& 0\end{array}\right)$, and $Z=\left(\begin{array}{cc}1& 0\\ 0& -1\end{array}\right)$ are called the Pauli gates. The most familiar of these is the $X$ gate, which is a generalization of the classical $NOT$ gate. Indeed, it transforms zeros into ones and ones into zeros. The other two gates do not have any analog gate in classical programming. They are called $X$, $Y$, and $Z$ because they flip the state of the qubit 180 degrees along the $x$, $y$, and $z$ axes.
• $CNOT=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right)$ is a two-qubit gate which applies an $X$ gate on the second qubit if and only if the first one is active. We call it the controlled NOT gate because it applies a $NOT$ gate on the target qubit according to the control qubit. We often say that it is a generalization of the $XOR$ gate, because it sets the target qubit to the $XOR$ between itself and the control qubit. Along with the Hadamard gate $H=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$ and the gate $S=\left(\begin{array}{cc}1& 0\\ 0& i\end{array}\right)$, they form a group of gates called the Clifford group. This group contains the Pauli group.
• $R_x\left(\theta \right)=\left(\begin{array}{cc}\cos \left(\theta /2\right)& -i\sin \left(\theta /2\right)\\ -i\sin \left(\theta /2\right)& \cos \left(\theta /2\right)\end{array}\right)$, $R_y\left(\theta \right)=\left(\begin{array}{cc}\cos \left(\theta /2\right)& -\sin \left(\theta /2\right)\\ \sin \left(\theta /2\right)& \cos \left(\theta /2\right)\end{array}\right)$, and $R_z\left(\theta \right)=\left(\begin{array}{cc}{e}^{-i\theta /2}& 0\\ 0& e^{i\theta /2}\end{array}\right)$ are called the rotation operator gates. They are generalizations of the Pauli gates: They perform a rotation of $\theta$ radians along the $x$, $y$, and $z$ axes. They together can form any one-qubit gate.
• $U(\alpha ,\beta ,\gamma ,\delta )=e^{i\alpha }{R}_z\left(\beta \right)R_y\left(\gamma \right)R_z\left(\delta \right)$ is the universal one-qubit gate, which also can form any one-qubit gate. To do so, it takes four parameters. It can represent any one-qubit gate. Together with $CNOT$, they form a universal gate set, which means that any quantum operation (and therefore any classical operation) can be performed using only these gates.
• $I_k$ is the identity matrix of length $k$. It leaves everything unchanged.
• $e_k$ is the vector that contains zeros everywhere except for a 1 at position $k$, whereas $e_{k,k}$ is the matrix that contains zeros everywhere except for a 1 at position $(k,k)$.
• $\otimes$ is the Kronecker product, which converts a $k$-qubit gate and a $l$-qubit gate into a $(k+l)$-qubit gate.
• A matrix to the power of zero is equal to the identity matrix.

The scheme

Encryption

If we want to encrypt a message of $n$ bits, we firstly have to transform it into a standard unit vector. For instance, to encrypt the sequence of bits 011, we first convert it into decimal (in which case we get 3), and we then convert it into the vector of $2^n$ elements with zeros everywhere except for a 1 at position 3+1, which is the vector $e_{3+1}$:

After that, we convert it into a density matrix that we note $\rho$ (we call it the plaintext). As the message is not a superposition, the density matrix is simply a square matrix whose diagonal is the vector we just computed:

Then, we select two random sequences $a$ and $b$, each of length $n$. These sequences are called the keys. With these sequences, we can now compute the ciphertext, which is:

Evaluation of CNOT

To apply a $CNOT$ gate on the $i$-th bit according to the $(i-1)$-th bit, we firstly have to compute a matrix $CNO{T}^{\prime }$ like so:

Then, we update $\sigma$ according to this formula:

Evaluation of the universal one-qubit gate

To apply $U(\alpha ,\beta ,\gamma ,\delta )$ on the $i$-th bit, we compute $U^{\prime }(\alpha ,\beta ,\gamma ,\delta )$ like so:

And we then update $\sigma$ according to this formula:

Decryption

To get back the plaintext from the ciphertext, we use the following formula:

At this point, $\rho$ is the density matrix we were looking for. If the result is not a superposition, then we can transform $\rho$ into a standard unit vector of the form $e_{j+1}$ by taking the diagonal (If the diagonal is not a standard unit vector, or that the matrix has non-zero elements outside of the diagonal, then the result is not a classical state). Finally, we convert $j$ back to binary to get the initial sequence of bits.

How the scheme looks like in Python

I coded the QFHE scheme in Python. It may help you understand how the scheme is supposed to work. If you are interested, you can find my programs here. One program shows how to implement the Toffoli gate using the scheme, and another one shows how to implement Rule 60, which outputs a Sierpiński triangle (but a very small one because we are trying to simulate a quantum computer inside of a classical computer, which takes a lot of time to compute).

The problem

The problem in the evaluation of CNOT

Suppose we have a ciphertext $\sigma$ corresponding to a plaintext $\rho$ that contains only classical states. Let's try to homomorphically apply a $CNOT$, where the control qubit is ${\rho }_i$ and the target qubit is ${\rho }_j$. From this operation, we obtain a ciphertext ${\sigma }^{\prime }$ corresponding to a plaintext ${\rho }^{\prime }$. $\sigma ={\sigma }^{\prime }$ is equivalent to $Decryp{t}_{a,b}\left(\sigma \right)=Decryp{t}_{a,b}\left({\sigma }^{\prime }\right)$, which is equivalent to $\rho ={\rho }^{\prime }$, which is equivalent to ${\rho }_j={\rho }_j^{\prime }$, which is equivalent to saying that the target qubit of the $CNOT$ didn't change, which is equivalent to saying that the control qubit of the $CNOT$ was equal to 0, which is equivalent to ${\rho }_i=0$. Therefore, $\sigma ={\sigma }^{\prime }⟺{\rho }_i=0$. In other words, by checking whether the ciphertext changed after homomorphically applying a $CNOT$, we can deduce the value of the control qubit in the plaintext.

The same problem in the evaluation of the universal one-qubit gate

Initially, I thought that the problem arose only for the evaluation of $CNOT$. For the problem to arise for one-qubit gates, we would need a one-qubit gate $G$ and two states $S_1$ and $S_2$ such that applying $G$ on $S_1$ changes $S_1$, but that applying $G$ on $S_2$ doesn't change $S_2$. I initially failed to find such a gates, and wrongly thought that it may not exist. However, such gates do exist. For instance, applying the $X$ gate on the $|0⟩$ state does change it, but applying it on the $|+⟩$ state doesn't change it. Therefore, if Alice takes one of these two states randomly, encrypts it, and asks you to homomorphically perform an $X$ gate on it, then you could guess which state she chose by looking at whether the ciphertext changes after evaluating the $X$ gate.

Actually, this problem arises for every one-qubit gate, except for the identity gate. Indeed, since a one-qubit gate corresponds to a rotation of the Bloch sphere, and that every non-null rotation of a sphere has exactly two fixed points, then for every one-qubit gate that is different than the identity gate, there are exactly two inputs that do not change, while the other inputs do change.

A more general version of the problem

Suppose you have a program which, when given the sequence 000, loops back after three timesteps, but which, when given the sequence 111, loops back after two timesteps. Suppose then that Alice took one of these two possible inputs randomly, encrypted it, sent the ciphertext to you, and then asked you to homomorphically run the program on the ciphertext. When running the program, you will see that the ciphertext will loop either every two timesteps or every three timesteps. From this observation, you will be able to guess whether the input Alice took was 000 or 111. That is, you learned something from the plaintext by just applying the evaluation phase.

It turns out that this problem is a generalization of the first one: The first problem is the specific case where the program loops back instantly according to one input, but loops back after two timesteps according to another input.

What we would need to solve this problem

When the plaintext/program loops back, we would want the ciphertext not to loop back too. In other words, we would want "same plaintext $\to$ different ciphertexts" to be possible. To do this, we need a key update. But, which key update do we need? To answer this question, I will show in the next section that, in classical computing, the $XOR$ gate can be evaluated safely. By "evaluated safely", I mean that no one involved in the computation can learn anything about the program, unless they cheat by communicating to each other.

How we would solve the problem in classical computing

The XOR gate can be evaluated safely

Suppose that Phoebe has a plaintext, that she generates a random key of identical length, and that she $XOR$s the two to get a ciphertext (this is the One-time pad that was discussed it in the last post). Then, she sends the key to Kevin and the ciphertext to Charlie. In this way, neither Kevin and Charlie can have any information about the plaintext. After a while, Kevin and Charlie give back the key and the ciphertext, that they modified without communicating to each other or to Phoebe. Phoebe then $XOR$s the two results to get a new plaintext. Now the question is, is there a scheme that Kevin and Charlie can follow in order to compute any function in this way?

I do not know whether this is possible. But it is very easy to see that at least one function is computable in this way. The most obvious example is the identity function, where Kevin and Charlie just do nothing. However, are there other functions? The answer is yes. Actually, every circuit $C$ that consist only of $XOR$ gates can can be computed in this way. To do so, Kevin and Charlie just need to apply $C$ on the key and the ciphertext. For instance, in this picture, Kevin and Charlie help Phoebe to compute a circuit that consists of a single $XOR$ gate:

This shows that it is possible to run any infinitely dangerous program safely as long as they consist only of $XOR$ gates. Indeed, if the program could affect Kevin or Charlie, then they would have gained information about the plaintext, which would contradict the perfect secrecy of the One-time pad.

Are there other classical gates evaluable in this way?

By looking at the picture closely, we can see that asking ourselves whether we can evaluate a function $F$ in this way is equivalent to asking ourselves whether there exist two functions $Kevin$ and $Charlie$ such that:

If we assume that $Kevin$ and $Charlie$ are classical circuits, then the only classical circuits that we can compute in this way are the ones that can be built using only $XOR$ gates (Technically, I considered only two-bit and three-bit programs, but it seems very unlikely to me that adding more bits would change the result). To show this, I created a program that brute-forces the problem:

"""We want to find Kevin and Charlie such that Kevin(k1, k2) ⊕ Charlie(k1 ⊕ p1, k2 ⊕ p2) = F(p1, p2)"""
import itertools

def allBinaryFunctions():
    return [(lambda x, y, array=arr: array[2*x + y]) for arr in itertools.product([0, 1], repeat=4)]

for F in allBinaryFunctions():
    for Kevin, Charlie in itertools.product(allBinaryFunctions(), repeat=2):
        areValid = True
        for (k1, k2, p1, p2) in itertools.product([0, 1], repeat=4):
            areValid &= Kevin(k1, k2) ^ Charlie(k1 ^ p1, k2 ^ p2) == F(p1, p2)
            if not areValid:
                break
                                
        if areValid:
            print("Found", F(0, 0), F(0, 1), F(1, 0), F(1, 1))
            print("Kevin :", Kevin(0, 0), Kevin(0, 1), Kevin(1, 0), Kevin(1, 1))
            print("Charlie :", Charlie(0, 0), Charlie(0, 1), Charlie(1, 0), Charlie(1, 1), "\n")
            break

This program outputs every two-bit functions that Kevin and Charlie can compute together. However, it turns out that all of those programs are exactly those that can be built using only the $XOR$ gate.

This is unfortunate for us, because the $XOR$ gate isn't a universal gate. However, not all hope is lost, as we focused only on classical computing. Is there a way to compute more functions than that using quantum computing?

I will now show that a similar technique can be applied for the QFHE scheme. However, there are still a few differences. For instance, in the QFHE scheme, we have two keys instead of one.

Which quantum gates can be evaluated safely without ancilla qubits?

An algorithm to know whether a one-qubit gate can be evaluated safely without ancilla qubits

Suppose, without loss of generality, that our ciphertext has a single qubit. We would want to safely evaluate a one-qubit gate $G$ without any ancilla qubit. Kevin will be given the two keys, which are the two bits $a_1$ and $b_1$, whereas Charlie will be given the ciphertext, which is a qubit $\sigma$. Kevin and Charlie will have to update $(a_1,b_1)$ and $\sigma$ respectively, using two functions $f,g:B\times B\to B$ and a quantum gate $G^{\prime }$ like so:

For the evaluation to be valid, it should be the case that encrypting a plaintext $\rho$, then applying the update, and then decrypting it gives us the right plaintext. In other words, it should be the case that, for all $(a_1,b_1)\in B^2$ and all $\rho$, this equation holds:

Firstly, given $G^{\prime }$, $f$ and $g$, how can we verify whether the equation holds for every $(a_1,b_1)$ and $\rho$? We cannot enumerate all the possible $\rho$, as there is an infinite amount of them. We could also try a lot of different $\rho$, but this would take a while, and we may still miss some rare exceptions. To solve this problem, I will firstly have to show that for every gate $A$ and $B$, we have $AC{A}^{-1}=BC{B}^{-1}$ for every state $C$ if and only if there exists $\lambda$ such that $A=\lambda B$. (This post initially had a proof that worked only for $2\times 2$ reversible matrices. Thankfully, one of my classmates, Julia PHAM BA NIEN, gave me a proof that works for every reversible matrix, which is now included here).

Therefore, $B^{-1}A$ has to commute with every other matrices. Let's prove that only matrices of the form $\lambda I$ do so. Firstly, it is trivial that every matrix of the form $\lambda I$ commutes with every other matrices, as $\left(\lambda I\right)C=\lambda C=\lambda CI=C\left(\lambda I\right)$. Now, let's prove that every matrix that commutes with every other matrices are of the form $\lambda I$. Let $P$ be a matrix that commutes with every other matrices. Note in particular that, for every $i$, we have:

Therefore, for every $i$ and $j$, we have ${\alpha }_{i,j}=0$ if i $\ne j$, and ${\alpha }_{i,j}={\alpha }_{1,1}$ if $i=j$. Therefore, all non-diagonal elements are equal to zero, and all diagonal elements are pairwise equal. As such, $P$ is of the form $\lambda I$. In our case, we therefore have $B^{-1}A=\lambda I$, and therefore $A=\lambda B$, which concludes the proof.

This property is useful to us, because our equation can be rewritten in the form $AC{A}^{-1}=BC{B}^{-1}$ like so: