# Diogenes Condensed

## 1. Notation:
* $P,Q$ -- big numbers, $P$ divides $Q$
* $n$ -- RLWE degree, big (65536).
* $\mathbf{x}|_{\vec{f}}$ -- subset of $\mathbf{x}$ by $\vec{f}$.
* $R_Q$ -- ring of polynomials over $Z_Q$ of degree $n$.

## 2. User Equations and Constraints over $Z_Q$

### 2.1 Variables
Public variables:
* $(A,B)\in R_Q^2$ -- common public key.
* $(a,b)\in R_Q^2$ -- common public key shares.
* $\vec{f}$ -- flag vector of candidates whose product is not divided by first primes.
* $ex=(ex_1,ex_2)$ -- shares ciphertext
* $EX\in R_Q^2$ -- factor/triple ciphertext.
* $EXYZ\in R_Q^2$ -- affine function ciphertext.
* $\mathbf{\gamma}\in Z_{2^{2048}}^{1000}$ --- a vector of bases for Jacobi test.

Private variables:
* $s\in R_Q$ secret key
* $e\in R_Q$ error
* $\mathbf{x}_1||\mathbf{x}_2||\mathbf{x}_3,\mathbf{y}_1||\mathbf{y}_2||\mathbf{y}_3,\mathbf{z}_1||\mathbf{z}_2||\mathbf{z}_3\in Z_{\tau}^n$ -- factor shares and triple elements.
* $x,y,z\in R_P$ -- interpolant polynomials fo $\mathbf{x},\mathbf{y},\mathbf{z}$
* $u_x,v_x,w_x,u_z,v_z,w_z,r\in R_Q$ -- encryption auxiliary variables.
* $r$ -- decryption noise.

### 2.2 Round By Round

#### Round 1:
$$
e,s \leftarrow \chi_{R_Q}(8)
$$

#### Round 3:
$$
b = s\cdot A +e
$$
One equation over $R_Q$ gives $n$ linear constraints over $Z_Q$.

#### Round 4.
* NTT conversion:
$$
x = NTT(\mathbf{x})
$$
Gives $n$ linear constraints over $Z_Q$.
* Encryption:
$$ex=(a\cdot u_x+v_x, b\cdot u_x+w_x+(Q/P)x)$$
Two equations over $R_Q$ give $2n$ linear constraints over $Z_Q$.

#### Round 5:
* NTT conversion:
$$
z = NTT(\mathbf{z})
$$
Gives $n$ linear constraints over $Z_Q$.
* Encryption:
$$ (ez_1,ez_2)=(A\cdot u_z+v_z, B\cdot u_z+w_z+(Q/P)(z+z_p)) $$
Two equations over $R_Q$ give $2n$ linear constraints over $Z_Q$.
* Multiplication over ciphertext$$
(ep_1,ep_2) = (y\cdot EX_1,y \cdot EX_2)
$$
Two equations over $R_Q$ give $2n$ linear constraints over $Z_Q$.
* Affine: $$
exyz = ep - ez.$$
Can be combined with previous equations and constraints.

#### Round 6:
* Decryption: $$ pxyz=r-s\cdot EXYZ$$
One equation over $R_Q$ gives $n$ linear constraints over $Z_Q$.

#### Round 7:
* Selection
\begin{align}
\mathbf{ps} = \mathbf{x}_1|_{\vec{f}};\\
\mathbf{qs} = \mathbf{y}_1|_{\vec{f}}.
\end{align}
At most $2n$ linear constraints, but maybe none.
* Blinding triples
\begin{align}
\mathbf{ax} = \mathbf{ps}-\mathbf{x}_2;\\
\mathbf{by} = \mathbf{qs}-\mathbf{y}_2
\end{align}
Gives $2n$ linear constraints over $Z_Q$.

#### Round 8
* Consuming triples
$$
\mathbf{axby} =AX\circ \mathbf{qs}+ BY\circ \mathbf{ps} + \mathbf{z}_2
$$
Gives $n$ linear constraints over $Z_Q$.

#### Round 10
* Exponentiating for Jacobi test
$$
\mathbf{exp} = \mathbf{\gamma_j}^{-\mathbf{ps}-\mathbf{qs}}\pmod{N_j}
$$
This is constraint over $Z_{N_j}$.

#### Round 11:
\begin{align}
ax' = aC-x_3;\\
by' = bC-y_3.
\end{align}
Two equations and two constraints over $Z_Q$.

#### Round 12:
* Exponentiating for Jacobi test $$
\mathbf{exp'} = \mathbf{\gamma}'^{-\mathbf{ps}-\mathbf{qs}}\pmod{N}
$$
These are 128 equations/constraints over $Z_N$.
* Affine function for GCD test: $$
axby' = AX'bC+BY'aC+z_3+v \pmod{B}
$$
One equation and one constraint over $Z_B$, so a few constraints over $Z_Q$.

#### Range constraints
* We need to range-constrain $u_x,v_x,w_x,u_z,v_z,w_z$ to be within 8-bit range.
* We constrain $\mathbf{x},\mathbf{y},\mathbf{z},r,z_p$ to be smaller than $\tau$.

### 2.3 Total count

Assume that to prevent the Dogbyte attack, we make $n$ small so that we likely to fail and have to repeat $65536/n$ iterations. Only one candidate is tested in round 10. We provide a ZK proof only for the successful iteration, where we need:
* $15n+4$ constraints over $Z_Q$;
* $6n$ range proofs for 8-bit ranges;
* $5n$ range proofs for $P$-range.
* $129$ exponent constraints over $Z_N$ (Sigma protocol);
* Constraints that link $Z_N$ exponents with $Z_Q$ values (called Connecting Sigma and Ligero in the original paper).

### 2.4 Global Equations
Round 2:
$$
A = \sum_i a_i
$$

Round 3:
$$
B = \sum_i b_i
$$

Round 4:
$$
EX= \sum_i ex_{i}
$$

Round 5:
$$
EXYZ = \sum_i exyz_i
$$

Round 6:
$$
\mathbf{C} =\sum_i pxyz_i
$$