Implementation

Let’s now put the above into practice. Our code, like the Concrete library, is written in Rust. More information on the Concrete Boolean library and how to use it can be found in the documentation. We’re also writing this with replication in mind, so for those so inclined to get to grips with Concrete Boolean we include some of the behind-the-scenes information about how Rust works.

Here, we start by first importing the relevant function and types from Concrete-boolean. Don’t worry too much about the syntax if you’re unfamiliar with Rust; this is conceptually similar (at least from the user point of view) to importing a library in C or Python:

[dependencies]
concrete-boolean = "0.1"

Let’s first tackle how to build the accumulator. For simplicity, we can break this up into two parts. The first part takes one server key, one encrypted bit, and a tuple of three ciphertexts encoding a 3-bit number, and returns an encryption of their sum. This is essentially a simple adder circuit made out of homomorphic Boolean gates:

// 3-bits adder
// 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)
}

This code is relatively straightforward: for each bit of the result, we perform a XOR operation with either the input aor the carry, and compute the next carry via an AND (except for the last bit, where no carry is needed). All operations are performed homomorphically thanks to the server key.

One element which may surprise readers who aren’t familiar with Rust (or C++, which uses a similar notation) is the use of the ampersand (&). This is used to pass objects by reference rather than by value; a function with an argument starting with an ampersand takes the memory address of the object to find it when needed, rather than creating a new object or moving it. (The details are, of course, a bit more involved than that. For the interested reader, the Rust book provides a good introduction to how objects can be passed to functions in Rust.) Contrary to C++, in Rust the ampersand must be specified both in the function declaration and when called.

Another peculiarity of Rust compared with other popular low-level languages is that a return statement is not always needed. Specifically, if the last line of a function is an expression which does not end with a semicolon, then the value of this expression is returned.

We can now use the above function to write the second part, the accumulator which sums a sequence of encrypted bits modulo 8:

// 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: &Vec<&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
}

Again, this function is fairly straightforward. It takes as arguments a server key, a vector of ciphertexts, and a tuple of three encryptions of 0. It then defines the result by summing the first element with zeros, accumulates the other elements, and returns the result. Notice that this function will crash (or ‘panic’ in the Rust terminology) if elementsis empty. This is not a problem in our case as we know that it will always be of size 8.

Finally, the function is_alive below returns an encryption of ‘true’ if the cell is alive after the update, and ‘false’ otherwise:

// 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
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.
    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)
    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;
    }
}

Example

Here is a simple example of use, with a 6 by 6 board:

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 fast in practice)
    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!("░");
                }
            }
        }
       
        println!("");
        
        unsafe {
            let runtime_and_energy = time_ene();
            println!("Runtime on the Echip so far: {}s", runtime_and_energy.0);
            println!("Energy cost on the Echip so far: {}J", runtime_and_energy.1);
        }
        
        println!("");
        
        // update
        board.update(&server_key, &zeros);
    }
}