> WIP, comments are welcomed. Thanks in advance!

> Technical paper on [IACR eprint 2016/969](https://eprint.iacr.org/2016/969), and R's talk's slides deck on [R's public website](https://web.engr.oregonstate.edu/~rosulekm/pubs/gc-gadgets-talk.pdf).

> A Primer to Garbled Circuit and Optimizations [here](https://hackmd.io/frMushaeSESma2OEdNseRQ).

TLDR: super efficient for arithmetic computation except for comparison:


# Generalizing Free-XOR

---
**Free-XOR is mod $2$**

---
**We can generalize to Free-XOR mod $m$**
> For $x \in \mathbb{Z}_m$, we have $W_x = W_0 + x\Delta_m$;
> Concretely we just pick $W_0$ then encode the rest as in the formula.

---
With the generalized Free-XOR encoding we have:
- Free addition mod $m$.
- Free multiplication by a constant $c$.
- Point-and-Permute still works by setting $\Delta_m$'s last "digit" (an element of $\mathbb{Z}_m$ not a bit anymore) to be 1 and for each wire label $W_x$ the color digit is set to be a random cyclic shift of $x$ from the color digit of wire $W_0$,
> i.e. color($W_x$) + $W_x$ = 1 and color($W_x$) = color($W_0$) + $x$.

## Mixed-Moduli Ciruit (MMC) for *Arbitrary* Projection

MMC is possible via a unary gate that allows conversion from Generalized Free-XOR mod $m$ to Generalized Free-XOR mod $l$, called "Projection". This can be done in a straight forward manner, i.e. by encrypting the arbitrary projection $\phi(x) \in \mathbb{Z}_l$ of $x \in \mathbb{Z}_m$ from mod $m$ to mod $l$,
> i.e. $C + \phi(x)\Delta_l$ is encrypted with key $A + x\Delta_m$ (resulting in $m$ ciphertexts).


Projection in BMR16 is compatible with Row Reduction (resulting in $m-1$ ciphertexts) and Point-and-Permute, i.e.
- **Point-and-Permute:** The $m$ ciphertexts can be ordered by the color digit as in Generalized Free-XOR,
> i.e. $\Delta_l$ is appended with the digit 1;
> and the $m$ ciphertexts can be ordered by the color digits of the input wire (i.e. $x + color(W_0)$):
> concretely each ciphertext is encrypted as
> $\hat{C}_{x+color(A_0)} = H(g, A_0 + x\Delta_m) + C_0 + \phi(x)\Delta_l$;
> thus $\hat{C}_{x+color(A_0)} = H(g, A_x) + C_{\phi(x)}$.
- **Row Reduction** By choosing $C_0 = -H(g, A_{-color(A_0)}) - \phi(-color(A_0)\Delta_l)$ we have $\hat{C} = 0$ and thus only $m-1$ ciphertexts are to be communicated.
<!-- - **Row Reduction 2** -->

---

### Concrete Algorithms


---

## Multiplication mod $m$


> Generalized Half-Gates and 3-Halves [here](https://hackmd.io/h7Tcx6ZkQzKNyQO5uUeqjw).
> > Somehow this generalization yields $2(m-1)$ ciphertexts so my guess is that BMR16 did not consider Row-Reduction when doing the above analysis?

## Garbling Arithmetic using CRT with MMC

To represent a large integer ($2^{32}$ or $2^{64}$) it is sufficient to use the CRT (Chinese Remainder Theorem) representation:
> $2 \cdot 3 \cdot 5 \cdot 7 \ldots 29 > 2^{32}$ (first 10 primes).
> $2 \cdot 3 \cdot 5 \cdot 7 \ldots 53 > 2^{64}$ (first 16 primes).
> $2 \cdot 3 \cdot 5 \cdot 7 \ldots 103 > 2^{128}$ (first 27 primes).

MMC can be leveraged to support many moduli in a single circuit.
> For each $\mathbb{Z}_{2^{32}}$ wire we use 10 CRT wires $\mathbb{Z}_{2}$, $\mathbb{Z}_{3}$, $\ldots$, $\mathbb{Z}_{29}$.
> We use notation: $[[x]]_{crt} = \{[x]_2, [x]_3, \ldots, [x]_{29} \}$

### Basic Arithmetic in CRT reps

Free addition --> just add each CRT residue.
> $[[x]]_{crt} + [[y]]_{crt} = \{[x + y]_2, [x + y]_3, \ldots, [x + y]_{29} \}$

Free multiplication by a constant --> just multiply each CRT residue.
> $c*[[x]]_{crt} = \{[c*x]_2, [c*x]_3, \ldots, [c*x]_{29} \}$
> However note that:
>> 
>> Use for scaling: https://en.wikipedia.org/wiki/List_of_prime_numbers

Raise to a public power --> use projection gate with power function $\phi(x) = [x^c]_p$ on each CRT residue mod $p$:
> cost $(2-1) + (3-1) + \ldots + (29-1)$ ciphertexts.

Similarly, remainder mod $q$ can be done with a projection gate with modulo function $x \mbox{ mod } q$ on each CRT residue mod $p$:
> cost $9 * (q-1)$ ciphertexts.

Multiplication mod $2 \cdot 3 \cdot \ldots 29$ --> can just multiply each CRT residue:
> cost $2*(2 + 3 + \ldots + 29)$ ciphertexts via [generalized half-gate](https://hackmd.io/h7Tcx6ZkQzKNyQO5uUeqjw).

### Alternate Multiplication

This alternate multiplication method scales better for high fan-in gate which will be used for advanced gadgets in the next Sections.

Observe that $x \cdot y = g^{dlog_g(x) + dlog_g(y)}$
> (provided that $x \cdot y \neq 0$);
> where $g$ is a primitive root mod $p$ and the exponent is in mod $p-1$.

GC in case $x \cdot y \neq 0$
- power of $g^z$ (1 projection gate $z \rightarrow g^z$ (mod $p$) costing $p-2$ ciphertexts)
- dlog(x) and dlog(y) (2 projection gates mapping $x, y \rightarrow dlog(x), dlog(y)$ (mod $p-1$) each costing $p-1$ ciphertexts)
- addition (free)
> cost $2(p-1) + (p-2) = (3p-4)$ ciphertexts

GC in case $x \cdot y = 0$
- compare $x = 0$ or $y = 0$ (2 equality tests which are 2 projection gates that map $\mathbb{Z}_p \setminus \{0\} \rightarrow 0$ and $0 \rightarrow 1$ each costing $p-1$ ciphertexts)
- OR gate which costs 2 ciphertexts (if we make the comparison output mod $2$)

Combining the two cases we actually compute $f(z,b) = g^z \mbox{ if } b = 0 \mbox{ OR } 0 \mbox{ otherwise}$.
> cost $6p - 5$ ciphertexts

In case of MMC total cost is $(6*2-5) + \ldots + (6*29-5)$

> Notice that high fan-in MUL gates such as fan-in 3 MUL gate $x \cdot y \cdot z$ benefits from free addition on the exponent as it only increase the number of dlog gates.

### Gadgets

#### Equality Test

To test $[[x]]_{crt} = [[y]]_{crt}$ we test $\large\land([x-y]_2 = 0; \ldots; [x-y]_{29} = 0)$
> subtraction is free
> comparison is a projection gate that costs $p-1$ ciphertexts
> AND gate which costs $10$ ciphertexts if we make comparison output mod $10$

In case of MMC total cost is $10 + (2-1) + \ldots + (29-1)$

#### Exact Weighted Threshold

The gate $\mathsf{Th}_{t,c_1,\ldots,c_m}(x_1,\ldots,x_m) = 1$ if $t = \sum^m_i c_i x_i$:
> Multiplication of $x_i$ by a public constant $c_i$ is free
> Addition is free
> Equality test (in MMC) cost $10 + (2-1) + \ldots + (29-1)$

#### Comparison

Comparison is typically done in binary form. Hence we need to convert the CRT reps to Boolean reps. Another method is to perform comparison in primorial-mixed-radix (PMR) form:
$[[x]]_{pmr} = (d_{29}, \ldots, d_1)$ where $d_i = \frac{x}{1\cdot\ldots\cdotp_i} \mbox{ mod } p_i$.


In such form, $[[x-y]]_{pmr}$'s most significant digit will server as the sign bit: $d_i = 0$ if $x > y$ and vice versa.

To convert CRT to PMR reps we can do the following:

An example:

Overall cost includes conversion from CRT to PMR, comparison in PMR form and conversion back to CRT form: $2(k-1)\sum_{i=1}^kp_i +2k^2 -k+p_k$

#### Weighted Threshold

The gate $\mathsf{Th}_{t,c_1,\ldots,c_m}(x_1,\ldots,x_m) = 1$ if $t > \sum^m_i c_i x_i$:
> Cost is as the exact weighted gate but with equality replaced with comparison.

## OT for Arithmetic CRT

Trivial approach is to use 1-out-of-p OT which yields base cost $(p-1)\lambda$ bits. In BMR16 the authors suggest a more efficient approach.

For a mod $p$ wire $w$, let $\ell = log p$ and we represent $w = \sum_{j=0}^{\ell-1} w_j2^j$. We can use $\ell$ 1-out-of-2 OTs to obtain the bits representation of $w$, then reconstruct the mod $p$ representation (for free) as $2^j$ are public constants.

## Input in CRT form