# Non-interactive PBS key gen

<!-- Let $\gamma$ be the publicly known main seed. Set no. of parties to P.

Sample party specific seeds $\gamma_i$ from $\gamma$ for $i \in [0, P)$.
Sample routine specific seeds
1. $\gamma_{ksk(s^2 \to s)}$: Seed used to generate collecrtive key switching key $s^2 \to s$.
2. dwd

**Key generation party j**

1. Generate RLWE secrets $s_j, u_j$, LWE secret $\hat{s_j} and ephemeral secret $u'_j$.

2. Generate shares for $ksk(s^2 \to s)$:
1. Sample $a_0, ..., a_{i-1}, a'_i, ..., a'_{i-1}$ from pseudo random generator seeded with $\gamma_{s^2 \to s}$
2. For $i$ in $0..d-1$ generate:
$$
(a_iu'_j + e - \beta^i s_j, a_i s_j + e)
$$
3. For i in 0..d-1 generate:
$$
a'_is_j + e + \beta^iu'_j
$$
3. Generate shares for $ksk(u_j \to s)$:
1. Sample $a''_{0, j}, a''_{1,j}, ..., a''_{d-1,j}$ from pseudo random generated seeded with $\gamma_{j}$
2. For i in 0..d-1 generate
$$a''_is_j + e + \beta_iu_j$$
4. Generate zero encryptions:
Define set $P_j = [i \in 0..P; i\neq j]$.

For i in P_j
1. Sample $a''_{0, i}, a''_{1, i}, ..., a''_{d-1, i}$ from $\gamma_i$
2. For k in 0..d-1:
$$(a''_{k, i}s_j + e)$$

5. Generate RGSW shares:
For i in 0..n
1. Sample random $a_i$
2. Generate $(a_i u_j + e + X^{\hat{s}[i]}, a_i, a_is_j+e)$

## Server

Server receives bootstrapping key shares $K_0, K_1, ..., K_{j-1}$ from all parties.

### Generate ksk(s^2 \to s)

To generate ksks^2 to s, sever aggregates shares of ksk(s^2 \to s)

1. For $i$ in $0..d-1$ aggregate:
$$
a_iu' + e - \beta^is = \sum_{j}^P a_iu'_j + e - \beta^i s_j
$$
2. For $i$ in $0..d-1$ aggregate:
$$
a_i s + e = \sum_{j=0}^P a_i s_j + e
$$
3. For $i$ in $0..d-1$ aggregate:
$$
a'_is + e + \beta^i u' = \sum_{j=0}^P a'_is_j + e + \beta^iu'_j
$$

4. For i in 0..d-1, server generates $RLWE(a_isu')$ as
$$RLWE(a_isu') = decomp<a_is + e> \cdot a'_is + e + \beta^i u'$$
5. Set ksk(s^2 \to s):
$$ksk(s^2 \to s) = [RLWE(a_isu') + (0, a_iu + e - \beta^is)]$$

### Generate ksk(u_j \to s)

For party j server generates $ksk(u_j \to s)$:

1. For i in $0..d-1$:
$$
a''_{i, j}s + e + \beta_iu_j = a''_{i, j} s_j + e + \beta_iu_j + \sum_{k \in P_j} a''_{i, j}s_k + e
$$
2. Set ksk as:
$$[RLWE_s(\beta^iu_j)] = [a''_{i, j}s + e + \beta_iu_j, a''_{i, j}]$$

### Generate $RGSW(\beta_k X^{\hat{s}[i]})$
1. Key switch $(a_i u_j + e + \beta^k X^{\hat{s}[i]}, a_i)$ from u_j \to s:

$$RLWE(-a_iu_j) = decomp<-a_i> \cdot [RLWE_s(\beta^iu_j)]$$

$$RLWE(\beta^k X^{\hat{s}[i]}) = (a_i u_j + e + \beta^k X^{\hat{s}[i]}, 0) + RLWE(-a_iu_j)$$
2. Key switch $RLWE(\beta^k X^{\hat{s}[i]})$ to $RLWE(-s\beta^k X^{\hat{s}[i]})$ using $ksk(s^2 \to s)$

Let $RLWE(\beta^k X^{\hat{s}[i]}) = (\hat{a}s + e + \beta^k X^{\hat{s}[i]}, \hat{a})$

Key switch $\hat{a}$:
$$RLWE(\hat{a}s^2) = decomp<\hat{a}> \cdot Ksk(s^2 \to s)$$

Set
$$RLWE(-s\beta^kX^{\hat{s}[i]}) = RLWE(\hat{a}s^2) + (0, \hat{a}s + e + \beta^k X^{\hat{s}[i]})$$

------
------ -->

Let $\gamma$ be the publicly known main seed. Set no. of parties to P.

Sample party specific seeds $\gamma_i$ from $\gamma$ for $i \in [0, P)$.
Sample key specific seeds \gamma_{k},

**Key generation party j**

1. Generate RLWE secrets $s_j, u_j$, LWE secret $\hat{s_j}.
2. Generate shares for $ksk(u_j \to s)$:
1. Sample $a''_{0, j}, a''_{1,j}, ..., a''_{d-1,j}$ from pseudo random generated seeded with $\gamma_{j}$
2. For i in 0..d-1 generate
$$a''_{i, j}s_j + e + \beta_iu_j$$
4. Generate zero encryptions:

Define set $P_j = [i \in 0..P; i\neq j]$.

For i in P_j
1. Sample $a''_{0, i}, a''_{1, i}, ..., a''_{d-1, i}$ from $\gamma_i$
2. For k in 0..d-1:
$$(a''_{k, i}s_j + e)$$

5. Generate RGSW shares:
For i in 0..n
1. Sample $a_i \leftarrow Rng_{\gamma_{K}}$
2. Generate $(a_i u_j + e + X^{\hat{s}[i]}, a_i, a_is_j+e)$

## Server

Server receives bootstrapping key shares $K_0, K_1, ..., K_{j-1}$ from all parties.

### Generate $ksk(u_j \to s)$

For party j server generates $ksk(u_j \to s)$:

1. For i in $0..d-1$:
$$
a''_{i, j}s + e + \beta_iu_j = a''_{i, j} s_j + e + \beta_iu_j + \sum_{k \in P_j} a''_{i, j}s_k + e
$$
2. Set ksk as:
$$[RLWE_s(\beta^iu_j)] = [a''_{i, j}s + e + \beta_iu_j, a''_{i, j}]$$

### Generate $RGSW(\beta_k X^{\hat{s}[i]})$
1. Generate $RLWE(\beta^kX_j^{\hat{s}[i]})$ using $Ksk(u_j \to s)$ as:

1. Sample $a_i \leftarrow Rng_{\gamma_{K}}$
2. Set

$$RLWE(-a_iu_j) = decomp<-a_i> \cdot [RLWE_s(\beta^iu_j)]$$

$$RLWE(\beta^k X_j^{\hat{s}[i]}) = (a_i u_j + e + \beta^k X_j^{\hat{s}[i]}, 0) + RLWE(-a_iu_j)$$
2. Generate $RLWE(\beta^kX_j^{\hat{s}[i]})$ using $Ksk(u_j \to s)$ as:
1. Aggregate
$$a_is + e = \sum a_is_j + e$$
2. Key switch $a_is + e$
$$RLWE_s(a_isu_j + eu_j) = decomp<a_is+e> \cdot [RLWE_s(\beta^iu_j)]$$
3. Set $RLWE(\beta^kX_j^{\hat{s}[i]})$:
$$RLWE(\beta^kX_j^{\hat{s}[i]}) = RLWE_s(a_isu_j + eu_j) + (0, a_i u_j + e + \beta^k X_j^{\hat{s}[i]})$$

----
----

## Modifying non-interactive key-gen to allow RLWE x RGSW and RGSW x RGSW to use differing bases.

### Key share gen

For Non-interactive RGSW ciphertext at LWE index $l$ we sample $d_{max}$ $a_i$s where $d_{max} = MAX(d_a, d_b)$ where $d_{a/b}$ are decomposition counts of RGSW x RGSW product.

We then generate RGSW zero encryptions, $a_i s_j + e$, for $a_i$ with $i \in [d_{max} - d_a, d_{max})$ because zero encryptions are only required to generate RLWE'(-sm) which has $d_a$ RLWE ciphertexts.

Let $d'_a$ and $d'_b$ be decompsition count for RLWE x RGSW and $d_a$ and $d_b$ be decomposition count for RGSW x RGSW. We assume that $d_a > d'_a$ AND $d_b > d'_b$.

Note that gadget vector for $d_{a/b}$ (or $d'_{a/b}$) either equals gadget vector of $d_{max}$ (or $d'_{max}$) or is contained inside it. For example, if $d_a = d_{max} = 5$ and $d_b = 2$, then gadget vector of $d_a = [\gamma, \gamma B,..., \gamma B^{4}]$ and gadget vector of $d_b = [\gamma B^3B^0, \gamma B^3B^1]$

Define $d_{max} = MAX(d_a, d_b)$. To produce non-interactive RGSW ciphertext for RGSW x RGSW -
1. Generate non-interactive RLWE ciphertext for each $a_{i}$ with $i \in [0, d_{max})$ using $d_{max}$ gadget vector = $[\gamma B^0, \gamma B^1, ..., \gamma B^{d_{max}-1}]$.
$$[a_i u_j + e + \gamma B^{i} X^{s[l]}]$$
2. Generate zero encrytions for non-interactive RGSW ciphertexts using $a_{i}$ with $i \in [d_{max} - d_a, d_{max})$. Recall that we only require zero encryptions to produce $RLWE(-sm)$ which has $d_a$ RLWE ciphertexts. Thus we restrict to top $d_a$ $a_i$s

Define $d'_{max} = MAX(d'_a, d'_b)$. To produce non-interactive RGSW ciphertext for RLWE x RGSW, since d_a > d'_a and user doe snot generate RGSW for RLWExRGSW and RGSW for RGSWxRGSW for same lwe index,we re-use $a_{i}$s used above. This prevents sending additional zero encryptions specifically suited for $d'_a$ and $d'_a$ of RLWE x RGSW decomposer.

1. Generate non-interactive RGSW ciphertext for each $a_{i}$ with $i \in [d_{max} - d'_{a}, d_{max})$ as
$$[a_i u_j + e + \gamma B'^iX^{s[l]}]$$

Note that to be able to re-use $a_{i}$s of zero encryptions we need to align indices of $a_i$s across the two routines. We do this by always picking top $a_i$'s as per $d_a$ or $d'_a$.

### Key share aggregation

Assume there exists a key switching key $KSK(u_j \to s)$, for user $j$, which multiplies polynomial a with $u_j$ to produce $RLWE(a u_j)$.

**Produce RGSW ciphertext for RGSW x RGSW.**

Define gadget vectors:
1. $G_{max} = [B^0, ..., B^{d_{max}-1}]$
2. $G_{a} = [B^{d_{max}-d_a}, B^{d_{max}-1}]$
3. $G_{b} = [B^{d_{max}-d_b}, B^{d_{max}-1}]$

To produce $RLWE'(-sX^{s[l]}) = [RLWE(-s G_a[i] X^{s[l]})]$, for $i \in [0, d_a)$
1. key switch aggregated zero encryptions $a_{i+d_{max}-d_a} s + e$, using $Ksk(u_j \to s)$ for $i \in [0, d_{a})$, i.e. to produce $RLWE(u_ja_{i}s + u_je)$.
2. Recall non-interactive RGSW ciphertext: $$[a_{i+d_{max}-d_{a}} u_j + e + G_a[i] X^{s[l]}]$$ For $i \in [0, d_{a})$
3. Set $$RLWE'(-sX^{s[l]})[i] = (0, u_j a_{i + d_{max}-d_{a}} + e + G_a[i] X^{s[l]}) + RLWE(u_ja_{i+d_{max}-d_a}s + u_je)$$ For $k \in [0, d_a)$

To produce $RLWE'(X^{s[l]}) = [RLWE(G_b[i] X^{s[l]})$ for $i \in [0, d_b)$
1. key switch $-a_{i+(d_{max} - d_b)}$ with $Ksk(u_j \to s)$ for $i \in [0, d_b)$ to produce $RLWE(-a_{i+(d_{max} - d_b)} u_j)$.
2. Set $$RLWE'(X^{s[l]})[i] = [(u_j a_{i+(d_{max} - d_b)} + e, 0) + RLWE(-a_{i+(d_{max} - d_b)} u_j)]$$

Set $RGSW(X^{s[l]}) = RLWE'(-sX^{s[l]}) || RLWE'(X^{s[l]})$

**Produce RGSW ciphertext for RLWE x RGSW.**

Define gadget vectors:
1. $G'_{max} = [B'^0, ..., B'^{d'_{max}-1}]$
2. $G'_{a} = [B^{d'_{max}-d'_a}, B'^{d'_{max}-1}]$
3. $G'_{b} = [B^{d'_{max}-d'_b}, B'^{d'_{max}-1}]$

To produce $RLWE'(-sX^{s[l]}) = [RLWE(-s G'_a[k] X^{s[l]})]$, for $k \in [0, d'_a)$
1. key switch aggregated zero encryptions for $i \in [0, d'_{a})$, i.e. $a_{i+d_{max}-d'_{a}} s + e$, using $Ksk(u_j \to s)$ to produce $RLWE(u_ja_{i+d_{max}-d'_{a}}s + u_je)$.
2. Recall non-interactive RGSW ciphertext for RLWE x RGSW: $$[a_{i+d_{max}-d'_{a}} u_j + e + G'_a[i] X^{s[l]}]$$ For $i \in [0, d'_{a})$
3. Set $$RLWE'(-sX^{s[l]})[i] = (0, u_j a_{i + d_{max}-d'_{a}} + e + G'_a[i] X^{s[l]}) + RLWE(u_ja_{k + d_{max}-d'_{a}}s + u_je)$$ For $k \in [0, d'_a)$

To produce $RLWE'(X^{s[l]}) = [RLWE(G'_b[i] X^{s[l]})$ for $i \in [0, d'_b)$
1. key switch $-a_{i+(d_{max} - d'_b)}$ with $Ksk(u_j \to s)$ for $i \in [0, d'_b)$ to produce $RLWE(-a_{i+(d_{max} - d'_b)} u_j)$.
2. Set $$RLWE'(X^{s[l]})[i] = [(u_j a_{i+(d_{max} - d'_b)} + e, 0) + RLWE(-a_{i+(d_{max} - d'_b)} u_j)]$$

Set $RGSW(X^{s[l]}) = RLWE'(-sX^{s[l]}) || RLWE'(X^{s[l]})$