# FHE ZheroTag

The goal is to build a new iteration of **ZheroTag** [1](https://docs.google.com/presentation/d/1OL8yg962QT-DHgDD-zecBKWVpN6b9eNND8x9Lz6F8Rc/edit#slide=id.g19e6048f63d_0_9), [2](https://github.com/kilyig/ZheroTag), [3](https://docs.google.com/document/d/1NKlXGp6SA32hZcv-NY0PsTs4kYVaMOUi36wuCUvgoPs/edit#heading=h.nn6shegjqj20) leveraging Fully Homomorphic Encryption. The core cryptographic primitive that enables to play the game without a trusted third party is Private Set Intersection (PSI). PSI allows two (or more) parties, where each party holds a set, to calculate the intersection of the two sets and reveal it to one another. Elements outside the intersection should not be revealed to any party.

The current version of the game is built using [PSI based on Diffie Hellman](https://github.com/kilyig/ZheroTag#psi-based-on-diffie-hellman). This works aims to explore the tradeoffs in building this leveraging FHE, especially in terms of:

- Developer experience
- Gamer experience (prover time, rounds of communications required, ...)
- Trust assumptions and overall soundness of the game dynamic

Note that this is a simplified version of [Fog of War Chess](https://www.youtube.com/watch?v=_1F9LHuQFxc). Neverthelss, starting from the cryptographic primitives being built here, it's trivial to extend it to a more complex game dynamic.

## Algorithms and Notation

### ZheroTag Game

Let finite $U \subseteq \mathbb{Z}^2$ be the set of positions on the board. Let ${P} = ( u, {N}, {S} )$ be the state of ZheroTag player where $u \in U$ is the current position on the board, ${N}$ is the set of positions that player can move to (_neighbors_), and ${S}$ is the set of positions that player can see at state ${P}$.

For example a 6x6 grid will be represented by the following matrix `M`

[
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
]

If the position of a player $u$ is `M[1][0]`. ${N}$ and ${S}$ equal to the set denoted by ones in the following matrix

[
    [1, 1, 0, 0, 0, 0]
    [u, 1, 0, 0, 0, 0]
    [1, 1, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
]

### Fully Homomorphic Encryption

We are gonna first describe the standard algorithm for FHE applied to PSI.

#### Setup

1. $Setup(\lambda, \kappa)=pp$
2. `White` generates secret key $sk_{w}$ - $SecKeyGen()$ and corresponding public key $pk_{w}$
3. `Black` generates secret key $sk_{b}$ - $SecKeyGen()$ and corresponding public key $pk_{b}$

#### Encryption

4. `White` encrypts their position $u_{w}$ under $pk_b$. $Enc(u_{w}, pk_{b}) = ct_{pos}$

[
    [E(0), E(0), E(0), E(0), E(0), E(0)]
    [E(0), E(0), E(0), E(0), E(0), E(0)]
    [E(0), E(0), E(0), E(1), E(0), E(0)]
    [E(0), E(0), E(0), E(0), E(0), E(0)]
    [E(0), E(0), E(0), E(0), E(0), E(0)]
    [E(0), E(0), E(0), E(0), E(0), E(0)]
]

5. `Black` encrypts their view $S_{b}$ under $pk_b$. $Enc(S_{b}, pk_{b}) = ct_{view}$

[
    [E(0), E(0), E(0), E(1), E(1), E(1)]
    [E(0), E(0), E(0), E(1), E(0), E(1)]
    [E(0), E(0), E(0), E(1), E(1), E(1)]
    [E(0), E(0), E(0), E(0), E(0), E(0)]
    [E(0), E(0), E(0), E(0), E(0), E(0)]
    [E(0), E(0), E(0), E(0), E(0), E(0)]
]

#### PSI homomorphic evaluation

Any third party can perform the homomorphic evaluation on two encrypted data sets if and only if these are encrypted under the same public key. For the PSI application, we are interested to compute the intersection between the sets $u_{w}$ and $S_{b}$

6. Performs Homomorphic Multiplication between $ct_{pos}$ and $ct_{view}$. $EvalPSI(ct_{pos}, ct_{view}) = ct_{psi}$

In particular, this require to perform homomorphic multiplication across the two encrypted matrices $ct_{pos}$ and $ct_{view}$. The result will be the following.

[
    [E(0), E(0), E(0), E(0), E(0), E(0)]
    [E(0), E(0), E(0), E(0), E(0), E(0)]
    [E(0), E(0), E(0), E(1), E(0), E(0)]
    [E(0), E(0), E(0), E(0), E(0), E(0)]
    [E(0), E(0), E(0), E(0), E(0), E(0)]
    [E(0), E(0), E(0), E(0), E(0), E(0)]
]

#### Decryption

7. `Black` can now decrypt $ct_{psi}$ using their secret key $sk_{b}$. $Dec(ct_{psi}, sk_{b}) = psi$. The result is the intersection between their view $S_{b}$ and `White` position $u_{w}$.

[
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 1, 0, 0]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
]

## Game Workflow

### Initial State

$P_w = (u_w, {N_w}, {S_w} )$

[
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
    [1, 1, 1, 0, 0, 0]
    [1, u, 1, 0, 0, 0]
    [1, 1, 1, 0, 0, 0]
]

$P_b = ( u_b, {N_b}, {S_b} )$

[
    [0, 0, 0, 1, 1, 1]
    [0, 0, 0, 1, u, 1]
    [0, 0, 0, 1, 1, 1]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
]

### White to move

- `Black` commits to their state. $C(P_b) = C_b$
- `Black` encrypts its view ${S_b}$ under $pk_b$. $Enc({S_b}, pk_b) = ct_{view}$
- `Black` generates a composite proof $\pi = (\pi_1, \pi_2)$ such that:
- $\pi_{1}(S_b, pk_b, ct_{view})$ : Proof of correct encryption
- $\pi_{2}(C_b, S_b)$ : Proof that ${S_b}$ belongs to the latest committed state
- `Black` **shares** $\pi$ and $ct_{view}$ with `White`
- `White` makes their move

$P_w' = (u_w', {N_w}', {S_w}' )$

[
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
    [0, 1, 1, 1, 0, 0]
    [0, 1, u, 1, 0, 0]
    [0, 1, 1, 1, 0, 0]
    [0, 0, 0, 0, 0, 0]
]

- `White` commits to their state. $C(P_w') = C_w'$
- `White` applies PSI between their position $u_w'$ and `Black`'s view $EvalPSI(u_w', ct_{view}) = ct_{psi}$
- `White` generates a composite proof $\pi = (\pi_1, \pi_2)$ such that:
- $\pi_{1}(EvalPSI, u_w', ct_{view}, ct_{psi})$ : Proof of correct homomorphic evaluation
- $\pi_{2}(C_w', u_w')$ : Proof that ${u_w'}$ belongs to the latest committed state
- `White` **shares** $\pi$ and $ct_{psi}$ with `Black`
- `Black` decrypts $ct_{psi}$. No intersection. Unfortunately for them, it means that there's no way to win with the next move. *(note that it's impossible for `Black` to win at the second move, so this whole process can be disregarded and start from the next round)*

[
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
]

### Black to move

- `White` encrypts its view ${S_w'}$ under $pk_w$. $Enc({S_w'}, pk_w) = ct_{view}$
- `White` generates a composite proof $\pi = (\pi_1, \pi_2)$ such that:
- $\pi_{1}(S_w', pk_w, ct_{view})$ : Proof of correct encryption
- $\pi_{2}(C_w', S_w')$ : Proof that ${S_w'}$ belongs to the latest committed state
- `White` **shares** $\pi$ and $ct_{view}$ with `Black`
- `Black` makes their move

$P_b' = (u_b', {N_b}', {S_b}' )$

[
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 1, 1, 1]
    [0, 0, 0, 1, u, 1]
    [0, 0, 0, 1, 1, 1]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
]

- `Black` commits to their state. $C(P_b') = C_b'$
- `Black` applies PSI between their position $u_b'$ and `White`'s view $EvalPSI(u_b', ct_{view}) = ct_{psi}$
- `Black` generates a composite proof $\pi = (\pi_1, \pi_2)$ such that:
- $\pi_{1}(EvalPSI, u_b', ct_{view}, ct_{psi})$ : Proof of correct homomorphic evaluation
- $\pi_{2}(C_b', u_b')$ : Proof that ${u_b'}$ belongs to the latest committed state
- `Black` **shares** $\pi$ and $ct_{psi}$ with `White`
- `White` decrypts $ct_{psi}$. No intersection. Unfortunately for them, it means that there's no way to win with the next move

[
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
]

### White to move

- `Black` encrypts its view ${S_b'}$ under $pk_b$. $Enc({S_b'}, pk_b) = ct_{view}$
- `Black` generates a composite proof $\pi = (\pi_1, \pi_2)$ such that:
- $\pi_{1}(S_b', pk_b, ct_{view})$ : Proof of correct encryption
- $\pi_{2}(C_b', S_b')$ : Proof that ${S_w'}$ belongs to the latest committed state
- `Black` **shares** $\pi$ and $ct_{view}$ with `White`
- `White` makes their move

$P_w'' = (u_w'', {N_w}'', {S_w}'' )$

[
    [0, 0, 0, 0, 0, 0]
    [0, 0, 1, 1, 1, 0]
    [0, 0, 1, u, 1, 0]
    [0, 0, 1, 1, 1, 0]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
]

- `White` commits to their state. $C(P_w'') = C_w''$
- `White` applies PSI between their position $u_w''$ and `Black`'s view $EvalPSI(u_w'', ct_{view}) = ct_{psi}$
- `White` generates a composite proof $\pi = (\pi_1, \pi_2)$ such that:
- $\pi_{1}(EvalPSI, u_w'', ct_{view}, ct_{psi})$ : Proof of correct homomorphic evaluation
- $\pi_{2}(C_w'', u_w'')$ : Proof that ${u_w''}$ belongs to the latest committed state
- `White` **shares** $\pi$ and $ct_{psi}$ with `Black`
- `Black` decrypts $ct_{psi}$. There's an intersection: `White` is in their view. It means they can win with the next move. Game over

[
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 1, 0, 0]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
]

---

### Observations/questions/open issue

- Reduced number of communications. Each round includes only 2 communications between the two actors.
- Requires to produce a zero knowledge proof of correct execution of $EvalPSI$ which might not be feasible
- Do we really need FHE for that. Other multiplicative homomorphic encryption algo should suffice