# Threshold Pseudorandom Correlation Generators

## Preliminaries

### Notation

| Name | Description |
| -------- | -------- |
| $\mathcal{C}$ | An elliptic curve |
| $p$ | Field modulus in $\mathcal{C}$ |
| $q$ | Subgroup order in $\mathcal{C}$ |
| $\mathbb{G}$ | The set of points in $\mathcal{C}$ of order $p$ |
| $1_{\mathbb{G}}$ | The point at infinity |
| $\mathbb{G}^*$ | The set of points in $\mathcal{C}$ of order $p$ excluding the point at infinity $1_\mathbb{G}$ |
| $P$ | Base point or generator in $\mathbb{G}^*$ |
| ${\mathbb{F}}$ | The ring of non-zero integers modulo $q$ |
| ${\mathbb{F}}^n$ | A vector of $\mathbb{F}$ elements with length *n* |
|$\xleftarrow{} \mathbb{F}$|Uniform randomly sampled integer in $\mathbb{F}$|
|$\mathcal{H}_{\mathbb{F}}$|Hash an arbitrary length byte sequence to a value in $\mathbb{F}$|
|[k]|The set of {1,...,k}|
|$\mathbb{N}$|Integers starting at 1|
|$\xleftarrow{} \mathbb{N}$|Uniform randomly sampled integer in $\mathbb{N}$|
|$\mathbb{N}^n$|A vector of $\mathbb{N}$ integers with length *n*|
|$U^{r}_{i}$|A matrix indexed as [i][r] |
|$U^{r,s}_{i,j,k}$|A matrix indexed as [i][j][k][r][s]|
| $\lambda$ | The security parameter |

We denote vectors of elements
via bold letters, e.g., **a**, and the i-th element of a vector **a** by a[i].

### Beaver Triple Setting

#### PCG
For $\tau$-out-of-*n*. Let $Q = \sum_{i \in [n]}\left(\alpha_i\right) \cdot P$ where $Q$ is the public mac key for the PCG.

**Eval**

On input seed $\kappa_i$ and **a**$\xleftarrow{}\mathbb{F}^c$ where **a**$^{r}\xleftarrow{} \mathbb{F}^{c-2}$ and **a**$^{c-1} =1$, do the following

- For $r \in [c]$, define the following polynomials $$u^r_i(X) = \sum_{l \in [t]}\beta^r_i[l] \cdot X^{\omega^r_i[l]}$$ $$v^r_i(X) = \sum_{l \in [t]}\gamma^r_i[l]\cdot X^{\eta^{r}_i[l]}$$
- For $r \in [c]$, compute $$\overline{u}^r_i = \alpha_i \cdot u^r_i,\ \overline{v} = \alpha_i \cdot v^r_i$$ $$\widetilde{u}^{r}_{i,j,\ i \ne j} = \mbox{DSPF}^2_{N,t}.\mbox{FullEval}(U^{r,0}_{i,j}) + \mbox{DSPF}^2_{N,t}.\mbox{FullEval}(U^{r,1}_{j,i})$$ $$\widetilde{v}^{r}_{i,j,\ i \ne j} = (\mbox{DSPF}^2_{N,t}.\mbox{FullEval}(V^{r,0}_{i,j}) + \mbox{DSPF}^2_{N,t}.\mbox{FullEval}(V^{r,1}_{j,i})$$
- For $r,s \in [c]$, compute $$\widehat{w}^{r,s}_i = u^{r}_i\cdot v^s_i$$ $$\overline{w}^{r,s}_i = \alpha_i\cdot \widehat{w}^{r,s}_i$$ $$w^{r,s}_{i,j,\ i\ne j} = \left(\mbox{DSPF}^2_{2N,t^2}.\mbox{FullEval}(C^{r,s,0}_{i,j}) + \mbox{DSPF}^2_{2N,t^2}.\mbox{FullEval}(C^{r,s,1}_{j,i})\right)$$ $$\widetilde{w}^{r,s}_{i,j,k,(i, i)\ne(j,k)}= (\mbox{DSPF}^3_{2N,t^2}.\mbox{FullEval}(W^{r,s,0}_{i,j,k}) +$$ $$\mbox{DSPF}^3_{2n,t^2}.\mbox{FullEval}(W^{r,s,1}_{k,i,j}) +$$ $$\mbox{DSPF}^3_{2N,t^2}.\mbox{FullEval}(W^{r,s,2}_{j,k,i}))$$
- Compute the final shares $$x_i=\langle a,u^r_i\rangle, y_i=\langle a,v^r_i\rangle$$ $$\overline{z}_i=\langle a\otimes a,\widehat{w}^{r,s}_i \rangle,z_{i,j} =\langle a\otimes a, w^{r,s}_{i,j}\rangle$$ $$\overline{m}^x_i=\langle a,\overline{u}^r_i \rangle, m^{x,0}_{i,j} =\langle a, \widetilde{u}^{r,0}_{i,j}\rangle,m^{x,1}_{i,j}=\langle a,\widetilde{u}^{r,1}_{i,j}\rangle$$ $$\overline{m}^y_i=\langle a,\overline{v}^r_i \rangle,m^{y,0}_{i,j} =\langle a, \widetilde{v}^{r,0}_{i,j}\rangle,m^{y,1}_{i,j}=\langle a,\widetilde{v}^{r,1}_{i,j}\rangle$$ $$\overline{m}^z_i=\langle a \otimes a, \overline{w}^{r,s}_i\rangle, m^z_{i,j,k}=\langle a\otimes a,\widetilde{w}^{r,s}_{i,j,k} \rangle$$
- Output $\{\alpha_i, x_i,y_i,\widehat{z}_i,z_{i,j},\overline{m}^x_i,m^{x,0}_{i,j},m^{x,1}_{i,j},\overline{m}^y_i,m^{y,0}_{i,j},m^{y,1}_{i,j},\overline{m}^z_i,m^{z}_{i,j,k}\}$

**Tuple** for $\tau$-out-of-*n*

On input root $\xi$, and signer set indices $S$, compute the following. Note that the inputs are the same for all signers.

- $z_i = \overline{z}_i + \sum_{j \in S}\left(z_{i,j} \right)$
- $m^x_i = \overline{m}^x_i + \sum_{j \in S}\left(m^{x,0}_{i,j} + m^{x,1}_{i,j} \right)$
- $m^y_i = \overline{m}^y_i + \sum_{j \in S}\left(m^{y,0}_{i,j} + m^{y,1}_{i,j}\right)$
- $m^z_i = \overline{m}^z_i +\sum_{j,k \in S}\left(m^{z}_{i,j,k}\right)$
- $x = \mbox{PolyEval}(x_i, \xi)$
- $y = \mbox{PolyEval}(y_i, \xi)$
- $z = \mbox{PolyEval}(z_i, \xi)$
- $m_x = \mbox{PolyEval}(m_{x,i}, \xi)$
- $m_y = \mbox{PolyEval}(m_{y,i}, \xi)$
- $m_z = \mbox{PolyEval}(m_{z,i}, \xi)$
- Output $[[x]]_i = \{\alpha_i, x, y, z, m_x, m_y, m_z\}$
- Output $[[X]]_i = \{Q, X, Y, Z, M_x, M_y, M_z\}$

**Prepresigning Round 1**

- $\star$ Each $P_i$ broadcasts $[[X]]_i$ to each other $P_j$.
- $\bullet$ Each $P_i$ waits to receive $[[X]]_j$ from each other $P_j$
- Each $P_i$ computes for $X,Y,Z,M_x,M_y,M_z \in T$ $$T = \sum_{j \in S}\left(T_j \right)$$
- Each $P_i$ samples **r**$^T\xleftarrow{}\mathbb{F}^S$ using PRF$\left(\mathcal{H}(\mathcal{D}|| \wp || Q || X || Y || Z || M_x || M_y || M_z)\right)$. $\wp$ is the signing nonce, $\mathcal{H}$ is SHA-256, and $\mathcal{D}$ is a domain separation tag. The hash output is the PRF seed.
- Each $P_i$ computes for $x,y,z \in T$ $$R_T = \sum_{j \in S}\left(r^T_j \cdot T_j\right)$$ $$\Lambda^T_i = \sum_{j \in S}\left(r^T_j\cdot M^T_j\right)$$ $$\sigma^T_i = \Lambda^T_i - \alpha_i\cdot R_T$$

**Prepresigning Round 2**
- $\star$ Each $P_i$ broadcasts for $x,y,z \in T$ $$\Omega^T_i = \mathcal{H}\left(\sigma^t_i \right)$$
- $\bullet$ Each $P_i$ waits to receive $\Omega^t_i$

**Add to Cait-Sith Presigning Round 1**
- $\star$ Each $P_i$ broadcasts $\sigma^T_i$
- $\bullet$ Each $P_i$ waits to receive $\sigma^T_j$ from each other $P_j$
- $\blacktriangle$ Each $P_i$ asserts $\Omega^t_j = \mathcal{H}\left(\sigma^t_j\right)$
- $\blacktriangle$ Each $P_i$ asserts $$\sum_{j \in S}\left(\sigma^T_j\right) = 1_{\mathbb{G}}$$

**Mac Check**
Based on [5] Fig.10 pg. 25 except computations are performed in $\mathbb{G}$

## Notes
### BBS+ Setting
This concept is not new and something similar is used in this setting

#### PCG

**Setup**
For $\tau$-out-of-*n* and *n*-out-of-*n* setting

Input:
- $\mathcal{C}, \lambda, N, n, \tau, c, t$

Steps:
- $x \xleftarrow{} \mathbb{F}$
- Create shamir shares of $x$ as $x_i$ belonging to Participant $p_i$
- For $i \in [n], r \in [c]$, make $(\omega^r_i)^N,(\eta^r_i)^N,(\phi^r_i)^N \xleftarrow{} \mathbb{N}^t$
- For $i \in [n], r\in[c]$, make $(\beta^r_i)^N,(\gamma^r_i)^N,(\epsilon^r_i)^N \xleftarrow{} \mathbb{F}^t$
- For every $i, j \in [n]$ with $i \ne j, r \in [c]$, compute $$(U^{r,0}_{i,j},U^{r,1}_{i,j}) \xleftarrow{} \mbox{DSPF}^2_{N,t}.\mbox{Gen}(\omega^r_i, x_{\ell j} \cdot \beta^r_i)$$
- For $i,j \in [n]$ with $i \ne j$, $r, s \in [c]$, compute $$(C^{r,s,0}_{i,j},C^{r,s,1}_{i,j}) \xleftarrow{} \mbox{DSPF}^2_{2N,t^2}.\mbox{Gen}(\omega^r_i \boxplus \phi^s_j, \beta^r_i \otimes \epsilon^s_j)$$ $$(V^{r,s,0}_{i,j},V^{r,s,1}_{i,j}) \xleftarrow{} \mbox{DSPF}^2_{2N,t^2}.\mbox{Gen}(\omega^r_i \boxplus \eta^s_j, \beta^r_i \otimes \gamma^s_j)$$
- For $i \in [n]$, output the seed $\kappa_i$ which contains
- $x_{\ell i}$
- $(\omega^r_i,\eta^r_i, \phi^r_i, \beta^r_i,\gamma^r_i,\epsilon^r_i)_{r \in [c]}$
- $(U^{r,0}_{i,j},U^{r,1}_{i,j})_{i \ne j,\ r \in [c]}$
- $(C^{r,s,0}_{i,j},C^{r,s,1}_{i,j})_{i \ne j,\ r,s \in [c]}$
- $(V^{r,s,0}_{i,j},V^{r,s,1}_{i,j})_{i \ne j,\ r,s \in [c]}$

**Eval** for *n*-out-of-*n*

On input seed $\kappa_i$ and **a**$\xleftarrow{}\mathbb{F}^c$ where **a**$^{r}\xleftarrow{} \mathbb{F}^{c-2}$ and **a**$^{c-1} =1$, do the following

- For every $r \in [c]$, define the polynomials $$u^r_i(X) = \sum_{l \in t}\beta^r_i[l] \cdot X^{\omega^r_i[l]}$$ $$v^r_i(X) = \sum_{l \in t}\gamma^r_i[l] \cdot X^{\eta^r_i[l]}$$ $$k^r_i(X) = \sum_{l \in t}\epsilon^r_i[l] \cdot X^{\phi^r_i[l]}$$
- For every $r \in [c]$, compute $$\widetilde{u}^r_i(X) = x_{\ell i}\cdot u^r_i(X) + $$ $$\sum(\mbox{DSPF}^2_{N,t}.\mbox{FullEval}(U^{r,0}_{i,j})(X)+$$ $$\mbox{DSPF}^2_{N,t}.\mbox{FullEval}(U^{r,1}_{j,i})(X))$$
- For every $r, s \in [c]$, compute $$w^r_i(X) = u^r_i(X)\cdot k^s_i(X) + $$ $$\sum_{i \ne j}(\mbox{DSPF}^2_{2N,t^2}.\mbox{FullEval}(C^{r,s,0}_{i,j})(X) +$$ $$\mbox{DSPF}^2_{2N,t^2}.\mbox{FullEval}(C^{r,s,1}_{j,i})(X))$$
- For every $r, s \in [c]$, compute $$m^r_i(X) = u^r_i(X)\cdot v^s_i(X) + $$ $$\sum_{i \ne j}(\mbox{DSPF}^2_{2N,t^2}.\mbox{FullEval}(V^{r,s,0}_{i,j})(X) +$$ $$\mbox{DSPF}^2_{2N,t^2}.\mbox{FullEval}(V^{r,s,1}_{j,i})(X))$$
- Compute the final shares $$a_i = \langle a, u_i \rangle, e_i =\langle a, v_i \rangle, s_i = \langle a,k_i \rangle$$ $$\delta^0_i = \langle a, \widetilde{u}_i \rangle, \alpha_i = \langle a\otimes a, w_i \rangle, \delta^1_i = \langle a \otimes a, m_i \rangle$$ $$\delta_i = \delta^0_i(X) + \delta^1_i(X)$$
- Output polynomials $\{x_{\ell i}, a_i, e_i, s_i, \alpha_i, \delta_i\}$

**Tuple** for *n*-out-of-*n*

On input root $\xi$, compute the following

- $a = a_i.\mbox{PolyEval}(\xi)$
- $e = e_i.\mbox{PolyEval}(\xi)$
- $s = s_i.\mbox{PolyEval}(\xi)$
- $\alpha = \alpha_i.\mbox{PolyEval}(\xi)$
- $\delta = \delta_i.\mbox{PolyEval}(\xi)$
- Output $\{x_{\ell i}, a, e, s, \alpha, \delta\}$

**Eval** for $\tau$-out-of-*n*

On input seed $\kappa_i$ and **a**$\xleftarrow{}\mathbb{F}^c$ where **a**$^{r}\xleftarrow{} \mathbb{F}^{c-2}$ and **a**$^{c-1} =1$, do the following

- For every $r \in [c]$, define the polynomials $$u^r_i(X) = \sum_{l \in t}\beta^r_i[l] \cdot X^{\omega^r_i[l]}$$ $$\overline{u}^r_i(X) = x_{\ell i}\cdot u^r_i(X)$$ $$v^r_i(X) = \sum_{l \in t}\gamma^r_i[l] \cdot X^{\eta^r_i[l]}$$ $$k^r_i(X) = \sum_{l \in t}\epsilon^r_i[l] \cdot X^{\phi^r_i[l]}$$
- For every $j \in [n], r \in [c]$, compute $$\widetilde{u}^{r,0}_{i,j,\ i \ne j}(X) = \mbox{DSPF}^2_{N,t}.\mbox{FullEval}(U^{r,0}_{i,j})(X)$$ $$\widetilde{u}^{r,1}_{i,j,\ i \ne j}(X) = \mbox{DSPF}^2_{N,t}.\mbox{FullEval}(U^{r,1}_{j,i})(X)$$
- For every $j \in [n], r, s \in [c]$ $$w^{r,s}_{i,j,\ i \ne j}(X) = (\mbox{DSPF}^2_{2N,t^2}.\mbox{FullEval}(C^{r,s,0}_{i,j})(X) +$$ $$\mbox{DSPF}^2_{2N,t^2}.\mbox{FullEval}(C^{r,s,1}_{j,i})(X))_{i \ne j}$$ $$m^{r,s}_{i,j,\ i \ne j} = (\mbox{DSPF}^2_{2N,t^2}.\mbox{FullEval}(V^{r,s,0}_{i,j})(X) +$$ $$\mbox{DSPF}^2_{2N,t^2}.\mbox{FullEval}(V^{r,s,1}_{j,i})(X))_{i \ne j}$$ $$\widehat{u_k}^{r,s}_{i,\ i \ne j}(X) = u^r_i(X)\cdot k^s_i(X)$$ $$\widehat{u_v}^{r,s}_{i,\ i \ne j}(X) = u^r_i(X)\cdot v^s_i(X)$$
- Compute the shares $$a_i = \langle a, u^r_i \rangle, e_i =\langle a, v^r_i \rangle, s_i = \langle a,k^r_i \rangle$$ $$\delta^{0,0}_{i,j,\ i \ne j} = \{\langle a,\widetilde{u}^{r,0}_{i,j} \rangle\}_{i \ne j \in [n]}, \delta^{0,1}_{i,j,\ i \ne j} = \{\langle a, \widetilde{u}^{r,1}_{i,j}\rangle\}_{i \ne j \in [n]}$$ $$\delta^{1}_{i,j,\ i \ne j}=\{ \langle a \otimes a, m^r_{i,j} \rangle\}_{i \ne j \in [n]}$$ $$\overline{u}_i = \langle a,\overline{u}^{r}_i \rangle, \alpha_{i,j} = \{\langle a \otimes a, w^r_{i,j} \rangle\}_{i \ne j \in [n]}$$ $$\widehat{u_k}_i = \langle a \otimes a, \widehat{u_k}^r_{i}\rangle, \widehat{u_v}_i=\langle a \otimes a, \widehat{u_v}^r_i \rangle$$
- Output polynomials $\{x_i, a_i, e_i, s_i, \delta^{0,0}_{i,j}, \delta^{0,1}_{i,j},\overline{u}_i, \alpha_{i,j}, \widehat{u_k}_i, \widehat{u_v}_i\}$

**Tuple** for $\tau$-out-of-*n*

On input root $\xi$, and signer set indices $S$, compute the following

- $\delta^0_i = \overline{u}_i + \widehat{u_v}_i + \sum_{j \in S}\left( \delta^{0,0}_{i,j} + \delta^{0,1}_{i,j} + \delta^1_{i,j}\right)$
- $\alpha_i = \widehat{u_k}_i + \sum_{j \in S}\left(\alpha_{i,j}\right)$
- $a = a_i.\mbox{PolyEval}(\xi)$
- $e = e_i.\mbox{PolyEval}(\xi)$
- $s = s_i.\mbox{PolyEval}(\xi)$
- $\alpha = \alpha_i.\mbox{PolyEval}(\xi)$
- $\delta = \delta_i.\mbox{PolyEval}(\xi)$
- Output $\{x_i, a, e, s, \alpha, \delta\}$

## References

1. [Low-Bandwidth Threshold ECDSA via Pseudorandom Correlation Generators](https://eprint.iacr.org/2021/1587), Damiano Abram, Ariel Nof, Claudio Orlandi, Peter Scholl, and Omer Shlomovits
2. [Low-Communication Multiparty Triple
Generation for SPDZ from Ring-LPN](https://eprint.iacr.org/2022/315), Damiano Abram and Peter Scholl
3. [Efficient Pseudorandom Correlation Generators from Ring-LPN](https://eprint.iacr.org/2022/1035), Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Scholl
4. [Non-Interactive Threshold BBS+ From
Pseudorandom Correlations](https://eprint.iacr.org/2023/1076), Sebastian Faust, Carmit Hazay, David Kretzler, Leandro Rometsch, and Benjamin Schlosser
5. [Practical Covertly Secure MPC for Dishonest Majority – or: Breaking the
SPDZ Limits](https://eprint.iacr.org/2012/642), Ivan Damgard, Marcel Keller, Enrique Larraia, Valerio Pastro, Peter Scholl, and Nigel P. Smart
6. [Function Secret Sharing: Improvements and Extensions](https://eprint.iacr.org/2018/707.pdf), Elette Boyle, Niv Gilboa, and Yuval Ishai, 2018
6. [Function Secret Sharing and
Homomorphic Secret Sharing](https://cs.idc.ac.il/~elette/HSS_FSS-Survey.pdf)
7. [Feist-Khovratovich technique for computing KZG proofs fast](https://alinush.github.io/2021/06/17/Feist-Khovratovich-technique-for-computing-KZG-proofs-fast.html)