Concrete Boolean and Conway’s Game of Life: A Tutorial
A guest article by Optalysys on implementing Conway’s Game of Life using homomorphic encryption
With Florent Michel, Joseph Wilson and Edward Cottle.
Fully Homomorphic Encryption is a remarkably powerful cryptographic technique that allows computation on encrypted data.
However, cryptography can be a difficult subject. Data is valuable and computers are complex machines; attacks on encrypted data rarely focus on the underlying mathematics of the cryptosystem, but instead target the practical implementation. Ensuring that cryptographic applications are secure requires expert oversight.
FHE is powerful because it allows for secure computation, but to achieve the full potential of what it offers it has to be accessible to everyone who has a use-case for it. Tools are needed to make it possible for non-specialists to safely implement the next generation of encrypted processing applications. This is what Zama have done with their Concrete Library, and we (Optalysys) are here to demonstrate that.
We’re a company developing a new kind of optical computing hardware, one that has tremendous promise for addressing the computational overhead of FHE. What we aren’t are specialists in the development of cryptographic libraries. However, Concrete is so user-friendly that we’ve not only been able to implement relatively complex FHE applications, but also test them out on our novel hardware concept. More than that, we’ve been able to do this quickly; the example we’re going to show here only took between 3–4 hours to develop.
In less than a month since the release of Concrete-Boolean, we’ve been able to develop multiple very different FHE applications of varying complexity. We’re currently in the process of writing articles on these too (which takes much longer than the actual development), but when we say that Concrete-Boolean is a groundbreaking advance for both end-users and FHE as a field, we mean it.
The first of the test applications we created was a classic simulation known as Conway’s Game of Life, carried out entirely in encrypted space. We’ve released our own article on how we executed this task using a combination of our optical computing system and Concrete, but here we’ve turned that article into a tutorial focused on Concrete Boolean itself.
Introduction to the Game of Life
When developing any application, we first need an understanding of what it is that we want to achieve. In this case, we want to implement Conway’s Game of Life through encrypted Boolean operations.
The Game of Life is an example of a cellular automaton, a simulation with simple rules from which complex behaviours can emerge. It is “played” on a 2-dimensional square grid. The size of this grid isn’t fixed; it can be any size, as long as you have sufficient computing memory. Each cell within this grid can be in one of two states, “alive” or “dead”, and each cell has 8 neighbours (including ones at the edge if the boundaries are treated as periodic). The system evolves over discrete update intervals according to the following rules:
- Birth: A dead cell with three (no more, no less) live neighbours becomes live on the next iteration.
- Survival: A live cell with two or three live neighbours lives on to the next iteration
- Death: A live cell with less than two or more than three live neighbours dies on the next iteration.
While simple, these rules can give rise to complex and unexpected behaviours as the system evolves in time. For example, dynamic-but-stable configurations like the one shown below, which moves through the grid in repeating patterns.
Boolean construction
Concrete Boolean provides us with a way to directly implement the majority of unary or binary boolean gate operations on ciphertexts with a single line of code, so we start by constructing boolean algorithms for the Game of Life.
Since each cell can be in either one of two states (‘alive’ or ‘dead’), the state of any cell may be represented by a single Boolean variable. We use ‘True’ to indicate that a cell is alive, and ‘False’ for dead.
After an update, a given cell is alive if and only if one of these two conditions is true:
- It was already alive and had 2 or 3 neighbours.
- It was dead and had exactly 3 neighbours.
If the variable alive(i) denotes the state of the cell and neighbours(i) its number of neighbours after i iterations, then the state of the cell after i+1 iterations can be written in a boolean way as:
alive(i+1) = (alive(i) AND (neighbours(i) = 3 OR neighbours(i) = 2)) OR (NOT(alive(i)) AND neighbours(i) = 3)
which can be simplified to:
alive(i+1) = (neighbours(i) = 3) OR (alive(i) AND neighbours(i) = 2).
This is our update algorithm; we can apply it to each cell on each iteration and the system will evolve according to the rules. However, as part of this algorithm we need to be able to calculate the number of living neighbours each cell has.
Without encryption, this is straightforward: for each cell, we can just sum the states of the 8 neighbours, with ‘true’ counting for 1 and ‘false’ for 0. This is also technically possible in FHE: given ciphers corresponding to some numbers, summing them (at least under TFHE; other schemes may require more complex operations) will give you a cipher containing their sum. However, there is no similarly easy way to compare the result against the values 2 and 3 without decrypting it. While this is certainly possible using a combination of gate operations and programmable bootstrapping, we’ll give a simpler solution using only the former.
Additions, like any other computable operations, can be evaluated using boolean circuits. For instance, if b1 and b2 are individual bits, their sum can be expressed as the two-bit number c1 c2 where
c1 = b1 AND b2
and
c2 = b1 XOR b2
In our case, since each cell has 8 neighbours, the sum of their states can be encoded in a 4-bit number (we’ll see later that this can actually be reduced to 3 bits). We can use the Boolean addition method to calculate this number for any given cell; this is the central principle through which we can begin building our algorithm for calculating the number of living neighbours.
The problem of determining the number of neighbours for a cell can now be reduced to the following steps:
- Design an accumulator circuit which can sum up to 8 bits (sequentially), with a 4-bit output.
- Use it to compute the number of neighbours of each cell and plug it into the formula used to update its state.
- Convert the circuit to work on encrypted data using Concrete-boolean.
That’s the core logic completed. We’ll now show how to use the concrete-boolean library to implement a homomorphic version of Conway’s Game of Life. In the following sections, we will write some code to:
- Define and encrypt the initial state of the board,
- Update the board homomorphically without decrypting anything,
- Decrypt and print the result.
This step by step guide shows how to write a simple single-threaded version of our example code which prints the output in the terminal. For more advanced users who want to see how this works with multiple processing threads, a multithreaded version with a basic graphical interface can be found here.
In this tutorial, we will assume you have a Rust compiler (it should work with any version of rustc from 1.51) and Cargo installed. Instructions on how to install them can be found on the rust-lang website.
Note: The implementation below was designed to be relatively simple, and is not optimised for speed. It is possible to further simplify the boolean circuits, although these tricks are beyond the scope of the tutorial. Remember, every operation counts in FHE, so it’s worth taking the time to optimise.
Set-up
The first thing we need to do is create a new cargo project using Rust. We can do this using the terminal command cargo new homomorphic_game_of_life.
Using this command will create a folder labelledhomomorphic_game_of_life. Inside this folder will be a new folder calledsrc.
The only dependency (apart from Rust’s standard library) is concrete-boolean. To use the code shown in this tutorial, you'll need to add concrete-boolean = "0.1" to the dependencies section of the Cargo.toml file, which will look like
Create a new file labelledlib.rs in the src folder that contains the line:
This will place the traits and functions from concrete-boolean in the current namespace, and also allow their use inmain.rs(wich we will write later). Unless stated otherwise, the next pieces of code should also go in lib.rs.
(What we’re doing here inlib.rs is creating a new library of functions that we can call upon when we execute the main section of our code, the part that establishes the initial starting conditions for the grid and then applies the core algorithm over subsequent iterations. These functions are specific to this application and implement the boolean algorithms that we described in the last section.)
Accumulator
We begin by writing an accumulator which will be used to add the states of the neighbours of each cell, with the state ‘alive’ interpreted as 1 and ‘dead’ as 0.
The function add_1 uses Concrete-Boolean operations to homomorphically add the contents of a ciphertext a (which encodes a boolean value) to a triplet b that encodes three boolean values.
The triplet b is the accumulator for the central cell; adding a ciphertext a containing a True (encryption of the value “1") boolean value to the accumulator will cause the binary value stored by the accumulator to increment by 1
We use a 3-bit accumulator, which means that we can count from 0 to 7. A cell can have 8 neighbours, but we do not need to distinguish between the values 8 and 0 since these both lead to the same state for the cell after the update. A 3-bit accumulator is enough, and it means we can cut down on additional complexity.
We then call this accumulator in our next function to compute the sum of a sequence of ciphertexts modulo 8 (i.e., where 8 and 0 are identified with one another).
This function takes three arguments: server_key, of type ServerKey (we will explain why this is needed later; for now, we’ll just say that it’s an essential part of performing homomorphic operations), elements, an array of ciphertexts, and zeros, and a triplet of encryptions of false (which may be identical). This function assumes the array elements is not empty and will panic if it is; we could easily change this by replacing it with
However, in our case, we know that elements will always be of length 8, so the original function sum will do.
Checking if a cell is alive after the update
We now have the tools we need to perform an encrypted computation of the state of each cell after one update using the following method:
Given an array containing the ciphertexts for the boolean states of its neighbours, we can add them together using oursumfunction, check if the output is 2 or 3, and determine the new state of the cell as follows:
- if the sum is 2 or 3 and the cell is alive, it stays alive,
- if the sum is 3 and the cell is dead, it becomes alive,
- otherwise, the cell is dead after the update.
And that’s all! Well, at least as long as the core logic is concerned. We still need to define a Board structure which will store the states of the cells and a way to print it. But this can be achieved using more standard Rust.
The Board
We now need to define the structure of the board and the operations that can be applied to it. In Rust, we can use astructto create the board. This is somewhat similar to a class in Python, although the usual conceptual caveats when translating ideas between languages apply.
We use periodic boundary conditions for the edges of the board, so that each cell has exactly 8 neighbours. In the following code, the function new creates a new board from a number of columns and a vector of ciphertexts defining the initial state (the number of rows is inferred from the vector length). This function assumes that the length of the vector is a multiple of n_cols. (Updating the board will panic if that is not the case; here we aim at keeping the code simple, but a production-ready implementation should check the length of the vector and raise an error if it is not a multiple of the number of columns.)
We also define theupdate process for updating the cells based on the states of their neighbours as a public function of the board. This process steps through each cell on the board, acquires the ciphertexts corresponding to the neighbouring cells, and then applies theis_alivelogic to determine if the cell will be alive or dead after the update. It then pushes the ciphertext output of is_aliveto a new array. Once every cell has been evaluated, the ciphertexts in the oldstatesarray are overwritten by the ciphertexts in thenew_states array, and the process is ready to begin again.
Main Program
Ok, that’s all the individual tools we needed to create. We can now start writing our main program algorithm. We start by generating the board and theclientandserverkeys.
The FHE scheme applied by Concrete is a symmetric version of TFHE. This means that information is encrypted and decrypted with the same key, which must be kept secret. This is theclientkey, which allows a user to encrypt information, send it for processing and then decrypt the result.
The role of the client key is a familiar concept in cryptography. Theserverkey occupies a role which is specific to FHE; it’s the thing that enables the bootstrapping process.
The structure of the server key can be more complex; however, the core idea is that it is an encrypted version of the client key that is used when executing the homomorphic decryption circuit during the bootstrap. Theserverkey needs to be sent with the data to enable processing, which is why we need to include it in oursum function.
We then define the initial state of the board
Now, your cargo project should contain a folder labelled “src”, containing the files “lib.rs” and “main.rs”, and a “cargo.toml” file.
We now need to compile and run this code. In a terminal window, navigate to the homomorphic_game_of_lifefolder and run the commandcargo run --release. This will compile and run the code. If you’re using the default settings included in the above code, this will define a 6 by 6 board with a ‘glider’: a configuration which moves diagonally (in this case, from the top left to the bottom right) while keeping its shape. The output is printed in the terminal after each update (it looks a bit better with a square font).
As you will probably notice, this is a bit slow, taking about a minute per update on an Intel i7 CPU @ 3.6GHz. The main reason is that it makes use of only one thread, while modern CPUs generally have several cores which can work in parallel. And, at a first sight, it may seem that the Game of Life should be easy to parallelize: since each cell can be updated independently of the others and since evaluating the new state of each cell is, by far, the most intensive part of the code, one can in principle use as many cores in parallel as there are cells in the board with negligible overhead.
A small difficulty in this regard is that the server key can not be shared between threads (technically, this is because the ServerKey type does not implement the Sync trait; the reason is that a ServerKey has a buffer which is modified during the bootstrap, so only one thread should access it at any given time). However, there are ways around this, for instance duplicating the server key so that each thread can have its own (an example is given here, taking about 10s per update).
As previously mentioned, there is also certainly room to make the boolean circuit used to update the cell states more efficient — for instance, the sum of the the states of three consecutive cells on a row or column could be used for updating one cell on each side.
At Optalysys, we are using optics and silicon photonics to compute Fourier transforms at the speed of light and accelerate Deep Learning, scientific computing, and Homomorphic Encryption. Check out our website and Medium page for more information on what we are doing!
