In 2010, Paul Christiano wrote Cryptographic Boxes for Unfriendly AI, in which he asks how we can sandbox arbitrarily dangerous AIs and recommends Homomorphic Encryption as a potential solution. However, Homomorphic Encryption relies on computational assumptions (it does not provide perfect secrecy) and is extremely slow. The question then is how can we sandbox arbitrarily dangerous AIs without any computational assumptions.
I now give a solution to the problem, which was actually known for a long time but neglected by the AI safety community. The central idea is that Homomorphic Encryption is not the way to go if we want zero computational assumptions. Instead, we should use Secure Multi-Party Computation, which does not require any computational assumptions, and which is also orders of magnitude faster. More precisely, the solution was discovered independently in the 1980s by two groups of researchers (Michael Ben-Or, Shafi Goldwasser, Avi Wigderson; David Chaum, Claude Crépeau, Ivan Damgård).
Running Breeder 1 from the Game of Life via Secure Multi-Party Computation. Each iteration takes around 15 seconds to run, whereas the version without any cryptographic protocol takes around one second. Although Secure Multi-Party Computation is slower, it is slower only up to a multiplicative constant. With Fully Homomorphic Encryption, running grids of such size would be almost impossible.
Introduction
Formulating our objective
Homomorphic Encryption is a cryptographic scheme in which Alice encrypts her code, sends the encrypted version to Bob, and lets Bob run the code for her. When Bob runs the code, he doesn't and cannot learn anything about it from what Alice sent him. After that, Bob sends back the encrypted result of the code, and Alice then decrypts it to obtain the final result. The reason why this theoretically enables us to run arbitrarily dangerous AIs safely is stated as follows by Paul Christiano:
If you run a homomorphically encrypted AI, sufficiently isolated from the private key, you get the very strong guarantee that the AI's execution has no computationally detectable effect on the rest of the world. If the AI was able to effect the world in a computationally detectable way, then we would have successfully broken the homomorphic encryption scheme by distinguishing the encrypted execution of the AI from the encrypted execution of some benign program.
The reason why it is safe is that no one involved in the computation has any information whatsoever about the code itself. For illustrative purposes, suppose that the code is not written in a programming language like Python, but rather is embedded in a grid of Conway's Game of Life, and that Alice wants it to run for timesteps. Then, Alice and Bob can set up the scheme in such a way that the only thing that Bob learns is that it is a grid of the Game of Life that has to be run for timesteps[1]. From Bob's perspective, he would just run the rules of the Game of Life on a uniformly random grid for timesteps, which is extremely unlikely to be dangerous.
Our objective is therefore to be able to run any program (such as an arbitrarily dangerous AI) while making sure that no one involved in running the program learns any information whatsoever about the program itself, even in the case where they have infinite compute.
The problems of Homomorphic Encryption
However, Homomorphic Encryption has major problems, which left the problem unsolved:
They rely on computational assumptions, such as Learning With Errors. Computational assumptions are mathematical statements such as "There is no efficient algorithm (that is, algorithms that run in polynomial time) that solves the problem ." There are two consequences to this:
The information is still here but cannot be extracted efficiently: When Alice encrypts her code using Homomorphic Encryption, the information is still here in the encrypted code, but according to the computational assumption, there is no efficient algorithm to extract it. If we assume that Bob can only execute efficient algorithms, then he indeed cannot extract information. However, if Bob had access to infinite compute, he could run non-polynomial time algorithms and extract all the information of the code. In such cases, we say that Homomorphic Encryption does not provide information-theoretic security.
The computational assumption could be wrong, in which case the information can be extracted efficiently: Currently, we do not know how to prove statements such as "There is no polynomial-time algorithm that extracts information from the message , but the information can be extracted from if we know the secret key." Basically, the reason why we currently do not know how to prove such statements is because it would prove the conjecture ≟. Furthermore, if (which is considered to be extremely unlikely), then all such computational assumptions are wrong.
Homomorphic Encryption that can run every program (called Fully Homomorphic Encryption) runs slowly. We can make it faster by using Partially Homomorphic Encryption, which is specialized for a narrow set of operations. A trivial example is a Homomorphic Encryption scheme that allows addition but not multiplication. But this means that the program we run has to be conceived with the cryptographic protocol in mind. Due to the (lack of) speed of FHE, some people argued against cryptographic AI boxing.
To solve these three problems, I proposed in my first post that we could use a symmetric Quantum Fully Homomorphic Encryption protocol with perfect secrecy proposed by Min Liang. This would both remove any computational assumption and run efficiently, with the disadvantage that it would require a quantum computer. However, I showed in my second post that this protocol is actually flawed, and that we can extract information about the code[2]. I therefore went back to the drawing board with the problem still unsolved.
What is Secure Multi-Party Computation?
Note that, with Homomorphic Encryption, we encrypt the code and give it to a single person. Basically, in Secure Multi-Party Computation, we allow ourselves to give it to multiple people. Here is a definition of Secure Multi-Party Computation (MPC):
At the beginning, parties each have a private data (for instance a bit) and want to jointly compute a function without revealing their inputs to one another. To be more precise, by the end of the protocol, the group should have the ability to either reveal the value of or not do it. If they don't do it, each party should "learn nothing about each other's secrets," in the sense that each party's probability distribution about each secret should be unchanged. But if they do, each party should "learn only the result and what can be inferred from it," in the sense that their probability distributions about each secret should change just as if they each sent their secret data to a trusted third party, which computed the result for them and broadcast it back to everyone.
To solve the problem of Secure Multi-Party Computation, people came up with protocols with the following operations:
: when a party has a secret , they should be able to split this secret into pieces called shares, and share to the -th party. The shares, each taken independently, should not give any information about (even with infinite compute), but should together uniquely identify .
: for any function , when the shares of and are distributed to the parties in the way mentioned above, the parties should be able to collectively compute the shares of and distribute them in the way mentioned before without revealing any secret.
: the parties should be able to reveal the shares of , allowing everyone to reconstruct . Revealing a value should only reveal that value and what can be inferred from it.
To make it easier, let's assume that everyone is honest (that is, everyone follows the protocol), that everyone has access to their own randomness source, and that there are authenticated secrecy channels between each pair of participants (that is, any party can send a message to any other party without anyone else hearing, and the party that receives the message knows which party sent the message). Then, there are very efficient protocols implementing the three above operations that can evaluate every function , as long as there are at least parties. Furthermore, these are information-theoretically secure protocols, meaning that they do not require any computational assumptions and work against adversaries with infinite compute. These protocols are also extremely efficient, since the number of operations needed for evaluating with/without the protocol is the same up to a multiplicative constant. We will now see how such protocols solve our problem of running arbitrarily dangerous AIs safely.
Why does it solve our problem
Remember our objective: Our objective is to be able to run any program (such as an arbitrarily dangerous AI) while making sure that no one involved in running the program learns any information whatsoever about the program itself, even in the case where they have infinite compute. To do this, we will reduce this problem to the Secure Multi-Party Computation Problem, which has a solution.
Suppose that we have a Secure Multi-Party Computation protocol for people that implements , , and .
Suppose I have an interpreter that everyone knows (for instance a function which applies the rules of the Game of Life a million times) and a dangerous code (for instance a grid). My objective is to let Alice, Bob and Charlie compute my result for me without them learning anything about . In that case:
I execute to compute the shares of . This can be done extremely fast in constant time (that is, no matter whether we run the rules of the Game of Life once or a million times). I then send to Alice, to Bob, and to Charlie. None of them learn anything about from this.
Alice, Bob, and Charlie then execute in order to obtain the shares of . Running may be slower than running , but only up to a multiplicative constant[3]. They still did not learn anything about from this. Alice, Bob, and Charlie then send back the shares of to me.
I then execute in order to get back . This also can be done extremely fast in constant time.
In that way, I get the result of while having done almost nothing (the part does all the job and does not require any interaction with me) and while ensuring that I am the only one knowing anything about the program . This solves our problem! The other three people, that is, Alice, Bob, and Charlie, did not get any information whatsoever about the code. From their perspective, they are just running the interpreter on a random sequence of bits. If their computer were to, for instance, blow up because my code is dangerous, they would obtain information about my code from that observation, which is impossible. Therefore, their computer cannot blow up because of my dangerous code.
When looking at Alice's computer and secrecy channels (left), we cannot infer anything about the program . Therefore, nothing dangerous can occur here due to the program , since if something dangerous were to occur here due to , it would give information about , which contradicts the protocol. Similarly, when looking at Bob's computer and secrecy channels (center), we cannot infer anything about , and therefore cannot have any visible effect here. Finally, when looking at Charlie's computer and secrecy channels (right), we cannot infer anything about , and therefore cannot have any observable impact here.
How does the solution to the Secure Multi-Party Computation problem work
Now that we have seen how some Secure Multi-Party Computation protocols can solve our problem, let's try to see how these schemes work and can be implemented. As stated previously, at the beginning of Secure Multi-Party Computation, there were two such protocols discovered independently. In the remainder of this post, I will focus only on one of these protocols (the one by David Chaum, Claude Crépeau, and Ivan Damgård).
Why does addition enable us to encrypt and decrypt messages?
Suppose I have a secret bit , that I generate a random bit using a fair coin toss, and that I compute the XOR between the two, that is, . As a reminder, the XOR operator returns 1 if and only if exactly one of the two bits is equal to 1. You can also visualize it as an operator that, if equals 0, outputs without modifying it, and otherwise flips before outputting it. Then, suppose I send to Alice and to Bob. Now, there are two questions:
Does Bob gain any information about from receiving ? The answer is no, because is simply the result of a coin toss that is independent from the value of . This was the easy case.
Does Alice gain any information about from receiving ? This answer is a little bit trickier. You may at first believe that the answer is yes, because the value of is partially determined by , as we can see in the formula . However, the true answer is no. We can show that our beliefs about after having seen , that is, , are the same than our beliefs about before having seen , that is, . This property is called Shannon's perfect secrecy.
In other words, when XORing a secret bit (called the plaintext) with a uniformly random bit of same length (called the key) generated from a fair coin toss, the result (called the ciphertext) does not contain any information about as long as we don't know about the value of the key , no matter how much compute you have. However, when you have the key , you can trivially find back the original secret from the ciphertext by XORing it with the key once again:
In other words, we can encrypt a message into an encrypted version (via a key generated uniformly randomly) by computing . This encrypted result, called the ciphertext, does not contain any information about the plaintext when we do not know anything about the key . We can then decrypt the ciphertext to obtain back the value of by computing . This is called the One-Time pad.
This works in the binary case with the XOR operator, but it can actually be generalized further. Remember that XOR is just addition modulo 2 (that is, addition where the only numbers we have are 0 and 1, and where after 1, we loop back to zero). This property can be generalized to addition modulo , where the key is a number taken uniformly randomly from the set . In fact, this property can be generalized even more to include every finite group, as long as the key is taken uniformly randomly from . In that case, the encryption is and the decryption is [4].
Why sharing points of polynomials enable us to and secrets?
Suppose we have a finite field[5]. For illustrative purposes, let's consider the real field with the classical addition and multiplication, but keep in mind that in practice, the field has to be finite. Also, suppose I am being told that someone generated a polynomial of degree uniformly randomly[6], that is, a line .
The polynomial with and
Now, the question is, how many distinct points do I need to uniquely identify this polynomial? The answer is two:
We need exactly two points in order to uniquely identify the line. A single point is not enough.
More generally, if a polynomial of degree has been generated uniformly randomly, I need exactly points in order to uniquely identify the polynomial.
For a polynomial of degree , that is, , we need exactly points in order to uniquely identify it.
Now, suppose once again that I know that a polynomial of degree has been generated uniformly randomly. Let's focus on the -intercept of the polynomial, that is, the value of the polynomial at . If I am given strictly less than distinct points with , I do not get any new information about the value of . However, if I am given distinct points, I can uniquely identify and therefore compute .
For a polynomial of degree generated uniformly randomly, I need exactly two points with in order to figure out the value of . With only a single point, I do not learn anything about .
This will enable us to share a secret to multiple people. Suppose Alice has a secret . Then, she can generate a polynomial of degree such that:
Its -intercept, that is, , is equal to her secret .
The other coefficients of the polynomial, that is, , have been generated uniformly randomly.
Then, she can keep , send to Bob, and send to Charlie. In that way, Bob and Charlie do not gain any information about . But if the two of them meet, they can share their knowledge and uniquely identify and therefore compute .
How to the sum between two secrets?
We have seen that, to share a secret to multiple people, Alice can generate a polynomial of degree uniformly randomly with a -intercept equal to , keep , share to Bob, and share to Charlie.
Similarly, if Bob also has a secret . He can generate a polynomial of degree uniformly randomly with a -intercept equal to , send to Alice, keep , and send to Charlie.
And if Charlie has a secret , they can generate a polynomial of degree uniformly randomly with a -intercept equal to , send to Alice, send to Bob, and keep .
We end up in a scenario where Alice owns , , and , Bob owns , , and , and Charlie owns , , and . No one has learned any information about the secret of the others.
Alice has a secret and therefore generated a polynomial whose -intercept is 1. Similarly, Bob has a secret and generated a polynomial whose -intercept is 1.5. And Charlie has a secret and generated a polynomial whose -intercept is 2. Alice knows the points at , Bob knows the points at , and Charlie knows the points at .
But now, suppose that Alice, Bob and Charlie want to compute a sum between two of their secrets[7], such as , without revealing them. To do so, Alice will compute , Bob will compute , and Charlie will compute . They therefore each have one point of the polynomial
Alice obtains (the upper-left point). Similarly, Bob obtains (the upper-center point), and Charlie obtains (the upper-right point). These points lie on the polynomial .
Note that, when adding polynomials together, the -intercepts add together. Therefore, this new polynomial has as a intercept the value :
Now, if they want to decrypt/reveal the result of , they can meet together, share their points for the polynomial to uniquely identify it, and deduce the -intercept . In that way, they managed to compute without sharing their secret.
If Alice, Bob and Charlie share their points on the upper blue line, they can uniquely identify it and compute the -intercept. Note that the -intercept of the upper blue line is equal to 2.5, which is exactly the sum of Alice's and Bob's secrets (1+1.5).
How to the product between two secrets?
Suppose that this time, Alice, Bob, and Charlie want to compute the sum between two of their secrets, such as . Then, they can do the exact same process, except that they multiply their values rather than adding them:
Alice creates a polynomial of degree with a -intercept equal to , keep , share to Bob, and share to Charlie.
Bob creates a polynomial of degree with a -intercept equal to , share to Alice, keep , and share to Charlie.
Alice therefore has and , Bob has and , and Charlie has and .
Alice computes , Bob computes , and Charlie computes .
Now, if they want to decrypt/reveal , they can share these three values, deduce the polynomial , and compute its -intercept, which will be equal to:
However, we can see that there is one problem left. This time, when multiplying the points together rather than adding them, we obtained a polynomial of degree rather than . This is because, even though adding a polynomial of degree with a polynomial of degree gives a polynomial of degree , multiplying a polynomial of degree with a polynomial of degree gives a polynomial of degree :
Multiplying two polynomials of degree 1 gives a polynomial of degree 2. The upper blue curve is not a line but a parabola.
This causes problems since, if we do multiple multiplications, the degree of the polynomial will increase fast and we will eventually not have enough points to deduce its -intercept. To solve this, we need to "transform" this polynomial of degree back to a polynomial of degree .
To do so, Alice, Bob, and Charlie firstly need to generate a polynomial of degree whose -intercept is unknown to everyone. To do so, Alice, Bob, and Charlie each generate a degree uniformly randomly (respectively the polynomials , , and ). Then, Alice obtains , , and , Bob obtains , , and , and Charlie obtains , , and . After this, Alice computes , Bob computes , and Charlie computes . In this way, they each have one point of the polynomial . Note that none of them know the -intercept of this polynomial.
Then, this unknown -intercept will now serve as a "secret random key" which will be used to hide from everyone. To do so, they will compute the sum between this polynomial and the quadratic polynomial . In other words:
Alice computes the sum between and . Bob computes the sum between and . Charlie computes the sum between and .
They meet together and reveal these three points. They therefore uniquely identify the polynomial . They compute the -intercept of this polynomial, which is
They therefore know the value , which does not leak the value of because no one knows the value of . Now:
Alice, Bob and Charlie respectively create a polynomial , , and of degree which respectively have the same -intercept as , , and . Then, Alice obtains , , and , Bob obtains , , and , and Charlie obtains , , and . After this, Alice computes , Bob computes , and Charlie computes . They therefore each have a point of the polynomial . Note that the -intercept of is the same as the -intercept of .
Finally, Alice computes , Bob computes , and Charlie computes . Note that the -intercept of this polynomial is:
In other words, Alice, Bob and Charlie managed, from their polynomial of degree whose -intercept was , to obtain a polynomial of degree with the same -intercept. This solves the problem of the degree increasing.
Now, if they want to decrypt/reveal the value of , they just need to meet and share the values , , and , and deduce the -intercept.
Why does this enable us to run any boolean function?
Now that, for any finite field, we can add and multiply secrets together as many times as we want and in the order we want, how can we run any program? Note that, in fields of two elements (called for Galois Field), addition is equivalent to the XOR and multiplication is equivalent to the AND. Since we also have constants like 0 and 1, this becomes functionally complete, meaning that we can run any boolean function we want!
However, note that, in our scheme, the finite field requires at least four elements. Indeed, since we need at least three people (Alice, Bob and Charlie) to which we attribute to them a distinct value different than zero (for instance for Alice, for Bob, and for Charlie), and that we also need a zero, we need at least four distinct values. So, we cannot use .
But this is not problematic at all. Instead, we can use a bigger field whose number of elements is a power of 2. The easiest one is . Note that is not normal addition and multiplication modulo 4 (this would be , which is not a field). Rather, the four elements are not called , , , and , but are instead called , , , and . The addition table in this field is the same as the subtraction table, which is as follows:
y
x
0
1
α
1 + α
0
0
1
α
1 + α
1
1
0
1 + α
α
α
α
1 + α
0
1
1 + α
1 + α
α
1
0
And the multiplication table is as follows:
y
x
0
1
α
1 + α
0
0
0
0
0
1
0
1
α
1 + α
α
0
α
1 + α
1
1 + α
0
1 + α
1
α
To implement addition and multiplication in in Python, we can just store the lookup tables. However, note that, if our binary representation of is , then addition in can be implemented by just using the bitwise XOR rather than using a lookup table.
Proof of concept: Cellular automata
To prove that the protocol works, I implemented it and programmed Rule 60 (which uses only XOR gates), Rule 110 (which is Turing complete and uses both XOR and AND gates), and the Game of Life (which is Turing complete and uses both XOR and AND gates). The code can be found here.
Running Rule 60 on a tape of 256 cells via Secure Multi-Party Computation. Since Rule 60 does not use AND gates, this doesn't require any communication between Alice, Bob, and Charlie, and therefore runs extremely fast, with around 21,000 iterations per second when using PyPy.
Running Rule 110 on a tape of 256 cells via Secure Multi-Party Computation. This runs at around 1600 iterations per second when using PyPy.
Running Breeder 1 from the Game of Life via Secure Multi-Party Computation. Each iteration takes around 15 seconds to run, whereas the version without any cryptographic protocol takes around one second. Although Secure Multi-Party Computation is slower, it is slower only up to a multiplicative constant. With Fully Homomorphic Encryption, running grids of such size would be almost impossible.
Problem - The distance between the three computers
In my Python implementation of the protocol, the shares of Alice, Bob, and Charlie are stored very close to each other (although they are in different lists). In practice, we would want Alice, Bob, and Charlie's computers to be far away from each other in order to avoid any covert channel accidentally leaking these shares.
How far away should they be? We know that some covert channels have been confirmed to go as far away as 87.5 meters, and some others are suspected to go hundreds of meters away. Personally, I would recommend to put the computers at least one kilometer away from each other in order to prevent any covert channel, although this may not be sufficient.
The downside of doing so is that the necessary communication needed to evaluate AND gates will be slowed down. If we have two computers at the opposite side of the Earth at the level of the equator, they will be separated by 12,756 kilometers. Since the speed of light is by definition 299,792,458 meters per second, then sending a message from one computer to the other would take approximately 0.05 seconds. Waiting for that long for every AND gate would make the protocol way too slow. Even a single kilometer adds approximately 0,0000033 seconds, which may be too slow. Despite this, keeping a large distance between the three computers should be a priority if we run dangerous AIs.
Note that this delay problem does not arise in Homomorphic Encryption, which doesn't require communication, except at the very beginning and end.
To reduce the risks of covert channels, I would also recommend air-gapping the computers of Alice, Bob, and Charlie. Air-gapping consists of physically isolating the computers from other networks. We should also put each computer inside its own Faraday cage, which are cages designed in order to block electromagnetic fields. However, note that air-gapped computers, including those inside Faraday cages, are not robust against covert channels[8]. We should also attempt to use signal jammers in order to prevent covert channels. Another way to reduce the risks of covert channels is to put the computers underground, like the data centers at Pionen, which are deep below 30 meters of granite and secured by a 40-centimeter thick door. Another possibility, mentioned by Paul Christiano in his post, may be to use quantum computers.
Appendix 1 - Why do we need at least three parties?
A function is said to be -private when there is a protocol where parties, each holding a value , can compute , and no subset of or fewer parties gains any information other than what can be deduced from .
We want to know which functions are 1-private, that is, which functions have a protocol where no single party can gain any information they shouldn't.
Case
For , for any finite sets , and , any function is 1-private. Indeed, we just need to encode the values of , and inside a single finite field of at least elements, and then use the protocol we saw in this post. Now, the question is, what happens when ?
Case
In the article Perfect Privacy for Two-Party Protocols, where , the authors show that, for any finite sets , and , a function is 1-private if and only if it is partitionable. To get an intuition of what partitionable functions are, consider the 2D table of :
For any partition and of the rows, we say that is row-separable into and when, for each column, there is no value appearing both in and in .
For any partition and of the columns, we say that is column-separable into and when, for each row, there is no value appearing both in and in .
Finally, we say that is partitionable when either is constant, or is row-separable or column-separable into and , which must themselves be partitionable (this definition is recursive).
This is a bit hard to interpret. We therefore wonder, what happens in the case where the function's output type is a boolean?
Case , with boolean outputs
In the article A Zero-One Law for Boolean Privacy, the authors show that, for any finite sets , a function that returns a boolean is -private if and only if:
where . In the case where , we obtain that any function is 1-private if and only if:
This is still a bit hard to interpret. We therefore wonder, what happens if both the inputs and outputs are boolean?
Case , with boolean inputs and outputs
In that case, the previous equation becomes:
with . This is the set of affine boolean functions, which, according to Post's lattice, is the set of boolean functions that can be built from the constant and the XOR gate. Note that this excludes the AND gate. Therefore, with computers, we cannot run every boolean function. Furthermore, no affine system, such as affine cellular automata, is known to be Turing complete. If you want to try to find one, I made a list of universal cellular automata to search for an affine one.
Appendix 2 - Having more than three parties helps if a group of them leak everything to each other
Intuitively, a function is -private when, if there is a group of parties or less that illegally or accidentally communicate everything to each other, they still cannot infer things they shouldn't when running the protocol.
With parties, having a group of parties that leak everything to each other is therefore still fine. In other words, adding more parties makes it harder for groups of parties to illegally or accidentally extract information.
Even better, if Alice adds padding to the grid, then Bob only needs to learn an upper bound for the size of the grid, which can be fixed to extremely high values in advance to minimize the amount of information learned. Furthermore, if Alice is even more careful, she can make sure that the result of timestep that she cares about gets stored somewhere in a register embedded in the grid, and in that case, if Bob runs the grid for longer than expected, Alice can still get the result. In that way, Bob only needs to learn an upper bound of , which can also be set to an extremely high value in advance.
I sent emails about the flaw to the author of the protocol, but I didn't get an answer to confirm it. If you find an error in my previous post, please contact me.
As we will see later, a single XOR gate gets converted into a fixed number of gates. Similarly for the AND gate. Therefore, the number of gates of the initial circuit is equal up to a constant to the number of gates in .
Note that, when is a finite field, then is a finite group, and therefore we can use the One-Time pad mentioned in the previous section using this addition operator.
By "polynomial of degree generated uniformly randomly," we mean a polynomial whose coefficients have been picked uniformly randomly from its field . In the case of infinite fields such as the real field , this is impossible, because we cannot pick a real number uniformly randomly. This is the reason why, in practice, we will have to work in a finite field, where selecting an element uniformly randomly is possible.
For Faraday cages, see for instance MAGNETO and ODINI, and for air-gapped systems in general, see the other publications of Mordechai Guri. This researcher is probably the world's most prolific researcher specializing in covert channels for air-gapped computers, and even created the Air Gap Research Page.
Summary
In 2010, Paul Christiano wrote Cryptographic Boxes for Unfriendly AI, in which he asks how we can sandbox arbitrarily dangerous AIs and recommends Homomorphic Encryption as a potential solution. However, Homomorphic Encryption relies on computational assumptions (it does not provide perfect secrecy) and is extremely slow. The question then is how can we sandbox arbitrarily dangerous AIs without any computational assumptions.
I now give a solution to the problem, which was actually known for a long time but neglected by the AI safety community. The central idea is that Homomorphic Encryption is not the way to go if we want zero computational assumptions. Instead, we should use Secure Multi-Party Computation, which does not require any computational assumptions, and which is also orders of magnitude faster. More precisely, the solution was discovered independently in the 1980s by two groups of researchers (Michael Ben-Or, Shafi Goldwasser, Avi Wigderson; David Chaum, Claude Crépeau, Ivan Damgård).
Running Breeder 1 from the Game of Life via Secure Multi-Party Computation. Each iteration takes around 15 seconds to run, whereas the version without any cryptographic protocol takes around one second. Although Secure Multi-Party Computation is slower, it is slower only up to a multiplicative constant. With Fully Homomorphic Encryption, running grids of such size would be almost impossible.
Introduction
Formulating our objective
Homomorphic Encryption is a cryptographic scheme in which Alice encrypts her code, sends the encrypted version to Bob, and lets Bob run the code for her. When Bob runs the code, he doesn't and cannot learn anything about it from what Alice sent him. After that, Bob sends back the encrypted result of the code, and Alice then decrypts it to obtain the final result. The reason why this theoretically enables us to run arbitrarily dangerous AIs safely is stated as follows by Paul Christiano:
The reason why it is safe is that no one involved in the computation has any information whatsoever about the code itself. For illustrative purposes, suppose that the code is not written in a programming language like Python, but rather is embedded in a
Our objective is therefore to be able to run any program (such as an arbitrarily dangerous AI) while making sure that no one involved in running the program learns any information whatsoever about the program itself, even in the case where they have infinite compute.
The problems of Homomorphic Encryption
However, Homomorphic Encryption has major problems, which left the problem unsolved:
To solve these three problems, I proposed in my first post that we could use a symmetric Quantum Fully Homomorphic Encryption protocol with perfect secrecy proposed by Min Liang. This would both remove any computational assumption and run efficiently, with the disadvantage that it would require a quantum computer. However, I showed in my second post that this protocol is actually flawed, and that we can extract information about the code[2]. I therefore went back to the drawing board with the problem still unsolved.
What is Secure Multi-Party Computation?
Note that, with Homomorphic Encryption, we encrypt the code and give it to a single person. Basically, in Secure Multi-Party Computation, we allow ourselves to give it to multiple people. Here is a definition of Secure Multi-Party Computation (MPC):
To solve the problem of Secure Multi-Party Computation, people came up with protocols with the following operations:
To make it easier, let's assume that everyone is honest (that is, everyone follows the protocol), that everyone has access to their own randomness source, and that there are authenticated secrecy channels between each pair of participants (that is, any party can send a message to any other party without anyone else hearing, and the party that receives the message knows which party sent the message). Then, there are very efficient protocols implementing the three above operations that can evaluate every function
Why does it solve our problem
Remember our objective: Our objective is to be able to run any program (such as an arbitrarily dangerous AI) while making sure that no one involved in running the program learns any information whatsoever about the program itself, even in the case where they have infinite compute. To do this, we will reduce this problem to the Secure Multi-Party Computation Problem, which has a solution.
Suppose that we have a Secure Multi-Party Computation protocol for
Suppose I have an interpreter
In that way, I get the result of
When looking at Alice's computer and secrecy channels (left), we cannot infer anything about the program
How does the solution to the Secure Multi-Party Computation problem work
Now that we have seen how some Secure Multi-Party Computation protocols can solve our problem, let's try to see how these schemes work and can be implemented. As stated previously, at the beginning of Secure Multi-Party Computation, there were two such protocols discovered independently. In the remainder of this post, I will focus only on one of these protocols (the one by David Chaum, Claude Crépeau, and Ivan Damgård).
Why does addition enable us to encrypt and decrypt messages?
Suppose I have a secret bit
In other words, when XORing a secret bit
In other words, we can encrypt a message
This works in the binary case with the XOR operator, but it can actually be generalized further. Remember that XOR is just addition modulo 2 (that is, addition where the only numbers we have are 0 and 1, and where after 1, we loop back to zero). This property can be generalized to addition modulo
Why sharing points of polynomials enable us to
Suppose we have a finite field
The polynomial
Now, the question is, how many distinct points do I need to uniquely identify this polynomial? The answer is two:
We need exactly two points in order to uniquely identify the line. A single point is not enough.
More generally, if a polynomial of degree
For a polynomial of degree
Now, suppose once again that I know that a polynomial
For a polynomial
This will enable us to share a secret to multiple people. Suppose Alice has a secret
Then, she can keep
How to
We have seen that, to share a secret
Similarly, if Bob also has a secret
And if Charlie has a secret
We end up in a scenario where Alice owns
Alice has a secret
But now, suppose that Alice, Bob and Charlie want to compute a sum between two of their secrets[7], such as
Alice obtains
Note that, when adding polynomials together, the
Now, if they want to decrypt/reveal the result of
If Alice, Bob and Charlie share their points on the upper blue line, they can uniquely identify it and compute the
How to
Suppose that this time, Alice, Bob, and Charlie want to compute the sum between two of their secrets, such as
However, we can see that there is one problem left. This time, when multiplying the points together rather than adding them, we obtained a polynomial of degree
Multiplying two polynomials of degree 1 gives a polynomial of degree 2. The upper blue curve is not a line but a parabola.
This causes problems since, if we do multiple multiplications, the degree of the polynomial will increase fast and we will eventually not have enough points to deduce its
To do so, Alice, Bob, and Charlie firstly need to generate a polynomial
Then, this unknown
They therefore know the value
In other words, Alice, Bob and Charlie managed, from their polynomial of degree
Now, if they want to decrypt/reveal the value of
Why does this enable us to run any boolean function?
Now that, for any finite field, we can add and multiply secrets together as many times as we want and in the order we want, how can we run any program? Note that, in fields of two elements (called
However, note that, in our scheme, the finite field requires at least four elements. Indeed, since we need at least three people (Alice, Bob and Charlie) to which we attribute to them a distinct
But this is not problematic at all. Instead, we can use a bigger field whose number of elements is a power of 2. The easiest one is
y
x
0
1
α
1 + α
0
0
1
α
1 + α
1
1
0
1 + α
α
α
α
1 + α
0
1
1 + α
1 + α
α
1
0
And the multiplication table is as follows:
y
x
0
1
α
1 + α
0
0
0
0
0
1
0
1
α
1 + α
α
0
α
1 + α
1
1 + α
0
1 + α
1
α
To implement addition and multiplication in
Proof of concept: Cellular automata
To prove that the protocol works, I implemented it and programmed Rule 60 (which uses only XOR gates), Rule 110 (which is Turing complete and uses both XOR and AND gates), and the Game of Life (which is Turing complete and uses both XOR and AND gates). The code can be found here.
Running Rule 60 on a tape of 256 cells via Secure Multi-Party Computation. Since Rule 60 does not use AND gates, this doesn't require any communication between Alice, Bob, and Charlie, and therefore runs extremely fast, with around 21,000 iterations per second when using PyPy.
Running Rule 110 on a tape of 256 cells via Secure Multi-Party Computation. This runs at around 1600 iterations per second when using PyPy.
Running Breeder 1 from the Game of Life via Secure Multi-Party Computation. Each iteration takes around 15 seconds to run, whereas the version without any cryptographic protocol takes around one second. Although Secure Multi-Party Computation is slower, it is slower only up to a multiplicative constant. With Fully Homomorphic Encryption, running grids of such size would be almost impossible.
Problem - The distance between the three computers
In my Python implementation of the protocol, the shares of Alice, Bob, and Charlie are stored very close to each other (although they are in different lists). In practice, we would want Alice, Bob, and Charlie's computers to be far away from each other in order to avoid any covert channel accidentally leaking these shares.
How far away should they be? We know that some covert channels have been confirmed to go as far away as 87.5 meters, and some others are suspected to go hundreds of meters away. Personally, I would recommend to put the computers at least one kilometer away from each other in order to prevent any covert channel, although this may not be sufficient.
The downside of doing so is that the necessary communication needed to evaluate AND gates will be slowed down. If we have two computers at the opposite side of the Earth at the level of the equator, they will be separated by 12,756 kilometers. Since the speed of light is by definition 299,792,458 meters per second, then sending a message from one computer to the other would take approximately 0.05 seconds. Waiting for that long for every AND gate would make the protocol way too slow. Even a single kilometer adds approximately 0,0000033 seconds, which may be too slow. Despite this, keeping a large distance between the three computers should be a priority if we run dangerous AIs.
Note that this delay problem does not arise in Homomorphic Encryption, which doesn't require communication, except at the very beginning and end.
To reduce the risks of covert channels, I would also recommend air-gapping the computers of Alice, Bob, and Charlie. Air-gapping consists of physically isolating the computers from other networks. We should also put each computer inside its own Faraday cage, which are cages designed in order to block electromagnetic fields. However, note that air-gapped computers, including those inside Faraday cages, are not robust against covert channels[8]. We should also attempt to use signal jammers in order to prevent covert channels. Another way to reduce the risks of covert channels is to put the computers underground, like the data centers at Pionen, which are deep below 30 meters of granite and secured by a 40-centimeter thick door. Another possibility, mentioned by Paul Christiano in his post, may be to use quantum computers.
Appendix 1 - Why do we need at least three parties?
A function
We want to know which functions are 1-private, that is, which functions have a protocol where no single party can gain any information they shouldn't.
Case
For
Case
In the article Perfect Privacy for Two-Party Protocols, where
This is a bit hard to interpret. We therefore wonder, what happens in the case where the function's output type is a boolean?
Case
In the article A Zero-One Law for Boolean Privacy, the authors show that, for any finite sets
where
This is still a bit hard to interpret. We therefore wonder, what happens if both the inputs and outputs are boolean?
Case
In that case, the previous equation becomes:
with
Appendix 2 - Having more than three parties helps if a group of them leak everything to each other
Intuitively, a function is
In the article A Zero-One Law for Secure Multi-Party Computation with Ternary Outputs, they show that, for every finite function
With
Even better, if Alice adds padding to the grid, then Bob only needs to learn an upper bound for the size of the grid, which can be fixed to extremely high values in advance to minimize the amount of information learned. Furthermore, if Alice is even more careful, she can make sure that the result of timestep
I sent emails about the flaw to the author of the protocol, but I didn't get an answer to confirm it. If you find an error in my previous post, please contact me.
As we will see later, a single XOR gate gets converted into a fixed number of gates. Similarly for the AND gate. Therefore, the number of gates of the initial circuit is equal up to a constant to the number of gates in
When working in binary (modulo 2), the + and - symbols play the same role, which is the role of XOR.
Note that, when
By "polynomial of degree
If they want to compute the sum between more than two secrets, they can just repeat this multiple times.
For Faraday cages, see for instance MAGNETO and ODINI, and for air-gapped systems in general, see the other publications of Mordechai Guri. This researcher is probably the world's most prolific researcher specializing in covert channels for air-gapped computers, and even created the Air Gap Research Page.