# LMKC++ Non-interative key gen

Let $s = \sum s_{i}$, $m = \sum m_{i}$, $u = \sum u_{i}$. We seek to generate $\textsf{RLWE}_{s}(-sm)$ from $\textsf{RLWE}_{s_{i}}(-sm_{i})$.

Let $a$ and $[a_{1}, \dots, a_{j}]$ be common reference polynomials derived from a public seed.

## Offline Setup

$P_{i}$ sends to the server:
- $\textsf{RLWE}_{u_{i}}^{a}(m_{i}) = [(au_{i}+m_{i}+e)]_{QP}$ where $u\leftarrow\chi_{sk}$
- $\textsf{GRLWE}_{s_{i}}^{a_{j}}(u_{i}) = [(-a_{1}s_{1}+ P'\cdot \mathbf{w}_{1}\cdot u_{i}+e), \dots, (-a_{j}s_{1}+P'\cdot\mathbf{w}_{j}\cdot u_{i}+e)]_{QPP'}$
- $\textsf{RLWE}_{s_{i}}^{a}(0) = [(-as_i+e)]_{QP}$

## Online Setup

1. The serveur computes:

$$
\begin{align}
&\textsf{GRLWE}_{s}^{a_{j}}(u)\\
=\ & \sum\textsf{GRLWE}_{s_{i}}^{a_{j}}(u_{i})\\
=\ & [(-a_1s+P'\cdot \mathbf{w}_{1}\cdot u+e), \dots, (-a_js+P'\cdot \mathbf{w}_{1}\cdot u+e)]_{QPP'}
\end{align}
$$

2. The serveur computes:
$$
\begin{align}
& \textsf{RLWE}_{s}^{a}(0)\\
=\ & \sum \textsf{RLWE}_{s_{i}}^{a}(0)\\
=\ &[(-as+e)]_{QP}
\end{align}
$$
3. The serveur computes:
$$
\begin{align}
& \textsf{RLWE}_{s}^{b}(u(-as+e))\\
=\ & \lceil P'^{-1}\cdot\left\langle\mathbf{w}^{-1}(\textsf{RLWE}_{s}^{a}(0)), \textsf{GRLWE}_{s}^{a_{j}}(u)\right\rangle\rfloor\\
=\ & \lceil P'^{-1}\cdot\sum \mathbf{w}_{j}^{-1}(-as+e) \cdot (-a_js+P'\cdot\mathbf{w}_{j}\cdot u+e, a_{j})\rfloor\\
=\ & [(-bs + u(-as+e)+ e, b)]_{QP}
\end{align}
$$
4. Finally, the server computes:
$$
\begin{align}
& \textsf{RLWE}_{s}^{c}(-sm)\\
=\ & \textsf{RLWE}_{s}^{b}(-u(as+e)) + \sum (0, \textsf{RLWE}_{u_{i}}^{a}(m_{i})[0])\\
=\ & (-bs - u(as+e)+ e, b) + (0, au+m+e) \\
=\ & (-s(b+ua) + e, b+ua+m+e)\\
=\ & [(-sc + e, c + m + e)]_{QP}
\end{align}
$$