Zama
Published in

Zama

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

Introduction to the Game of Life

  1. Birth: A dead cell with three (no more, no less) live neighbours becomes live on the next iteration.
  1. Survival: A live cell with two or three live neighbours lives on to the next iteration
  1. Death: A live cell with less than two or more than three live neighbours dies on the next iteration.

Boolean construction

  • It was already alive and had 2 or 3 neighbours.
  • It was dead and had exactly 3 neighbours.
Summing the neighbour cells via Boolean operations and accumulating the result for the centre cell. From the image we can see that there are 3 live cells surrounding the central cell, and this is reflected in the total accumulated binary value (ACC) after addition. This value can then be passed to the earlier algorithm that determines if the cell will be living or dead on the next iteration.
  • 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.
  • Define and encrypt the initial state of the board,
  • Update the board homomorphically without decrypting anything,
  • Decrypt and print the result.

Set-up

Accumulator

Checking if a cell is alive after the update

  • 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.

The Board

Main Program

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Optalysys

We are developing Optical chips which will provide previously unseen levels of processing whilst consuming a fraction of the power of electronic processors.