# Diogenes
<style>
.ui-infobar, #doc.markdown-body { max-width: 1450px; }
</style>

## Code

### Notation

RLWE parameters:
* $\text{NbPrimesP} = 9$ and array $\mathcal{P}[NbPrimesP]$.
* $\text{NbPrimesQ} = 21$
* $P,Q$ -- prime products of 9 (resp., 21) 62-bit primes, $P$ divides $Q$.
* $R_P = Z_P[X]/(X^n+1)$;
* $R_Q = Z_Q[X]/(X^n+1)$;

Protocol parameters:
* $R_1 = 43917$ (primesPS)
* $R_2 = 21600$ (primesCAN)
* $R_3 = 19$ (primesGCD)
* $n=R_1+R_2+R_3=65536$

[Key generation syntax]():
$$
Gen: \;\rightarrow R_Q\times R_Q\times R_Q:\quad (\text{private key}=s,\text{public key}=a,\text{randomness}=e)
$$

[Vector encryption syntax](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/LatticeEncryption.hpp#L308-L340):
$$
Enc: \, Z_P^{n}\times R_Q^2\rightarrow R_Q^2\times R_Q\times R_Q\times R_Q:\quad (\text{message}[],\text{public key})\rightarrow(\text{ciphertext},u,v,w).
$$

[Ciphertext multiplication syntax](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/LatticeEncryption.hpp#L594-L600):
$$
\mathrm{Product}:\,R_Q^2\times R_P\times Z^n\times R_Q^2\rightarrow R_Q^2\times R_Q:\quad (\text{ciphertext},\text{scalar},\text{moduli}[],\text{public key})\rightarrow(\text{ciphertext},z).
$$

[Ciphertext partial decryption syntax](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/LatticeEncryption.hpp#L594-L600):
$$
\mathrm{PartDecrypt}: R_Q^2\times R_Q\rightarrow R_Q\times R_Q:\quad (\text{ciphertext},\text{secret key})\rightarrow(\text{partial message},r).
$$

Packing:
$$
\mathbf{m}\in Z_P^n \rightarrow m(X):\quad m = \text{Inverse FFT}(\mathbf{m})
$$

Polynom $p(x)$ evaluation procedure:
* Apply inverse NTT to unpack the message
* Round each value to the nearest multiple of $Q/P$;

[CRT reconstruction](https://github.com/ligeroinc/LigeroRSA/blob/17d8b3d00604da1e0272035e871fac3add8d7551/include/Math.hpp#L419)
$$
z = \mathrm{Reconstruct}(R[N] = \mathrm{Remainders},M[N]=\mathrm{Moduli})
$$
* $P = \prod_i M[i]$
* $$
v[i] = \left(\frac{P}{M[i]} \bmod{M[i]}\right),\;1\leq i\leq N.
$$
* $$
c[i] = \frac{P}{M[i]}\cdot \left(\frac{1}{v[i]} \bmod{M[i]}\right),\;1\leq i\leq N.$$
* $$
z = \sum_i c[i] R[i] \bmod{P}
$$

## Protocol flow
* $\rightarrow$: from Client to Coordinator
* $\leftarrow$: from Coordinator to Client
* $\Leftarrow$: from Coordinator to all Clients

| | Client $P_i$ | Coordinator |
| -------- | -------- | -------- |
| **Round 1** | | |
| | Generate gaussian [$e,s$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2039) with parameter [$\chi=8$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L657-L658) | |
| | [Generate (private,public) key pair for signatures](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/Transport.hpp#L1360-L1362)| [Generate (private,public) key pair for signatures and store public key in $config$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/src/coordinator_full_protocol.cpp#L153-L158) |
| | [Generate array of certain 19 primes $\alpha_{GCD}[]$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2046) using an [RNG seeded with 0](https://github.com/ligeroinc/LigeroRSA/blob/17d8b3d00604da1e0272035e871fac3add8d7551/include/Math.hpp#L464-L474) | |
| | [Generate array of random 2176-bit numbers $\sigma_r[128]$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2061) | |
| | [Set an array $\sigma_{r,GCD}[128\cdot 19l+19j+k] = (\sigma_r[j]\bmod \alpha_{GCD}[k])\bmod \mathcal{P}[l],l\leq 9$.](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2059-L2072) | |
| | [Record $e_i,s_i,\sigma_{r,GCD}[]$ to secretData](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2089) | |
| | [Prepare a Ligero proof $\widehat{\mathcal{P}}$ of knowledge of secretData filled so far](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2093) | |
| | [Generate random $a\in R_Q$ and FFT it](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2101-L2102) | |
| | [Generate Jacobi seed shares $seed_1,seed_2$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2104-L2106) | |
| | $\rightarrow$ [(ID_PARTY, IP address,$\widehat{\mathcal{P}}$, commitments $H(a),H(seed_1),H(seed_2)$)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2108-L2116) | [Store commitments](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/Transport.hpp#L170) |
| | | $\Leftarrow$ [(PROTOCOL_CONFIG,party numbers $P[i]$, config)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1236-L1240) |
| | [Store coordinator public key](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L626) | |
| **Round 2** | |
| | $\rightarrow$ [(PUBLIC_KEY_A_SHARES, decommitment $a$)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2138) | |
| | | [Check if $a_i$ matches $H(a_i)$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/Transport.hpp#L505-L520) |
| | |[$A= \sum_i a_i$ (in $R_Q$)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L39)|
| | | $\Leftarrow$ [PUBLIC_KEY_A_VALUE, $A$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L43) |
| **Round 3** | |
| | [Compute $b = s\cdot A +e$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2150-L2153) | [InvertNTT of $A$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L44) |
| | $\rightarrow$ [(PUBLIC_KEY_B_SHARES, $b$)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2156) | |
| | |[$B= \sum_i b_i$ (in $R_Q$)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L39)|
| | | $\Leftarrow$ [(PUBLIC_KEY_B_VALUE, $B$)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L43), InvertNTT of $B$ |
| | [Set public key $=(A,B)$, secret key $=s$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2166) | |
| **Intermediate** | |
| | |[Assign](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1746-L1748) $P_1$ to the first party and broadcast ASSIGNMENT_P1. Also broadcast other IDs. |
| | Check if we are $P_1$ | |
| **Round 4** | |
| | [Create prime products $\tau_i$ and weights $w_i$, $1\leq i \leq 6=\lceil 1000/175 \rceil$.](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2249) | [Create prime products $\tau_i$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L854) |
| | [Create prime vector $\alpha_{CAN}[6 =\lceil 1048/175 \rceil]$ and weights $w'[i] = 3600$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2250) | [Create prime vector $\alpha_{CAN}$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L856) |
| | [Create prime vector $\alpha_{GCD}[19 =\lceil 3210/175 \rceil]$ and weights $w''[i] = 1=19/19$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2251) | [Create prime vector $\alpha_{GCD}$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L859) |
| | [Generate a vector of random 175-bit triples $(x[n],y[n],z[n])$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2277-L2282) | |
| | Define $v=\phi(k)$ as minimum $v$ such that $\sum_{i\leq v}w_i\geq k$ | |
| | Define $\psi(k) = k\bmod{6}$ | |
| | Define $\nu(k)= k\bmod{19}$ | |
| | Create array of [primes](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2369) or [prime products](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2335): $\tau[k] = \begin{cases} \tau_{\phi(k)}, & k<R_1\\ \alpha_{CAN}[\psi(k-R_1)],&R_1\leq k < R_1+R_2;\\\alpha_{GCD}[\nu(k-R_1-R_2)],&R_1+R_2 \leq k\\& <R_1+R_2+R_3\end{cases}$ | |
| | [Reduce elements to fit the bucket](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2328-L2330) $x[k] = x[k]\bmod{\tau[k]}$, $y[k] = y[k]\bmod{\tau[k]}$, $z[k]=z[k]\bmod{\tau[k]}, k<R_1+R_2+R_3$| |
| | [Create auxiliary triple elements from first $R_1$ triples](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2333-L2334) $z[k]=0$, $a[k]=x[k]$, $b[k]=y[k]$, $k<R_1$ | |
| | [Create auxiliary candidate elements from next $R_2$ triples](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2349-L2351) $x_{can}[k]=x[k+R_1]$, $y_{can}[k]=y[k+R_1]$, $z_{can}[k]=z[k+R_1]$, $k < R_2$| |
| | [Create auxiliary GCD elements from last $R_3$ triples](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2366-L2372) $x_{gcd}[k]=x[k+R_1+R_2]$, $y_{gcd}[k]=y[k+R_1+R_2]$, $z_{gcd}[k]=z[k+R_1+R_2]$, $k < R_3$ | |
| | [Encrypt $x[]$ on the common public key $a$: $$(E_x,u_x,v_x,w_x) = Enc(x[],a)$$ ](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2391) | |
| | $\rightarrow$ [(ENCRYPTED_X_SHARES, $E_x$)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2400) | |
| | | [$EX= \sum_i E_{x,i},$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L923-L928)|
| | | $\Leftarrow$ [(ENCRYPTED_X_VALUE, $EX)$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L936) |
| **Round 5** | |
| | [Encrypt $z[]$ on the common public key $A$: $$(E_z,u_z,v_z,w_z) = Enc(z[],A)$$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2410) | |
| | [Multiply ciphertext: $(E_p,z_p) = \mathrm{Product}(EX,y,\tau[],A)$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2425) where $y$ is interpreted as $R_P$ element| |
| | [Compute affine function $E_{xyz} = E_p-E_z$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2428-L2430) | |
| | $\rightarrow$ [(ENCRYPTED_XY_PLUS_Z_SHARES, $E_{xyz}$)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2434) | |
| | | [$EXYZ= \sum_i E_{xyz,i}$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L943-L948)|
| | | $\Leftarrow$ [(ENCRYPTED_XY_PLUS_Z_VALUE, $EXYZ$)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L955), Apply inverse FFT to $EXYZ$ |
| **Round 6** | Pre-sieving: for each $k$ interpret $a[k],b[k]$ as shares of some $A[k], B[k]$ and filter out those not co-prime with $\tau[k]$. Keep at most 3600 from each of 6 buckets, the rest declare to be shares of 3600 prime candidates in the CRT form |
| | [Partially decrypt: $(p_{xyz},r) = \begin{cases} \mathrm{PartDecrypt}(EXYZ,s)& \text{If }P_1;\\ \mathrm{PartDecrypt}(\langle EXYZ.1,0\rangle,s)& \text{If not }P_1;\end{cases}$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2448-L2456)| |
| | $\rightarrow$ [(PARTIAL_XY_MINUS_Z_SHARES, $p_{xyz}$)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2458) | |
| | | [$eit_{poly}= \sum_i p_{xyz,i}$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L961-L966)|
| | | Create array of [primes](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L992-L1012) or [prime products](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L980-L985): $\tau[k] = \begin{cases} \tau_{\phi(k)}, & k\leq R_1\\ \alpha_{CAN}[\psi(k-R_1)],&R_1< k \leq R_1+R_2;\\\alpha_{GCD}[\nu(k-R_1-R_2)],&R_1+R_2 < k\\& \leq R_1+R_2+R_3\end{cases}$ |
| | | [Recover multiples: $c[k] = Eval(eit_{poly},\tau[])[k]$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1022) |
| | | [For every $k\leq R_1$ compute $flag[k]=(GCD(c[k],\tau[k])!=1)$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L811-L814) |
| | | $\Leftarrow$ [(PS_SIEVING_FLAGS, $flags[])$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1030) |
| | Store flags[] internally | [Write flags[] to transcript](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1031) |
| | [Let $col_1[]$ be the subset of first $w_1$ element pairs $(a[k],b[k])$ such that $flags[k]=1$. Let $col_2$ be the subset of next $w_2$ elements $(a[k],b[k])$ such that $flags[k]=1$, and up to $w_6$. ](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2192-L2208) Also starting from $i=0$ set $index[i]$ to the number of successful candidates so far if $flags[i]=1$, else set to $-1$. | [Let $col_2[]$ be the subset of first $w_1$ elements $c[k]$ such that $flags[k]=1$. Let $col_3[]$ be the subset of next $w_2$ elements $c[k]$ such that $flags[k]=1$, and up to $w_6$. ](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1264-L1273) |
| | [Let $valid\_shares[6][]=\{col_1,col_2,\ldots,col_6\}$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2473) | [Create array $col_1$ of ones](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1276) |
| | [Let $M$ be the minimal length of these vectors. Then create an array res[M][7], whose $i$-th column is $col_i[]$ truncated to $m$.](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2492-L2499) Column 7 is [all 3 (for $P_1$) and 0 (for all others)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2508). | [Let $M$ be the minimal length of these vectors. Then create an array res[M][7], whose $i$-th column is $col_i[]$ truncated to $m$.](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1283-L1287) |
| | | [Create array $c_{can}[R_2] = c[R_1...R_1+R_2)$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1038-L1041) |
| | | [Create array $c_{gcd}[R_3] = c[R_1+R_2...R_1+R_2+R_3)$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L10343-L1046) |
| | [Create array $\alpha'[7] = \{\tau_1,\tau_2,\ldots,\tau_6,4\}$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2481-L2488) | [Create array $\alpha'[7] = \{4,\tau_1,\tau_2,\ldots,\tau_6\}$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1038) |
| | | [Create array $\alpha_{comb} = \alpha_{CAN} \| \alpha'$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1072-L1081) |
| | Create array $prime_s[M]$: $prime_s[i]=[\mathrm{Reconstruct}(res[i],\alpha')]$ | |
| **Round 7** | Modulus reconstruction: compute prime shares modulo $\alpha_{CAN}$ using triples and then CRT-reconstruct the modulus together with $a[],b[]$ | |
| | [Create array $p_s[M/2]$ of even indices of $prime_s[]$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2557) | |
| | [Create array $q_s[M/2]$ of odd indices of $prime_s[]$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2558) | |
| | [Define $p_{scrt}[k] = p_s[k/6]\bmod \alpha_{CAN}[k\bmod 6]$, $k\leq R_2$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2571) | |
| | [Define $q_{scrt}[k] = q_s[k/6]\bmod \alpha_{CAN}[k\bmod 6]$, $k\leq R_2$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2572) | |
| | [Create array $ax[3M]$ as $ax[i] = p_s[i/6]-x_{can}[i] \bmod \alpha_{CAN}[i\bmod 6]$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2584) | |
| | [Create array $by[3M]$ as $by[i] = q_s[i/6]-y_{can}[i]\bmod \alpha_{CAN}[i\bmod 6]$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2584) | |
| | [$\rightarrow$ (AX_BY_SHARES,$ax$,$by$)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2601) | |
| | | Aggregate arrays [elementwise](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1091-L1102) $AX[j] = \sum_i ax_i[j]\bmod{\alpha_{CAN}[j\bmod 6]},$ $BY[j] = \sum_i by_i[j]\bmod{\alpha_{CAN}[j\bmod 6]}$, $1\leq j \leq M$ |
| | | $\Leftarrow$ [(AX_BY_VALUE, $AX,BY$)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1127) |
| **Round 8** | | |
| | [\begin{multline}axby[k] = AX[k]q_{scrt}[k]+BY[k]p_{scrt}[k]+z_{can}[k]\\\bmod{\alpha_{CAN}[k\bmod{6}]}, 1\leq k\leq R_2\end{multline}](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2622) | |
| | [$\rightarrow$ (AXB_MINUS_BYA_SHARES,$axby$)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2601) | |
| | | Aggregate vectors [elementwise](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1139-L1140) $AXBY[j] = \sum_i axby_i[j]$, $1\leq j \leq R_2$ |
| | | [Compute new vector ](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1157-L1163) \begin{multline}AB[k] = AXBY[k]+c_{can}[k]-AX[k]BY[k]\\\bmod{\alpha_{CAN}[k\bmod 6]}, k \leq R_2\end{multline} |
| | | [For each $i\leq min(M,3600)$ compute $x[j]=AB[6i+j],x[j'+6]=res[i][j']$, $j\leq 6, j'\leq 7$ and then set $N[i] = \mathrm{Reconstruct}(x[],\alpha_{comb})$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1180-L1188) |
| | | [Check that no candidate $N[i]$ is divisible by any of the first 127 primes, otherwise stop protocol ](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1189-L1200) |
| | | $\Leftarrow$ [(MODULUS_CANDIDATE, $N[]$) and write $N[]$ to transcript](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1215) |
| | [Store $N[]$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2651) | Abort if we have 0 candidates |
| | [$\rightarrow$ (SYNCHRONIZE_NOW,1)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2649) | |
| | [Check that $p_s[i]=q_s[i]=0\bmod{4}$ (for all parties but $P_1$; $=3\bmod{4}$ for $P_1$)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L717-L733) | [Check if any candidate is divisible by any of the first 100 primes, abort if any.](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1801-L1803) |
| | | [For every $N[i]$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1815) perform [Pollard $(p-1)$ algorithm to test for small factors](https://github.com/ligeroinc/LigeroRSA/blob/17d8b3d00604da1e0272035e871fac3add8d7551/include/Factoring.hpp#L1152-L1162) and compute array discardSieve[] |
| | | $\Leftarrow$ [(POST_SIEVE, discardSieve[])](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1817) and save discardFlags[] to the transcript |
| | [Remove $p_s[],q_s[],N[]$ entries that are discarded in discardSieve[]](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L745-L747)| [Remove N[] entries that are discarded in discardSieve[]](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1819) |
| **Round 9** | | |
| | | $\Leftarrow$ [(GAMMA_SHARES)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1521) |
| | [$\rightarrow$ (GAMMA_RANDOM_SEED_SHARES, $seed_1$)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2675) | |
| | | [Check if $seed_{1,i}$ matches $H(seed_{1,i})$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/Transport.hpp#L505-L520) |
| | | [Compute $\gamma_{seed} = XOR_i seed_{1,i}$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1524-L1530) |
| | | $\Leftarrow$ [(GAMMA_RANDOM_SEED_VALUE, $\gamma_{seed}$)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1537)|
| **Round 10** | | |
| | [Convert $\gamma_{seed}$ to 32-byte array s[]](https://github.com/ligeroinc/LigeroRSA/blob/17d8b3d00604da1e0272035e871fac3add8d7551/include/Math.hpp#L107-L122)| |
| | [Generate 256000-byte string using a ChaCha-based PRNG seeded with s[]](https://github.com/ligeroinc/LigeroRSA/blob/17d8b3d00604da1e0272035e871fac3add8d7551/include/Math.hpp#L124) and [interpret it as 1000 2048-bit integers $\gamma[]$](https://github.com/ligeroinc/LigeroRSA/blob/17d8b3d00604da1e0272035e871fac3add8d7551/include/Math.hpp#L126-L131) | |
| | [For every $i$ find smallest $i_j$ such that $\mathrm{Jacobi}(\gamma[i_j]\bmod{N[i]},N[i])=1$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2699-L2723) | |
| | [For every $i$ check that $\gamma[i_j]$ is coprime with $N[i]$ ](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2725-L2727) | |
| | [For every $i$ compute $exp[i]=\gamma[i_j]^{-p_s[i]-q_s[i]}\bmod{N[i]}$ (for $P_1$ compute $\gamma[i_j]^{N+1-p_s[i]-q_s[i]}\bmod{N[i]}$)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2740-L2764) | |
| | [$\rightarrow$ (EXPONENTIATED_GAMMA_VALUE,$exp[]$)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2770) | |
| | | [For every $j$ compute aggregated product $Exp[j] = \prod_i exp_i[j]$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1542-L1551) |
| | | [For every $j$ set discardJacobi[j]=1 if $Exp[j]=\pm 1 \bmod{N[j]}$ else set to 0](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1563-L1573) |
| | | $\Leftarrow$ [(DISCARD_FLAGS, discardJacobi[])](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1860) and save discardJacobi[] to the transcript |
| | | [Remove N[] entries that are discarded in discardJacobi[]](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1863) |
| **Round 11** | | |
| | | $\Leftarrow$ [(GCD_RAND_SHARES)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1310)|
| | [Set $p=p[1],q=q[1],N = N[1]$ ](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L794-L798) | |
| | [Let $s=1$ if $P_1$, otherwise 0.](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2837) | |
| | [Generate random 2048-bit $a$ and let aCRT[19] be its remainders by $\alpha_{GCD}[]$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2844-L2846) | |
| | [Let $bCRT[19]$ be remainders fo $( p+q-s)$ by $\alpha_{GCD}[]$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2851)| |
| | [For all $k\leq 19$ $ax'[k] = (aCRT[k]-x_{gcd}[k])\bmod{\alpha_{GCD}[k]}$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2859) | |
| | [For all $k\leq 19$ $by'[k] = (bCRT[k]-y_{gcd}[k])\bmod{\alpha_{GCD}[k]}$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2862) | |
| | [$\rightarrow$ (GCD_AX_BY_SHARES,$ax'[],by'[],seed_2$)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2770) | |
| | | [Check for every party $P_j$ if $seed_{2,j}$ matches $H(seed_{2,j})$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/Transport.hpp#L499-L529) |
| | | [Aggregate: \begin{align}AX'[j] = \sum_i ax_i'[j] \bmod{\alpha_{GCD}[j]},\\ BY'[j] = \sum_i by_i'[j]\bmod{\alpha_{GCD}[j]}, \\\gamma_{GCD} = XOR_j seed_{2,j}\end{align} ](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1335-L1364) |
| | | $\Leftarrow$ [(AX_BY_VALUE, $AX'[],BY'[],\gamma_{GCD}$)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1370) |
| **Round 12** | | |
| | [Generate 1000 2048-bit integers \gamma'[]](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2912) like for $\gamma[]$ | |
| | [Find $i_1,i_2,\ldots,i_{128}$ such that $\mathrm{Jacobi}(\gamma'[i_j]\bmod{N},N)=1$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2924-L2949) | |
| | [Check that $\gamma'[i_j]$ is coprime with $N$ for every $j$ ](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2952-L2955) | |
| | [Compute $exp'[j]=\gamma'[i_j]^{-p-q}\bmod{N}$ (for $P_1$ compute $\gamma'[i_j]^{N+1-p-q}\bmod{N}$)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2967-L2996) | |
| | [ Generate random 1234-bit $v$ and for every $k\leq 19$ compute \begin{multline} axby'[k]=AX'[k]bCRT[k]+BY'[k]aCRT[k]+\\+z_{GCD}[k]+v\cdot N[1]\bmod{\alpha_{GCD}[k]}\end{multline}](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L3012-L3017)| |
| | [$\rightarrow$ (AXB_MINUS_BYA_SHARES,$axby'[], exp'[]$)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L3029) | |
| | | [Aggregate: $AXBY'[k] = \sum_j axby_j[k]$, $EXP[j] = \prod_i exp_i'[j]$ ](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1388-L1397) |
| | | [For $k\leq 19$ compute $$z_{CRT}[k]=AXBY[k]+c_{GCD}[k]-AX'[k]BY'[k]\bmod{\alpha_{GCD}[k]}$$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1415-L1420) |
| | | [Compute $Z = \mathrm{Reconstruct}(z_{CRT}[],\alpha_{GCD}[])$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1436) |
| | | [If $Z$ is not co-prime with $N[1]$ set discardGCD=true else set to false](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1443-L1471) |
| | | [If for any $j$ $EXP[j]=N-1$ or $EXP[j]=1$ then discardJacobi=true else set to false](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1476-L1497)|
| | | $\Leftarrow$ [(DISCARD_FLAGS, DF=discardGCD OR discardJacobi)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1896) and save DF to the transcript |
| | [Remove the modulus if DF=true](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L823-L825) | [Remove the modulus if DF=true](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1903) |
| | | [If DF=true $\Leftarrow$ (FOUND_MODULI)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1915-L1921) else [$\Leftarrow$ (NO_MODULI)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1907-L1909)|
| | If FOUND_MODULI [select $N$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L878) | |

## Code flow

### Client

main->participate->participateHelper->start:
* [startHelper](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L612)
* [registerAndAwaitConfiguration](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2032-L2034)
* [start_rsa_ceremony](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L664)
* [generateKeyPair](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2130)
* [generatePreSievingShares](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2233)
* [pruneAndReorderShares](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2179)
* [crt_reconstruct](https://github.com/ligeroinc/LigeroRSA/blob/17d8b3d00604da1e0272035e871fac3add8d7551/include/Math.hpp#L419)
* [performModulusGeneration](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2531)
* [discardCandidates](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/Common.hpp#L1344)
* [performJacobiTest](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2666)
* generateRandomVector
* discardCandidates
* [performGCDandJacobiTest](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2791)
* discardCandidates

### Coordinator
* [registerAndHostRSACeremony](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1699)
* hostRegistration
* [host_rsa_ceremony](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1728)
* [hostGenerateKeyPair](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L35)
* [compute_m_b_vec](https://github.com/ligeroinc/LigeroRSA/blob/17d8b3d00604da1e0272035e871fac3add8d7551/include/Factoring.hpp#L1277)
* [hostPreSieving](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L848)
* balanced_bucket_n_primes
* fixed_bucket_n_primes
* [eval_poly](https://github.com/ligeroinc/LigeroRSA/blob/17d8b3d00604da1e0272035e871fac3add8d7551/include/LatticeEncryption.hpp#L412)
* [computeEITAndFlags](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L782)
* [pruneAndReorderEIT](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1249)
* [hostModulusCandidates ](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1058)
* [postSieve=test_factorizable_threaded](https://github.com/ligeroinc/LigeroRSA/blob/17d8b3d00604da1e0272035e871fac3add8d7551/include/Factoring.hpp#L1240)
* [test_factorizable_worker](https://github.com/ligeroinc/LigeroRSA/blob/17d8b3d00604da1e0272035e871fac3add8d7551/include/Factoring.hpp#L1240)
* [test_factorizable](https://github.com/ligeroinc/LigeroRSA/blob/17d8b3d00604da1e0272035e871fac3add8d7551/include/Factoring.hpp#L1188)
* [computeM](https://github.com/ligeroinc/LigeroRSA/blob/17d8b3d00604da1e0272035e871fac3add8d7551/include/Factoring.hpp#L1136)
* mpz_powm
* [discardCandidates](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/Common.hpp#L1344)
* [hostJacobiProtocol](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1516)
* [hostGCDandJacobiTest ](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedCoordinator.hpp#L1298)

### ZK proof
main-> [participate](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/src/party_full_protocol.cpp#L326)-> [participateHelper](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/src/party_full_protocol.cpp#L70)
* gatherData
* [produceArgumentOfKnowledge](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/ZkArgument.hpp#L1029)
* [buildConstraintSet](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/protocol/ExpressNPStatement.hpp#L4225) (for first 9 moduli)
* Preprocessing
* [NP_RSARound3_keyGen](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/protocol/ExpressNPStatement.hpp#L402)
* NP_RSARound4_preSieving
* NP_RSARound5_preSieving
* NP_RSARound6_partialDecrypt
* NP_RSARound7_candidateGeneration
* NP_RSARound8_beaversTriples
* NP_RSARound11_12_jacobiGCD
* NP_Stitching
* NP_Connecting_Proofs
* NP_Equate_Variables
* NP_RSACeremony_Bounding_Variables
* [buildConstraintSet](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/protocol/ExpressNPStatement.hpp#L4225) (for other 12 moduli)
* Preprocessing
* [NP_RSARound3_keyGen](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/protocol/ExpressNPStatement.hpp#L402)
* NP_RSARound4_preSieving
* NP_RSARound5_preSieving
* NP_RSARound6_partialDecrypt
* NP_Stitching

| | Client $P_i$ |
| -------- | -------- |
| | [Let $I[] = \{I^P_1,I^P_2,\ldots,I^P_6,I^C,I^C+1,\ldots,I^C+5,65517,65518,\ldots,65535\}$ be the set of indices of triples that are used for the found modulus (6 from PS, 6 from CAN, 19 from PS)](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L876). Let $I_0$ be the index of candidate selected in $N[]$ so that $I^C = 6I_0+R_1$|
| **Round 3** | |
| | [Compute $l = A\cdot s +e-b$ as a polynomial of degree $2n$]((https://github.com/ligeroinc/LigeroRSA/blob/5ae78c85c836813190b636ed838f8c8523ce9bd3/include/EncryptedClient.hpp#L1034-L1037)) |
| | [Get $q_3 = l/(x^n+1)$ in Q-CRT form](https://github.com/ligeroinc/LigeroRSA/blob/5ae78c85c836813190b636ed838f8c8523ce9bd3/include/EncryptedClient.hpp#L1042) |
| **Round 4** | |
| | [Compute $l = u_x\cdot A +v_x -E_x^1$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L1071-L1077) |
| | [Get $q_{4,1} = l/(x^n+1)$ in Q-CRT form](https://github.com/ligeroinc/LigeroRSA/blob/5ae78c85c836813190b636ed838f8c8523ce9bd3/include/EncryptedClient.hpp#L1081) |
| | [Set $x' = InvNTT(poly(x[]))$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L1056-L1059) |
| | [Compute $l = u_x\cdot b +w_x +x'-E_x^2$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L1096-L1101) |
| | [Get $q_{4,2} = l/(x^n+1)$ in Q-CRT form](https://github.com/ligeroinc/LigeroRSA/blob/5ae78c85c836813190b636ed838f8c8523ce9bd3/include/EncryptedClient.hpp#L1105) |
| **Round 5** | |
| | [Compute $l = y'\cdot EX^1 -u_z\cdot A -v_z-E_x^1$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L1147-L1158) |
| | [Get $q_{5,1} = l/(x^n+1)$ in Q-CRT form](https://github.com/ligeroinc/LigeroRSA/blob/5ae78c85c836813190b636ed838f8c8523ce9bd3/include/EncryptedClient.hpp#L1162) |
| | [Compute $l = y'EX^2 +z_p-b\cdot u_z -w_z-z'-E_x^2$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L1180-L1191) |
| | [Get $q_{5,2} = l/(x^n+1)$ in Q-CRT form](https://github.com/ligeroinc/LigeroRSA/blob/5ae78c85c836813190b636ed838f8c8523ce9bd3/include/EncryptedClient.hpp#L1195) |
| **Round 6** | |
| | [Compute $l = r-p_{xyz}- EXYZ.1\cdot s$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L1215-L1220) |
| | [Get $q_{6} = l/(x^n+1)$ in Q-CRT form](https://github.com/ligeroinc/LigeroRSA/blob/5ae78c85c836813190b636ed838f8c8523ce9bd3/include/EncryptedClient.hpp#L1228) |
| **Round 7** | |
| Store secrets | |
| | [$x_i\leftarrow x'$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L1444)|
| | [x_sharesCAN$[N_Q]\leftarrow x[i_0]\bmod \alpha_{CAN}$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L1479-L1480)|
| | [x_sharesPS$[N_Q]\leftarrow x[i_0]\bmod \alpha_{PS}$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L1479-L1480)|
| | [x_sharesGCD$[N_Q]\leftarrow x[i_0]\bmod \alpha_{GCD}$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L1624)|

### NP-statement

Range proofs:
$$
Vars[i]<d[i]
$$ is transformed to
$$
Vars[i]\pmod{P[j]} < d[i]\pmod{P[j]}
$$
Then
$$
X <dd
$$
is converted to $X+C <D=2^{log2D}$.

`Vars`= $x[I[]]||y[I[]]||z[I_{CAN}]||z_p||r$

Public inputs:
* `modulusIdx` = index of the number in the prime decomposition of $Q$, modulo which we create a proof.
* `A`$=A$;
* `bi`$=b$;
* `ci_1`=$E_x^1$
* `ci_2`=$E_x^2$
* `b` $=B$;
* `ci_1_prime` = $E_{xyz}^1$;
* `ci_2_prime` =$E_{xyz}^2$.
* `c_1` $= EX^1$;
* `c_2` $= EX^2$;
* `special` -- if party is $P_1.$
* `di` $=p_{xyz}$.
* `c_1_prime` $=EXYZ.1$.
* `c_2_prime` $=EXYZ.2$.
* `coefsCAN` $= N\bmod{\alpha_{CAN}[]}$ (elementwise).
* `cans` $=\alpha_{CAN}[]||\alpha_{PS}[]||\alpha_{GCD}[]$
* `prodcans` $=(4\cdot\prod_i\alpha_{PS}[i])\mod{\alpha_{CAN}[]}$
* `indicesPS` $=I[]\cap [<R_1]$ (PS indices)
* `indicesCAN` $=I[]\cap [R_1;R_1+R_2)$ (CAN indices)
* `indicesGCD` $=I[]\cap [R_1+R_2;R_1+R_2+R_3)$ (GCD indices)
* `by_shares` $=by[]$.
* `ax_shares` $=ax[]$.
* `ax` $=AX[6I_0..6I_0+5]$;
* `by` $=BY[6I_0..6I_0+5]$;
* `axby` $=AXBY[6I_0..6I_0+5]$;
* `q_r8` $=B$;
* `Cs`, `Ds`, `log2Ds`: range proof parameters. $=C[],dd[]$
* `by_shares_GCD` $=?$
* `ax_shares_GCD` $=?$
* `finalModuli_GCD` $=N\pmod{\alpha_{GCD}[]}\pmod{P[i]}$
* `coefsGCD` $= N\pmod{\alpha_{GCD}[]} $
* `gcds` $=\alpha_{GCD}$;
* `prodgcds`
* `axGCD`
* `byGCD`
* `axbyGCD`

Secret inputs (`sdata`) and their witness assignments (=):
* `eiP` $= e\in \mathbb{B}^{64}[]$, [gets transformed to $e_i$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/protocol/ExpressNPStatement.hpp#L4679-L4681);
* `siP` $=s[]$;
* `q_r3` $=q_3$;
* `ux` $=u_x$;
* `vx` $=v_x$;
* `wx` $=w_x$;
* `uz` $=u_z$;
* `vz` $=v_z$;
* `wz` $=w_z$;
* `xi` $=x' = poly(x[])$. Seems to be used in one constraint only
* `yi` $=y' = poly(y[])$
* `zi` $=z' = poly(z[])$
* `q_r4_1` $=q_{4,1}$;
* `q_r4_2` $=q_{4,2}$;
* `vxP` is subset $v_{x_0}$ of $v_x$ values based on $I[]$.
* `wxP` is subset $w_{x_0}$ of $w_x$ values based on $I[]$.
* `vzP` is subset $v_{z_0}$ of $v_z$ values based on $I[]$.
* `wzP` is subset $w_{z_0}$ of $w_z$ values based on $I[]$.
* `q_r5_1` $=q_{5,1}$;
* `q_r5_2` $=q_{5,2}$;
* `zp`$=z_p$;
* `rNoise`= $r$ (from PartDecrypt).
* `q_r6` $=q_{6}$;
* `x_sharesPS` is subset $x_{PS}$ of $x[]$ values from PS triples based on $I[]$.
* `x_sharesCAN` is subset $x_{CAN}$ of $x[]$ values from CAN triples based on $I[]$.
* `y_sharesPS` is subset $y_{PS}$ of $y[]$ values from PS triples based on $I[]$.
* `y_sharesCAN` is subset $y_{CAN}$ of $y[]$ values from CAN triples based on $I[]$.
* `z_sharesCAN` is subset $z_{CAN}$ of $z[]$ values from CAN triples based on $I[]$.
* `q_p_prod_r7` $=?$;
* `q_p_r7` $=?$;
* `q_q_prod_r7` $=?$;
* `q_q_r7` $=?$;
* `q_r8` $=?$;
* `XplusCs`,`XplusDs`,`Xs`: bit decompositions for range proofs $=(X+C)[],(X+dd)[],(X)[]$
* `q_p_prod_r11` $=?$;
* `q_pq_r11` $=?$;
* `q_q_prod_r11` $=?$;
* `q_r_r11` $=?$;
* `r_CRTs` $=aCRT[]\pmod{P[]}$
* `q_r12` $=?$
* `ss_GCD` $= v\pmod{\alpha_{GCD}[]}\pmod{P[i]}$
* `y_sharesGCD` $=y[GCD]$
* `x_sharesGCD` $= x[GCD]$
* `z_sharesGCD` $=z[GCD]$;
* `sigmarGCD` $=\sigma_{r,GCD}$;
* `sigmaxGCD` $=sigma_x_GCD())$;
* `expqGCD` $=exp_q_GCD())$;
* `sigmaqGCD` $=sigma_q_GCD())$;

Sigma protocol:
* `sigmazGCD` $sigma_z_GCD())$;
* `sigmaeGCD` $=sigma_e_GCD())$;
* `sigmaaGCD` $=sigma_a_GCD())$;
* `sigmagGCD` $=sigma_g_GCD())$;

Constraints:
#### `NP_RSARound3_keyGen`:

We split $e,s$ into 21 variables each and bound the first ones only

[Bounding](https://github.com/ligeroinc/LigeroRSA/blob/f21fb37b8518334e9e646cca31726068cbe50a92/include/protocol/ExpressNPStatement.hpp#L1679-L1687)
$$
e_0<10
\sigma;\quad s_0<10\sigma
$$

[Store $s$ in variable `_siBlocs` and $e$ in `_eiBlocs`](https://github.com/ligeroinc/LigeroRSA/blob/f21fb37b8518334e9e646cca31726068cbe50a92/include/protocol/ExpressNPStatement.hpp#L3397-L3398)

[Public key share generation](https://github.com/ligeroinc/LigeroRSA/blob/f21fb37b8518334e9e646cca31726068cbe50a92/include/protocol/ExpressNPStatement.hpp#L1711-L1722):
$$
A(x_j)s(x_j)+e(x_j)-b(x_j)=q_3(x_j)(x_j^n+1)
$$
for each of three $x_j$ and 21 moduli. All further polynomial checks will be done this way.

#### `NP_RSARound4_preSieving`:
* [Ciphertext-1](https://github.com/ligeroinc/LigeroRSA/blob/f21fb37b8518334e9e646cca31726068cbe50a92/include/protocol/ExpressNPStatement.hpp#L3410-L3423)

$$
E_x^1 +q_{4,1}\cdot (x^n+1) = A\cdot u_x+v_x
$$

[Bounding](https://github.com/ligeroinc/LigeroRSA/blob/f21fb37b8518334e9e646cca31726068cbe50a92/include/protocol/ExpressNPStatement.hpp#L3385-L3387)
$$
u_{x_0}<10 \sigma
$$

[Store $u_x$ in variable `_uxBlocs` and $v_x$ in `_vx_blockIndices `](https://github.com/ligeroinc/LigeroRSA/blob/f21fb37b8518334e9e646cca31726068cbe50a92/include/protocol/ExpressNPStatement.hpp#L3397-L3398)

* [Ciphertext-2](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/protocol/ExpressNPStatement.hpp#L533-L535)
$$
E_x^2 +q_{4,2}\cdot (x^n+1) = b\cdot u_x+w_x+x'
$$

`_uxBlocs` is not used?!!!

[Store $x'$ in `_xprimeIds` and $w_x$ in `_wx_blockIndices`](https://github.com/ligeroinc/LigeroRSA/blob/f21fb37b8518334e9e646cca31726068cbe50a92/include/protocol/ExpressNPStatement.hpp#L3506-L3507)

* [Encryption bounds](https://github.com/ligeroinc/LigeroRSA/blob/f21fb37b8518334e9e646cca31726068cbe50a92/include/protocol/ExpressNPStatement.hpp#L573-L583):
$$
v_{x_0} < 10\cdot \sigma; \quad w_{x_0} <10\cdot \sigma.
$$

#### `NP_RSARound5_preSieving`:
* [Encryption](https://github.com/ligeroinc/LigeroRSA/blob/f21fb37b8518334e9e646cca31726068cbe50a92/include/protocol/ExpressNPStatement.hpp#L3764-L3777)
$$
E_{xyz}^1 +q_{5,1}\cdot (x^n+1) = EX^1\cdot y' -A\cdot u_z-v_z
$$

[Store $u_z$ in variable `_uzBlocs`, $y'$ in `_yprimeIds`, and $v_z$ in `_vz_blockIndices `](https://github.com/ligeroinc/LigeroRSA/blob/f21fb37b8518334e9e646cca31726068cbe50a92/include/protocol/ExpressNPStatement.hpp#L3743-L3751)

* [Encryption-2](https://github.com/ligeroinc/LigeroRSA/blob/f21fb37b8518334e9e646cca31726068cbe50a92/include/protocol/ExpressNPStatement.hpp#L3896-L3913)
$$
E_{xyz}^2 +q_{5,2}\cdot (x^n+1)= EX^2\cdot y' - b\cdot u_z + z_p-w_z-z'
$$

[Store $z'$ in variable `_zprimeIds`, and $w_z$ in `_wz_blockIndices `](https://github.com/ligeroinc/LigeroRSA/blob/f21fb37b8518334e9e646cca31726068cbe50a92/include/protocol/ExpressNPStatement.hpp#L3882-L3883)

`_uzBlocs` and `_yprimeIds` are not used?!!!

[Bounding](https://github.com/ligeroinc/LigeroRSA/blob/f21fb37b8518334e9e646cca31726068cbe50a92/include/protocol/ExpressNPStatement.hpp#L3736-L3738)
$$
u_{z_0}<10 \sigma
$$

* [Encryption bounds](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/protocol/ExpressNPStatement.hpp#L707-L736):
$$
v_{z_0} \leq 10\cdot \sigma; \quad w_{z_0} \leq 10\cdot \sigma.
$$

#### `NP_RSARound6_partialDecrypt`:
* [Partial decryption](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/protocol/ExpressNPStatement.hpp#L765)
$$
p_{xyz} +q_{6}\cdot (x^n+1) = EXYZ.2-s\cdot EXYZ.1 +r
$$

We do not use `_siBlocs`!

#### `NP_RSARound7_candidateGeneration`

Here $p_s$ is the prime share and $B_1,B_2,\ldots,B_6$ is its decomposition modulo $\alpha_{PS}[]$. We have 6 equations ($0\leq i \leq 5$):
$$
ax[i] = p_s-x_{can}[i] \bmod \alpha_{CAN}[i]
$$
This transforms to
$$
ax[i]+x_{can}[i] = D[i]-E[i] \alpha_{CAN}[i] + q[i]\alpha_{CAN}[i]
$$
where
$$
D[i] = \sum_{j}A_j^i B_j;\quad E[i] = \lfloor D[i]/\alpha_{CAN}[i]\rfloor;\quad q[i]<3\quad E[i]<7
$$
for some coefficients $A_j^i$.

The same for $q_s$ with $C_c$ instead of $B_c$.

References to variables $B_c,x_{can}[],C_c,y_{can}[]$ are returned and stored in `_xsharesPSidxs `, `_xsharesCANidxs`, `_ysharesPSidxs`, `_ysharesCANidxs`.

#### `NP_RSARound8_beaversTriples`

Similar to round 7 but with bigger equation. We create another set of variables for $B_c,C_c$ which are stored in `_xsharesPSidxs_2`, `_ysharesPSidxs_2`. We store $z_{can}[]$ in `_zsharesCANidxs`.

We also allocate variables for $W_1,W_2,W_3,\alpha$ and store them in `_stitchingVariables`.

#### `NP_RSARound11_12_jacobiGCD`

[We create another set of variables for $B_c,C_c$ which are stored in `_xsharesPSidxs_3`, `_ysharesPSidxs_3`.](https://github.com/ligeroinc/LigeroRSA/blob/f21fb37b8518334e9e646cca31726068cbe50a92/include/protocol/ExpressNPStatement.hpp#L2400-L2403)

[We store `x_sharesGCD`in `_xsharesGCDidxs` and `y_sharesGCD` in `_ysharesGCDidxs`.](https://github.com/ligeroinc/LigeroRSA/blob/f21fb37b8518334e9e646cca31726068cbe50a92/include/protocol/ExpressNPStatement.hpp#L2404-L2411)

[We create yet another set of variables for $B_c,C_c$ which are stored in `_xsharesPSidxs_4`, `_ysharesPSidxs_4`.](https://github.com/ligeroinc/LigeroRSA/blob/f21fb37b8518334e9e646cca31726068cbe50a92/include/protocol/ExpressNPStatement.hpp#L2725-L2728)

[We create $128\cdot 6$ constraints](https://github.com/ligeroinc/LigeroRSA/blob/f21fb37b8518334e9e646cca31726068cbe50a92/include/protocol/ExpressNPStatement.hpp#L3275-L3304):
$$
\sigma_{x,GCD}[j]\sigma_{e,GCD}[i]+\sigma_{r,GCD}[j] + \alpha_{GCD}[i] \sigma_{q,GCD}[j]= \sigma_{z,GCD}
$$

#### `NP_Stitching`

UNclear what happens there

#### `NP_Connecting_Proofs`
* [Check that `_xprimeIds` matches `_xsharesPSidxs`, `_xsharesCANidxs`, `_xsharesGCDidxs`.](https://github.com/ligeroinc/LigeroRSA/blob/f21fb37b8518334e9e646cca31726068cbe50a92/include/protocol/ExpressNPStatement.hpp#L1218-L1226)
* [Check that `_yprimeIds` matches `_ysharesPSidxs`, `_ysharesCANidxs`, `_ysharesGCDidxs`.](https://github.com/ligeroinc/LigeroRSA/blob/f21fb37b8518334e9e646cca31726068cbe50a92/include/protocol/ExpressNPStatement.hpp#L1227-L1236)
* [Check that `_zprimeIds` matches `_zsharesCANidxs` .](https://github.com/ligeroinc/LigeroRSA/blob/f21fb37b8518334e9e646cca31726068cbe50a92/include/protocol/ExpressNPStatement.hpp#L1239)

Then ???????

#### `NP_Equate_Variables`

* [Check that `_xsharesPSidxs`=`_xsharesPSidxs_2` =`_xsharesPSidxs_3` = `_xsharesPSidxs_4`](https://github.com/ligeroinc/LigeroRSA/blob/f21fb37b8518334e9e646cca31726068cbe50a92/include/protocol/ExpressNPStatement.hpp#L467-L494)
* [Check that `_ysharesPSidxs`=`_ysharesPSidxs_2` =`_ysharesPSidxs_3` = `_ysharesPSidxs_4`](https://github.com/ligeroinc/LigeroRSA/blob/f21fb37b8518334e9e646cca31726068cbe50a92/include/protocol/ExpressNPStatement.hpp#L496-L524)

#### `NP_RSACeremony_Bounding_Variables`:
Enforce boundary constraints for all variables to be bound:
\begin{align}
B[i]+C[i]\
\end{align}

## What happens in rounds 6-8
Notation:
* $[A]_{\text{parties}}$ -- number $A$ secretshared among the parties.
* $[A]_{PS}$ -- number $A$ represented as a set of remainders modulo values $\alpha_{PS}$.
* $[A]_{CAN}$ -- number $A$ represented as a set of remainders modulo values $\alpha_{CAN}$.

For all $k$:
\begin{align}
[X]_{\text{parties}} &= x_{can};\\
[Y]_{\text{parties}} &= y_{can};\\
C&=X\cdot Y -Z;\\
[p_s]_{PS} &= A[k,k+w_1,k+w_1+w_2\ldots k+w_1+w_2+w_3+w_4+w_5]\\
[q_s]_{PS} &= B[k,k+w_1,k+w_1+w_2\ldots k+w_1+w_2+w_3+w_4+w_5]
\end{align}

Group of 6:
\begin{align}
[p_s]_{CAN} &= p_{sc}[k..k+5];\\
[q_s]_{CAN} &= q_{sc}[k..k+5];\\
\mathbf{AX} &= [p_s]_{CAN} - \mathbf{X}\\
\mathbf{BY} &=[q_s]_{CAN} - \mathbf{Y}\\
\mathbf{AXBY} &=\mathbf{AX}\odot [q_s]_{CAN} +\mathbf{BY}\odot [p_s]_{CAN} +\mathbf{Z}\\
\mathbf{AB} &=\mathbf{AXBY} + \mathbf{C} - \mathbf{AX}\odot \mathbf{BY}=\\
& = \mathbf{AX}\odot [q_s]_{CAN} +\mathbf{BY}\odot [p_s]_{CAN} +\mathbf{Z} + \mathbf{C} - ( [p_s]_{CAN} - \mathbf{X})\odot ([q_s]_{CAN} - \mathbf{Y})=\\
&= ([p_s]_{CAN} - \mathbf{X})\odot [q_s]_{CAN} +([q_s]_{CAN} - \mathbf{Y})\odot [p_s]_{CAN} +\mathbf{Z} + \mathbf{C} - ( [p_s]_{CAN} - \mathbf{X})\odot ([q_s]_{CAN} - \mathbf{Y})=\\
&=([p_s]_{CAN} - \mathbf{X})\odot [q_s]_{CAN} +\mathbf{Z} + \mathbf{C}
+\mathbf{X}\odot ([q_s]_{CAN} - \mathbf{Y})=\\
&=[p_s]_{CAN} \odot [q_s]_{CAN} +\mathbf{Z} +\mathbf{X}\mathbf{Y}-\mathbf{Z}-\mathbf{X}\mathbf{Y}=\\
&=[p_s]_{CAN} \odot [q_s]_{CAN} = [N]_{CAN}.
\end{align}

## Rounds 11-12
\begin{align}
[a]_{GCD} &= aCRT[1..19];\\
[p+q-s]_{GCD} &= bCRT[1..19];\\
\mathbf{AX}' &= [a]_{GCD} - \mathbf{X}\\
\mathbf{BY}' &=[p+q-s]_{GCD} - \mathbf{Y}\\
\mathbf{AXBY}' &=\mathbf{AX}'\odot [p+q-s]_{GCD} +\mathbf{BY}'\odot [a]_{GCD} +\mathbf{Z}+[V]_{GCD}\odot[N]_{GCD}=\\
&= ([a]_{GCD} - \mathbf{X})\odot [p+q-s]_{GCD} +([p+q-s]_{GCD} - \mathbf{Y})\odot [a]_{GCD} +\mathbf{Z} + [V]_{GCD}\odot[N]_{GCD}\\
\mathbf{ZC}&= \mathbf{AXBY}'+ \mathbf{C}- \mathbf{AX}'\mathbf{BY}'=\\
&=([a]_{GCD} - \mathbf{X})\odot [p+q-s]_{GCD} +([p+q-s]_{GCD} - \mathbf{Y})\odot [a]_{GCD} +\mathbf{Z} + [V]_{GCD}\odot[N]_{GCD}+\mathbf{X}\mathbf{Y}-\mathbf{Z} - ([a]_{GCD} - \mathbf{X})([p+q-s]_{GCD} - \mathbf{Y})=\\
&=([p+q-s]_{GCD} - \mathbf{Y})\odot [a]_{GCD} +\mathbf{Z} + [V]_{GCD}\odot[N]_{GCD}+\mathbf{X}\mathbf{Y}-\mathbf{Z} + ([a]_{GCD} - \mathbf{X})\mathbf{Y}=\\
&= [p+q-s]_{GCD} \odot [a]_{GCD} +\mathbf{Z} + [V]_{GCD}\odot[N]_{GCD}+\mathbf{X}\mathbf{Y}-\mathbf{Z} - \mathbf{X}\mathbf{Y}=\\
&=[p+q-s]_{GCD} \odot [a]_{GCD} + [V]_{GCD}\odot[N]_{GCD}
\end{align}

## MAC

| | Prover | Verifier |
| -------- | -------- | -------- |
| Round 1 | | |
| | Sample $W_1$, $W_2$, $W_3$ from $F_{p_1}$ | |
| | Send a commitment to $(s,e,u_x,u_z,W_1,W_2,W_3)$ to the verifier. | |
| | | Sample random vector $r$ and send to the prover. |
|Round 2 | | |
| | Compute $\mu = (s, e, u_x, u_z, W) \odot r \bmod{p_1}$ | |
| | Sample random $\alpha<2^{210}$ | |
| | Compute $\mu’ = \mu + \alpha p_1$ over the integers.| |
| | Send $(\mu, \mu')$ and a commitment to $\alpha$ to the verifier. | |
| | Create a Ligero proof $\pi$ that $(\mu, \mu_2, \ldots, \mu_{21}) = ((s,e,u_x, u_z, W) \odot r + \alpha p_1\bmod{p_1}, \ldots, (s,e,u_x, u_z, W) \odot r + \alpha p_1\bmod{p_{21}})$ | |
| | | Compute $\mu_2, \ldots , \mu_{21}$ by taking the relevant modulos.|
| | | Check $\pi$ using $\mu,\mu_2, \ldots , \mu_{21}$ |
| | | Check $\mu' \bmod{p_1} = \mu$.|
| | | |
| | | |

<!-- ## Sampling

| What | Where | ZK-Verified | Ideal |
| - | - | - | - |
| Triple $(a_j,b_j,c_j)$ | $\Pi_{ctriple}$, Input phase | ''consistent with $R_j$'' (Figure 4), but no NP-statement | Random pair $(\sum_j a_j,\sum_j b_j)$ |
| Randomness $R_j$ | $\Pi_{ctriple}$, Commit phase | - | - |
| Random $r_j$ (is it the secret key below?) | Figure 4, THE phase | ? | |
| [Encryption secret key $s_i,e_i$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2039-L2040) | RLWE key generation (page 29, l.40) | Only a certain range (page 34 line 15) | Gaussian |
| [Encryption secret key $a_i$](https://github.com/ligeroinc/LigeroRSA/blob/15a5950db39fbdfe9f95de382c4602dc5a2e5fd7/include/EncryptedClient.hpp#L2101) | RLWE key generation (page 29, l.39) | - | Uniform |
| Triple mask $z_j$ | $\Pi_{ctriple}$, input phase | Only a certain range (page 34 line 25) | Uniform |
| Encryption randomness $u,v,w$ for encryption and addition | $\Pi_{ctriple}$, triples phase | Knowledge (page 34 lines 25-27) | Uniform |
| Decryption randomness $r$ for distributed decryption | $\Pi_{ctriple}$, triples phase | Knowledge and range (page 34 line 35) | |
| Subprime residue $r_{i,t}^j, \tilde r_{i,t}^j$ | $\Pi_{RSA}$, pre-sieving | Knowledge (page 34 line 37) | Random |
| Gamma share $\gamma_{i}^j$ | $\Pi_{RSA}$, Jacobi | ? (page 35 line 3) | Random |
| GCD share $a_{i}^j$ | $\Pi_{RSA}$, GCD | ? (page 35 line 8) | Random |
-->