Skip to main content

Build Games with FHE

The primary benefit of FHE is its ability to improve application privacy, which can significantly increase the appeal of certain gaming scenarios.

For instance, integrating FHE into chess-like games can transform them into "fog-of-war" versions. Below, highlight a common example of such variations.

Game of Lifes

Game of Life, introduced in 1970 by British mathematician John H. Conway, is a zeroplayer cellular automaton controlling its evolution based solely on its initial arrangement. Interaction involves crafting an initial pattern and observing its evolution. Life unfolds on an infinite, two-dimensional square lattice of cells, each capable of being either active (populated) or inactive (unpopulated). Each cell interacts with its eight neighboring cells, horizontally, vertically, or diagonally. The following rules govern subsequent generations.

  • A live cell with less than two live neighbors dies due to underpopulation.
  • A live cell with two or three live neighbors survives to the next generation.
  • A live cell with more than three live neighbors dies due to overpopulation.
  • A dead cell with precisely three live neighbors becomes a live cell, as if by reproduction.

An alternate "dark" variant of Life can employ FHE, enabling blind computation of cell states. Note we use Boolean expressions to denote the states of cells. Let the variable state(i) denotes the state of the cell and neighbours(i) its number of live neighbours after ith iterations.

Then the state for any cell in the i+1 iteration will be:

state(i+1) = (neighbours(i) = 3) OR (state(i) AND neighbours(i) = 2).

Note in a new iteration, 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 live neighbours.
  • It was dead and had exactly 3 live neighbours.

The key job becomes how to blindly compute the neighbours(i) and compare it with 2 and 3, in the dark version. In our case, since each cell has 8 neighbours, the sum of their states is an arithmetic operation but can be simulated and constructed by logical (gate) computation. The figure below is a 4-bit adder which given 8 inputs of bit, and output a 4-bit number.

alt text

Note all the bit-wise operations shall be computed homomophically. And once the 4-bit number is computed as neighbours(i), we shall then homomorphcally compare it with 2 and 3. Again, we still use bit-wise computation to simulate the arithmetic compare. In particular, we can use the following pseudocode to complete the comparison.

Bit[] sum = neighbours(i);
Bit c3 = zkFHE.not(sum.[3]); //hightest bit shall not be 1;
Bit c2 = zkFHE.not(sum.[2]); // second highest bit shall not be 1;
//lowest bit can be 0 or 1, and the second lowest bit shall be 1;
Bit result = zkFHE.and(zkFHE.and(c3,c2), sum[1]);

Note one can use less homomorphic logical operations to simulate the condition satisfaction that the neighbours(i) shall be either 2 or 3. The post give more detailed explanation on implementing the private version of the game.

References