Chi Squared Test

Task

The Χ² or chi-squared tests are common statistical tests. For our application, we specifically consider Pearson's Goodness-of-Fit test as it can be used to test for deviation from the Hardy-Weinberg equilibrium in Genome Wide Association Studies (GWAS).

We split the computation into a polynomial part on the server and a final set of divisions on the client, as proposed by Lauter et al. First, the server receives the encrypted genotype counts N₀, N₁, N₂ then it computes α, (β_i)_i=0,1,2 as follows:
α = (4N₀ N₂ - N₁²)²
β₁ = 2(2N₀+N₁)²
β₂ = (2N₀+N₁)(2N₂+N₁)
β₃= 2(2N₂+N₁)²
and returns the encrypted results to the client. Decrypting these, the client can compute the test statistic as
Χ² = α/2N ( 1/β₁ + 1/β₂ + 1/β₃). While we consider the genotype counts as inputs, a more realistic deployment scenario would see the server calculate these over an encrypted genomic database.

Implementation in Tools

Cingulata

As the input circuit is already multiplicative depth-optimized, Cingulata's optimizations cannot improve the circuit. Instead, the optimized circuit has a larger multiplicative depth (38 instead of 16), although also significantly less expensive AND gates (277 instead of 1698).

Input circuit
	x depth 16, x gates 796, + gates 1698               <-- Original circuit
Executing optimization command ""
	x depth 15, x gates 576, + gates 1286 *
Executing optimization command "resyn2"
	x depth 40, x gates 894, + gates 326
Executing optimization command "resyn2rs"
	x depth 35, x gates 903, + gates 297
Executing optimization command "recadd3;resyn2rs"
	x depth 38, x gates 2770, + gates 277               <-- optimized circuit

SEAL-BFV

If you are compiling on Apple M1 (arm64) add the following to your CMAkeLists.txt before the line project(eval_benchmark):

SET(CMAKE_OSX_ARCHITECTURES "arm64" CACHE STRING "Build architectures for Mac OS X" FORCE)

SEAL-BFV-SIMD

TFHE

EVA

See https://github.com/MarbleHE/SoK/blob/master/EVA/source/chi_squared/chi_squared.py