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
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 muchlonger 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 two bits, the two-bit number c1 c2 where
c1 = b1 AND b2
and
c2 = b1 XOR b2
is their sum. 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 labelled homomorphic_game_of_life.
Inside this folder will be a new folder called src
.
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
[dependencies]
concrete-boolean = "0.1"
Create a new file labelled lib.rs
in the src
folder that contains the line:
pub use concrete_boolean::*;
This will place the traits and functions from concrete-boolean
in the current namespace, and also allow their use inmain.rs
(which we will write later). Unless stated otherwise, the next pieces of code should also go in lib.rs
.
(What we’re doing here in lib.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
// 3-bits accumulator
// The value 8 is identified with 0.
fn add_1(server_key: &ServerKey, a: &Ciphertext, b: &(Ciphertext, Ciphertext, Ciphertext))
-> (Ciphertext, Ciphertext, Ciphertext)
{
// lowest bit of the result
let c1 = server_key.xor(a,&b.0);
// first carry
let r = server_key.and(a,&b.0);
// second lowest bit of the result
let c2 = server_key.xor(&r,&b.1);
// second carry
let r = server_key.and(&r,&b.1);
// highest bit of the result
let c3 = server_key.xor(&r,&b.2);
(c1, c2, c3)
}
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).
// sum a sequence of ciphertexts, with the value 8 identified with 0
// This function panics if `elements` is empty.
fn sum(server_key: &ServerKey, elements: &[&Ciphertext], zeros: &(Ciphertext, Ciphertext, Ciphertext))
-> (Ciphertext, Ciphertext, Ciphertext)
{
let mut result = add_1(server_key, elements[0], zeros);
for i in 1..elements.len() {
result = add_1(server_key, elements[i], &result);
}
result
}
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
// sum a sequence of ciphertexts, with the value 8 identified with 0
// This function panics if `elements` is empty.
fn sum_no_panic(server_key: &ServerKey, elements: &[&Ciphertext], zeros: &(Ciphertext, Ciphertext, Ciphertext))
-> (Ciphertext, Ciphertext, Ciphertext)
{
let mut result = zeros.0.clone();
for i in 0..elements.len() {
result = add_1(server_key, elements[i], &result);
}
result
}
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 oursum
function, 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.
fn is_alive(server_key: &ServerKey, cell: &Ciphertext, neighbours: &[&Ciphertext],
zeros: &(Ciphertext, Ciphertext, Ciphertext))
-> Ciphertext
{
// perform the sum
let sum_neighbours = sum(server_key, neighbours, zeros);
// check if the sum is equal to 2 or 3
let sum_is_2_or_3 = server_key.and(&sum_neighbours.1, &server_key.not(&sum_neighbours.2));
// check if the sum is 3
let sum_is_3 = server_key.and(&sum_neighbours.0, &server_key.and(&sum_neighbours.1,
&server_key.not(&sum_neighbours.2)));
// return (an encryption of) the new state of the cell
server_key.or(&sum_is_3, &server_key.and(cell, &sum_is_2_or_3))
}
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 astruct
to 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.)
/// a board structure for Conway's game of Life
///
/// Fields:
///
/// dimensions: the height and width of the board
/// states: vector of ciphertextx encoding the current state of each cell
pub struct Board {
dimensions: (usize, usize),
states: Vec<Ciphertext>
}
impl Board {
/// build a new board
///
/// Arguments:
///
/// n_cols: the number of columns of the board
/// states: vector of ciphertexts encoding the initial state of each cell
///
/// If the length of the states vector is not a multiplt of n_cols, the cells on the incomplete
/// row will not be updated.
pub fn new(n_cols: usize, states: Vec<Ciphertext>) -> Board {
// compute the number of rows
let n_rows = states.len() / n_cols;
Board { dimensions: (n_rows, n_cols), states }
}
/// update the state of each cell
///
/// Arguments:
///
/// server_key: the server key needed to perform homomorphic operations
/// zeros: three encryptions of false (which may be identical)
pub fn update(&mut self, server_key: &ServerKey, zeros: &(Ciphertext, Ciphertext, Ciphertext))
{
let mut new_states = Vec::<Ciphertext>::new();
let nx = self.dimensions.0;
let ny = self.dimensions.1;
for i in 0..nx {
let im = if i == 0 { nx-1 } else { i-1 };
let ip = if i == nx-1 { 0 } else { i+1 };
for j in 0..ny {
let jm = if j == 0 { ny-1 } else { j-1 };
let jp = if j == ny-1 { 0 } else { j+1 };
// get the neighbours, with periodic boundary conditions
let n1 = &self.states[im*ny+jm];
let n2 = &self.states[im*ny+j];
let n3 = &self.states[im*ny+jp];
let n4 = &self.states[i*ny+jm];
let n5 = &self.states[i*ny+jp];
let n6 = &self.states[ip*ny+jm];
let n7 = &self.states[ip*ny+j];
let n8 = &self.states[ip*ny+jp];
// see if the cell is alive of dead
new_states.push(is_alive(server_key, &self.states[i*ny+j],
&vec![n1,n2,n3,n4,n5,n6,n7,n8], zeros));
}
}
// update the board
self.states = new_states;
}
}
We also define the update
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 the is_alive
logic to determine if the cell will be alive or dead after the update. It then pushes the ciphertext output of is_alive
to a new array. Once every cell has been evaluated, the ciphertexts in the old states
array are overwritten by the ciphertexts in the new_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 the client
and server
keys.
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 the client
key, 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. The server
key 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. The server
key 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
use homomorphic_game_of_life::*;
fn main() {
// define the board dimensions
let (n_rows, n_cols): (usize, usize) = (6,6);
// generate the client and server keys
let (client_key, server_key) = gen_keys();
// compute three encryptions of 0
// (we could also work with only one; but this is quite fqst inprqctice)
let zeros = (client_key.encrypt(false), client_key.encrypt(false), client_key.encrypt(false));
// initial configuration
let states = vec![
true, false, false, false, false, false,
false, true, true, false, false, false,
true, true, false, false, false, false,
false, false, false, false, false, false,
false, false, false, false, false, false,
false, false, false, false, false, false,
];
// encrypt the initial configuration
let states: Vec<Ciphertext> = states.into_iter().map(|x| client_key.encrypt(x)).collect();
// build the board
let mut board = Board::new(n_cols, states);
loop {
// show the board
for i in 0..n_rows {
println!("");
for j in 0..n_rows {
if client_key.decrypt(&board.states[i*n_cols+j]) {
print!("█");
} else {
print!("░");
}
}
}
// increase the time step
board.update(&server_key, &zeros);
}
}
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_life
folder and run the command cargo 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!
With Florent Michel, Joseph Wilson and Edward Cottle