Cait-Sith Security (3): Multiplication and Triples

We basically start with the ideal functionality for multiplicative-to-additive conversion (MTA), from HMRT21. We slightly simplify their functionality, by giving the adversary more power to corrupt the result.

Definition (MTA):

$$\boxed{\begin{array}{c}F[\text{MTA}]\\ \\ \boxed{\begin{array}{rl}& P_i\\ & \\ & a_1,a_2,{\beta }_1,{\beta }_2\leftarrow \perp \\ & \Delta \leftarrow \perp \\ & \\ & \underline{(1){\text{StartMTA}}_i(a):}\\ & a_i\leftarrow a\\ & \\ & \underline{\text{Sample}():}\\ & \text{assert }{a}_1,a_2,\Delta \ne \perp \\ & \text{if }{\beta }_1,{\beta }_2=\perp :\\ & ({\beta }_1,{\beta }_2)\stackrel{\$}{\leftarrow }\{({\beta }_1,{\beta }_2)\in {\mathbb{F}}_q^2\mid {\beta }_1+{\beta }_2=a_1\cdot a_2+\Delta \}\\ & \\ & \underline{(1){\text{EndMTA}}_i():}\\ & \text{wait}\_(i,0)a_1,a_2,\Delta \ne \perp \\ & \text{Sample}()\\ & \text{return }{\beta }_i\\ & \\ & \underline{(1)\text{Cheat}(\Delta )}\\ & \Delta \leftarrow \Delta \end{array}}\end{array}}$$

$\square$

The basic idea is that we convert a secret $s=a\cdot b$ into shares $\alpha ,\beta$ such that $\alpha +\beta =s$. But, the malicious party can cause the result to fail, by instead being a secret sharing of $s+\Delta$.

Multiplication

Next, we consider multiplication using this functionality.

First, we need to take a detour, to consider using two instances of the functionality together.

Consider the following protocol:

$$\boxed{\begin{array}{c}\mathcal{P}[{\text{MTA}}^2]\\ \\ \boxed{\begin{array}{rl}& P_i\\ & \\ & \underline{(1)\text{Start}\_ij(a,b):}\\ & {\text{StartMTA}}_i^0(\text{Flip}\_ij(a,b))\\ & {\text{StartMTA}}_i^1(\text{Flip}\_ij(b,a))\\ & \\ & \underline{(1)\text{EndMTA}\_ij():}\\ & \text{return }{\text{EndMTA}}_i^0()+{\text{EndMTA}}_i^1()\\ & \\ & \underline{(1){\text{Cheat}}^{\tau }(\Delta )}\\ & {\text{Cheat}}^{\tau }(\Delta )\end{array}}\end{array}}⊲\mathcal{P}[\text{MTA}{]}^2$$

Well, it turns out that this implements the following functionality:

$$\boxed{\begin{array}{c}F[{\text{MTA}}^2]\\ \\ \boxed{\begin{array}{rl}& P_i\\ & \\ & a_1,a_2,b_1,b_2,{\beta }_1,{\beta }_2\leftarrow \perp \\ & \Delta \leftarrow \perp \\ & \\ & \underline{(1){\text{Start}}_i(a,b):}\\ & a_i\leftarrow a,b_i\leftarrow b\\ & \\ & \underline{\text{Sample}():}\\ & \text{assert }{a}_1,a_2,b_1,b_2,\Delta \ne \perp \\ & \text{if }{\beta }_1,{\beta }_2=\perp :\\ & ({\beta }_1,{\beta }_2)\stackrel{\$}{\leftarrow }\{({\beta }_1,{\beta }_2)\in {\mathbb{F}}_q^2\mid {\beta }_1+{\beta }_2=a_1\cdot b_2+a_2\cdot b_1+\Delta \}\\ & \\ & \underline{(1){\text{End}}_i():}\\ & \text{wait}\_(i,0)a_1,a_2,b_1,b_2,\Delta \ne \perp \\ & \text{Sample}()\\ & \text{return }{\beta }_i\\ & \\ & \underline{(1)\text{Cheat}(\Delta )}\\ & \Delta \leftarrow \Delta \\ & \\ & \underline{\text{Leak}(\Delta )}\\ & \text{return }(a_1\ne \perp ,a_2\ne \perp ,b_1\ne \perp ,b_2\ne \perp )\end{array}}\end{array}}$$

This is a bit of a simplification, in that there’s only a single $\Delta$ for the result, rather than 2. This will make our life a bit easier later.

Lemma:

For a negligible $ϵ$, and any number of malicious corruptions, we have:

$$\mathcal{P}[{\text{MTA}}^2]\stackrel{ϵ}{⇝}F[{\text{MTA}}^2]$$

Proof:

First, the case of all corruptions is trivial, as with any protocol, and the protocol clearly functions in the case of no corruptions, so we consider the case where, without loss of generality, the second party is corrupt.

We start, as usual, by unrolling things.

$$\begin{array}{c}\boxed{\begin{array}{rl}& {\Gamma }_H^0\\ & \\ & \underline{(1){\text{Start}}_1(a,b):}\\ & \dots \end{array}}\otimes \boxed{{\Gamma }_M^0=1\left(\begin{array}{c}{\text{StartMTA}}_2^{\tau },\\ {\text{EndMTA}}_2^{\tau },\\ {\text{Cheat}}^{\tau }\end{array}\right)}\\ \circ \\ F[\text{MTA}]\otimes F[\text{MTA}]\end{array}$$

And from here, we can directly perform a simulation.

$$\begin{array}{c}\boxed{\begin{array}{rl}& {\Gamma }_H^1=1\left(\begin{array}{c}{\text{Start}}_1,\\ {\text{End}}_1\end{array}\right)\end{array}}\otimes \boxed{\begin{array}{rl}& S\\ & \\ & {\Delta }^1,{\Delta }^2,\text{first}\leftarrow \perp \\ & \alpha \stackrel{\$}{\leftarrow }{\mathbb{F}}_q\\ & \\ & \underline{(1){\text{StartMTA}}_2^{\tau }(a):}\\ & \text{if }{a}^{\tau }=\perp :\\ & a^{\tau }\leftarrow a\\ & \text{if }{a}^1,a^2\ne \perp :\\ & \text{Start}(a^1,a^2)\\ & \\ & \underline{(1){\text{EndMTA}}_2^{\tau }():}\\ & (r_1,\bullet ,r_2,\bullet )\leftarrow \text{Leak}()\\ & \text{wait}\_(2,0)r\_\tau \ne \perp \wedge a^{\tau },{\Delta }^{\tau }\ne \perp \\ & \text{if }\text{first}=\perp :\\ & \text{first}\leftarrow \tau \\ & \text{if }\text{first}=\tau :\\ & \text{return }\alpha \\ & \text{return }{\text{End}}_2()\\ & \\ & \underline{(1){\text{Cheat}}^{\tau }(\Delta ):}\\ & \text{if }{\Delta }^{\tau }=\perp :\\ & {\Delta }^{\tau }\leftarrow \Delta \\ & \text{if }{\Delta }^1,{\Delta }^2\ne \perp :\\ & \text{Cheat}({\Delta }^1+{\Delta }^2-\alpha )\end{array}}\\ \circ \\ F[{\text{MTA}}^2]\end{array}$$

The basic idea is that the adversary can only tell whether or not they’ve received correct shares of the MTA by summing everything together, from both the honest and malicious parties, because of this, we can give them junk until they get the second share, in which case we need to make it so that the sum is preserved. We can do this by cheating with ${\Delta }^1+{\Delta }^2-\alpha$, and using the result of the “double MTA” as their second share. When we sum everything up, we’ll get the right share.

$■$

Next, let’s look at the actual multiplication protocol.

Definition (Multiplication):

$$\boxed{\begin{array}{c}\mathcal{P}[\text{Multiply}]\\ \\ \boxed{\begin{array}{rl}& P_i\\ & \\ & {\text{start}}_i\leftarrow \perp \\ & \\ & \underline{(1){\text{StartMultiply}}_i(a,b):}\\ & {\text{start}}_i\leftarrow \text{true}\\ & \forall j\ne i.{\text{StartMTA}}_i^{(0,ij)}({\text{Flip}}_i(a,b))\\ & \forall j\ne i.{\text{StartMTA}}_i^{(1,ij)}({\text{Flip}}_i(b,a))\\ & \\ & \underline{(1){\text{EndMultiply}}_i():}\\ & \text{assert }{\text{start}}_i\\ & \text{wait}\_(i,0)\forall j.({\gamma }^0\_j,{\gamma }^1\_j)\leftarrow ({\text{EndMTA}}_i^{(0,ij)}(),{\text{EndMTA}}_i^{(1,ij)}())\\ & \text{return }a\cdot b+\sum _j({\gamma }_j^0+{\gamma }^1\_j)\end{array}}\end{array}}⊲\begin{array}{c}F[\text{MTA}{]}^{n^2}\end{array}$$

$\square$

The basic idea is that you need to do MTAs between each pair of parties. One bit of notation we use is that we use $ij$ as indices, whereas in reality this only ranges of pairs such that $i\le j$, to not repeat the same pair twice. We also use ${\text{Flip}}_i(a,b)$ to denote a process whereby for each pair $i,j$, one party uses $a$ and the other $b$. We assume some common convention for doing this flip.

This gets us to the ideal functionality for multiplication:

Definition (Ideal Multiplication):

$$\boxed{\begin{array}{c}\mathcal{P}[\text{IdealMultiply}]\\ \\ \boxed{\begin{array}{rl}& P_i\\ & \\ & a,b\leftarrow \perp \\ & \\ & \underline{(1){\text{StartMultiply}}_i(a,b):}\\ & a,b\leftarrow a,b\\ & a\_\bullet \leftarrow a,b\_\bullet \leftarrow b\\ & {\text{StartMultiply}}_i(a\_\bullet ,b\_\bullet )\\ & \\ & \underline{(1){\text{EndMultiply}}_i():}\\ & \text{return }a\cdot b+{\text{EndMultiply}}_i()\end{array}}\boxed{\begin{array}{rl}& F[\text{Multiply}]\\ & \\ & a\_ij,b\_ij,{\beta }_i,\Delta \leftarrow \perp \\ & \\ & \underline{(1){\text{StartMultiply}}_i(a\_\bullet ,b\_\bullet ):}\\ & a\_i\bullet \leftarrow a\_\bullet ,b\_i\bullet \leftarrow b\_\bullet \\ & \\ & \underline{(1){\text{EndMultiply}}_i():}\\ & \text{wait}\_(i,0)\forall i\ne j.a\_ij,b\_ij\ne \perp \wedge \Delta \ne \perp \wedge a\_ii\ne \perp \\ & \text{Sample}()\\ & \text{return }{\beta }_i\\ & \\ & \underline{\text{Sample}():}\\ & \text{assert }\forall i\ne j.a\_ij,b\_ij\ne \perp \wedge \Delta \ne \perp \\ & \text{if }\forall i.{\beta }_i=\perp :\\ & c\leftarrow \sum \_i\ne ja\_ij\cdot b\_ji\\ & ({\beta }_1,\dots ,{\beta }_n)\leftarrow \{{\beta }_i\stackrel{\$}{\leftarrow }{\mathbb{F}}_q^n\mid \sum _i{\beta }_i=c+\Delta \}\\ & \\ & \underline{(1)\text{Cheat}(\Delta ):}\\ & \Delta \leftarrow \Delta \\ & \\ & \underline{\text{Leak}(i,j):}\\ & \text{return }a\_ij,b\_ij\ne \perp \end{array}}\end{array}}$$

$\square$

There are two ways the adversary can tamper with the result here. They can cheat via $\Delta$, as one might expect, or they can cheat by using inconsistent shares in the multiplication. This is reflected by using an entire vector $a\_\bullet ,b\_\bullet$, rather than a single scalar.

Lemma:

For some negligible $ϵ$, and any number of malicious corruptions, we have:

$$\mathcal{P}[\text{Multiply}]\stackrel{ϵ}{⇝}\mathcal{P}[\text{IdealMultiply}]$$

Proof:

First, $\mathcal{P}[\text{Multiply}]={\mathcal{P}}^0⊲\mathcal{P}[{\text{MTA}}^2{]}^{n^2}$, where:

$$\boxed{\begin{array}{c}{\mathcal{P}}^0\\ \\ \boxed{\begin{array}{rl}& P_i\\ & \\ & {\text{start}}_i\leftarrow \perp \\ & \\ & \underline{(1){\text{StartMultiply}}_i(a,b):}\\ & {\text{start}}_i\leftarrow \text{true}\\ & \forall j\ne i.{\text{Start}}_i^{ij}(a,b)\\ & \\ & \underline{(1){\text{EndMultiply}}_i():}\\ & \text{assert }{\text{start}}_i\\ & \text{return }a\cdot b+\sum \_j\ne i{\text{End}}_i^{ij}()\end{array}}\end{array}}⊲\begin{array}{c}\mathcal{P}[{\text{MTA}}^2{]}^{n^2}\end{array}$$

Then, it holds that:

$${\mathcal{P}}^0⊲\mathcal{P}[{\text{MTA}}^2{]}^{n^2/2}⇝\mathcal{P}⊲F[{\text{MTA}}^2{]}^{n^2/2}={\mathcal{P}}^1$$

Unrolling ${\mathcal{P}}^1$, we get the following:

$$\begin{array}{c}\boxed{\begin{array}{rl}& {\Gamma }_H^0\\ & \\ & \underline{(1){\text{StartMultiply}}_i(a,b):}\\ & \dots \end{array}}\otimes \boxed{{\Gamma }_M^0=1\left(\begin{array}{c}{\text{Start}}_k^{ki},\\ {\text{End}}_k^{ki},\\ {\text{Cheat}}^{ki}\end{array}\right)}\\ \circ \\ F[{\text{MTA}}^2{]}^{n^2/2}\end{array}$$

This is equivalent to:

$$\begin{array}{c}\boxed{\begin{array}{rl}& {\Gamma }_H^0=1\left(\begin{array}{c}{\text{StartMultiply}}_i,\\ {\text{EndMultiply}}_i\end{array}\right)\end{array}}\otimes \boxed{\begin{array}{rl}& S\\ & \\ & \text{left}\leftarrow \{(k,i)k\in \mathcal{M},i\in \mathcal{H}\}\\ & a\_ki,b\_ki,\alpha \_ki,\Delta \_ki\leftarrow \perp \\ & a\_kl,b\_kl\leftarrow 0\\ & \\ & \underline{{\text{Start}}_k^{ki}(a,b)}\\ & a\_ki\leftarrow a,b\_ki\leftarrow b\\ & \text{if }\forall i.a\_ki,b\_ki\ne \perp :\\ & {\text{StartMultiply}}_i(a\_\bullet ,b\_\bullet )\\ & \\ & \underline{{\text{End}}_k^{ki}()}\\ & \text{if }(k,i)\notin \text{left}:\\ & \text{return }\alpha \_ki\\ & \text{wait}\_(i,0)a\_ki,b\_ki,\Delta \_ki\ne \perp \wedge \text{Leak}(i,k)\\ & \text{left}\leftarrow \text{left}/\{(k,i)\}\\ & \text{if }|\text{left}|=0:\\ & {\alpha }_k\leftarrow {\text{EndMultiply}}_k()(k\in \mathcal{M})\\ & \text{return }\sum \_k\in \mathcal{M}{\alpha }_k-\sum \_\alpha \_ki\ne \perp \alpha \_ki\\ & \text{else}:\\ & \alpha \_ki\stackrel{\$}{\leftarrow }{\mathbb{F}}_q\\ & \text{return }\alpha \_ki\\ & \\ & \underline{{\text{Cheat}}^{ki}(\Delta )}\\ & \Delta \_ki\leftarrow \Delta \\ & \text{if }\forall k,i.\text{Delta}\_ki\ne \perp \\ & \text{Cheat}\left(\sum \_(k,i)\Delta \_ki\right)\end{array}}\otimes 1\left(\begin{array}{c}{\text{Start}}_k^{kl},\\ {\text{End}}_k^{kl},\\ {\text{Cheat}}^{kl}\end{array}\right)\\ \circ \\ F[\text{Multiply}]\end{array}$$

In essence, this is just a more complicated variant of the simulator from the previous proof. All that matters is that the sum of all shares is correct, so we can just keep using junk up until the very last share, at which point we need to ensure that the result is correct. We also need to aggregate the cheating values used by all of the malicious parties, in order to get just a single bias in the end.

$■$

Triples

Definition (Triple Generation):

$$\boxed{\begin{array}{c}\mathcal{P}[\text{Triple}]\\ \\ \boxed{\begin{array}{rl}& P_i\\ & \\ & \underline{(1){\text{Triple}}_i():}\\ & f_i,e_i\stackrel{\$}{\leftarrow }{\mathbb{F}}_q[X]\_\le t-1\\ & F_i,E_i\leftarrow f_i\cdot G,e_i\cdot G\\ & {\text{SetCommit}}_i((F_i,E_i))\\ & {\text{Commit}}_i()\\ & {\text{SetMask}}_i()\\ & \\ & {\text{WaitCommit}}_i()\\ & {\text{WaitMask}}_i()\\ & {\text{Open}}_i()\\ & {\pi }_i^0\leftarrow {\text{Prove}}^{\phi }(F_i(0);f_i(0))\\ & {\pi }_i^1\leftarrow {\text{Prove}}^{\phi }(E_i(0);e_i(0))\\ & {\Rsh }_i(\star ,({\pi }_i^0,{\pi }_i^1),0)\\ & {\Rsh }_i(\star ,[(f_i(j),e_i(j))\mid j\in [n]],1)\\ & \\ & (F\_\bullet ,E\_\bullet )\leftarrow {\text{WaitOpen}}_i()\\ & ({\pi }^0\_\bullet i,{\pi }^1\_\bullet i)\leftarrow {\Lsh }_i(\star ,1)\\ & (a\_\bullet i,b\_\bullet i)\leftarrow {\Lsh }_i(\star ,1)\\ & a_i\leftarrow \sum _{j}a\_ji,F\leftarrow \sum _j{F}_j(0)\\ & b_i\leftarrow \sum _{j}a\_ji,E\leftarrow \sum _j{E}_j(0)\\ & {\text{bad}}^0\leftarrow \exists j.\neg {\text{Verify}}^{\phi }({\pi }_j^0,F_j(0))\\ & {\text{bad}}^1\leftarrow \exists j.\neg {\text{Verify}}^{\phi }({\pi }_j^1,E_j(0))\\ & \text{if }{a}_i\cdot G\ne E(i)\vee b_i\cdot G\ne F(i)\vee {\text{bad}}^0\vee {\text{bad}}^1\\ & \text{stop}(\star ,0)\\ & {\text{Multiply}}_i(f_i(0),e_i(0))\\ & C_i\leftarrow e_i(0)\cdot F(0)\\ & {\pi }_i^2\leftarrow {\text{Prove}}^{\psi }(E_i(0),F(0),C_i;e_i(0))\\ & {\Rsh }_i(\star ,(C_i,{\pi }_i),1)\\ & \\ & (C\_\bullet ,{\pi }^2\_\bullet ){\Lsh }_i(\star ,1)\\ & \text{if }\exists j.\neg {\text{Verify}}^{\psi }({\pi }_j^2,(E_j(0),F(0),C_j))\\ & \text{stop}(\star ,1)\\ & z_i\leftarrow {\text{WaitMultiply}}_i()\\ & {\text{Share}}_i(z_i)\\ & c_i\leftarrow {\text{WaitShare}}_i(C)\\ & \text{return }(a_i,b_i,c_i,E(0),F(0),C)\end{array}}\begin{array}{c}F[\text{ZK}(\phi )]\\ \otimes \\ F[\text{ZK}(\psi )]\\ \otimes \\ F[\text{SyncComm}]\\ ⊚\\ F[\text{Stop}]\end{array}\\ \\ \text{Leakage}:=\{\text{stop}\}\end{array}}⊲\begin{array}{c}\mathcal{P}[\text{Commit}]\\ \otimes \\ \mathcal{P}[\text{Convert}]\\ \otimes \\ \mathcal{P}[\text{Multiply}]\end{array}$$

$\square$

This protocol is very long, but relatively straightforward. The idea is that you first generate $a$ and $b$, and commit to their sharings as polynomials. Then you prove that you know your secret share, and convert those to threshold shares. Concurrently, you also run multiplication to get a secret sharing of $a\ast b$, and run a little protocol to learn $a\ast b\cdot G$, using ZK proofs to make sure that this check value $C$ has been learned correctly. Finally, you can use this to verify your share of the multiplication, detecting cheating there, including inconsistent shares.

Definition (Ideal Triple Generation):

$$\boxed{\begin{array}{c}\mathcal{P}[\text{IdealTriple}]\\ \\ \boxed{\begin{array}{rl}& P_i\\ & \\ & \underline{(1){\text{Triple}}_i():}\\ & {\text{Set}}_i(\star )\\ & {\text{WaitSet}}_i(\star ,\text{true})\\ & {\text{Share}}_i^0(\star )\\ & (a_i,b_i)\leftarrow {\text{WaitShares}}_i^0(\text{true})\\ & {\text{Share}}_i^1(\star )\\ & c_i\leftarrow {\text{WaitShares}}_i^1(\text{true})\\ & (A,B,C)\leftarrow ({\text{F}}^{A,h}()(0),{\text{F}}^{B,h}()(0),{\text{F}}^{C,h}()(0))\\ & \text{return }(a_i,b_i,c_i,A,B,C)\end{array}}\begin{array}{c}\boxed{\begin{array}{rl}& F[\text{Convert}]\\ & \\ & f^{A,h},f^{B,h},\stackrel{\$}{\leftarrow }{\mathbb{F}}_q[X]\_\le t-1\\ & f^{A,h},f^{B,h},\stackrel{\$}{\leftarrow }\{f\in {\mathbb{F}}_q[X]\_\le t-1\mid f(0)=f^{A,h}(0)\cdot f^{B,h}(0)\}\\ & F^{A,m},F^{B,m},F^{C,m},\text{ready}\_ij,{\text{shared}}^{\{0,1\}}\_ij,a\_i,b\_i,c\_i,x_i^A,x_i^B,x_i^C\leftarrow \perp \\ & \\ & \underline{{\text{Set}}_i(S):}\\ & \text{ready}\_ij\leftarrow \text{true}(\forall j\in S)\\ & \\ & \underline{(1)\text{Cheat}(F^A,F^B,F^C):}\\ & \text{assert }F(0)=0\wedge \text{deg}(F)=t-1\\ & F^{A,m},F^{B,m},F^{C,m}\leftarrow F^A,F^B,F^C\\ & \\ & \underline{{\text{WaitSet}}_i(S,m):}\\ & \text{wait}\_(i,0)\forall j\in S.\text{ready}\_ji\wedge (m\to F^{\bullet ,m}\ne \perp )\\ & \\ & \underline{{\text{Share}}_i^0(S):}\\ & {\text{shared}}^0\_ij\leftarrow \text{true}(\forall j\in S)\\ & \\ & \underline{{\text{CheatShare}}^0(S,{\hat{x}}^A\_\bullet ,{\hat{x}}^B\_\bullet ):}\\ & \text{for }Y\in \{A,B\}:\\ & \text{assert }{F}^{Y,m}\ne \perp \wedge \forall j\in S.{\hat{x}}_j^Y\cdot G=F^{Y,m}(j)\\ & \text{for }j.x_j^Y\ne \perp :x_j^Y\leftarrow {\hat{x}}_j^Y\\ & \\ & \underline{{\text{WaitShares}}_i^0(h):}\\ & \text{if }h:\\ & \text{wait}\_(i,1)x_i^A,x_i^B\ne \perp \wedge \forall j.\wedge \forall j.{\text{shared}}^0\_ji\\ & \text{return }(f^{A,h}(i)+x_i^A,f^{B,h}(i)+x_i^B)\\ & \text{else}:\\ & \text{wait}\_(i,1)\forall j\in \mathcal{H}.{\text{shared}}^0\_ji\ne \perp \\ & \text{return }(f^{A,h}(i),f^{B,h}(i))\\ & \\ & \underline{{\text{Share}}_i^1(S):}\\ & {\text{shared}}^1\_ij\leftarrow \text{true}(\forall j\in S)\\ & \\ & \underline{{\text{CheatShare}}^1(S,{\hat{x}}^C\_\bullet ):}\\ & \text{assert }{F}^{C,m}\ne \perp \wedge \forall j\in S.{\hat{x}}_j^C\cdot G=F^{C,m}(j)\\ & \text{for }j.x_j^C=\perp :x_j^C\leftarrow {\hat{x}}_j^C\\ & \\ & \underline{{\text{WaitShares}}_i^1():}\\ & \text{wait}\_(i,1)x_i^C,\ne \perp \wedge \forall j.\wedge \forall j.{\text{shared}}^1\_ji\\ & \text{return }{f}^{C,h}(i)+x_i^C\\ & \\ & \underline{{\text{F}}^{Y\in \{A,B,C\},h}():}\\ & \text{wait }{F}^{Y,m}\ne \perp \wedge \forall i.\exists j.\text{ready}\_ij\\ & \text{return }{f}^{Y,h}\cdot G\end{array}}\\ \otimes \\ F[\text{Sync}]\\ ⊚\\ F[\text{Stop}]\end{array}\\ \\ \text{Leakage}:=\{\text{stop}\}\end{array}}$$

The ideal triple generation protocol is as you might expect, with the functionality itself doing the multiplication perfectly. However, we once again have the various tweaks to secret sharing induced by the commit reveal paradigm. See the key sharing document for some discussion about these artifacts, which naturally show up here again.

Lemma

For a negligible $ϵ$, and up to $t-1$ corrupt parties:

$$\mathcal{P}[\text{Triple}]\stackrel{ϵ}{⇝}\mathcal{P}[\text{IdealTriple}]$$

Proof

Clearly, $\mathcal{P}[\text{Triple}]$ is simulated by the following protocol making use of $\mathcal{P}[\text{SplitShare}]$ twice:

$$\boxed{\begin{array}{c}{\mathcal{P}}^0\\ \\ \boxed{\begin{array}{rl}& P_i\\ & \\ & \underline{(1){\text{Triple}}_i():}\\ & z_i^A,z_i^B\stackrel{\$}{\leftarrow }{\mathbb{F}}_q\\ & {\text{Set}}_i^0(z_i^A),{\text{Set}}_i^1(z_i^B)\\ & {\text{SetMask}}_i()\\ & \\ & {\text{WaitSet}}_i^0(),{\text{WaitSet}}_i^1()\\ & {\text{WaitMask}}_i()\\ & {\text{Share}}_i^0(),{\text{Share}}_i^1\\ & \\ & a_i\leftarrow {\text{WaitShare}}_i^0(),b_i\leftarrow {\text{WaitShare}}_i^1()\\ & {\text{StartMultiply}}_i(z_i^A,z_i^B)\\ & \text{A}\leftarrow \sum _i{\text{Z}}^0(i),\text{B}\leftarrow \sum _i{\text{Z}}^1(i)\\ & C_i\leftarrow z_i^B\cdot A\\ & {\pi }_i^2\leftarrow {\text{Prove}}^{\psi }({\text{Z}}^1(i),A,C_i;z_i^B)\\ & {\Rsh }_i(\star ,(C_i,{\pi }_i),1)\\ & \\ & (C\_\bullet ,{\pi }^2\_\bullet ){\Lsh }_i(\star ,1)\\ & \text{if }\exists j.\neg {\text{Verify}}^{\psi }({\pi }_j^2,({\text{Z}}^1(j),A,C_j))\\ & \text{stop}(\star ,1)\\ & z_i^C\leftarrow {\text{EndMultiply}}_i()\\ & {\text{Share}}_i(z_i^C)\\ & c_i\leftarrow {\text{WaitShare}}_i()\\ & C\leftarrow \sum _i{C}_i\\ & \text{if }\sum _i{\text{Z}}^2(i)\ne C\\ & \text{stop}(\star ,2)\\ & \text{return }(a_i,b_i,c_i,A,B,C)\end{array}}\end{array}}⊲\begin{array}{c}\mathcal{P}[\text{SplitShare}]\\ \otimes \\ \mathcal{P}[\text{SplitShare}]\\ \otimes \\ \mathcal{P}[\text{Convert}]\\ \otimes \\ \mathcal{P}[\text{Multiply}]\end{array}$$

From here, we can jump to the final protocol with an atrocious simulator:

$$\begin{array}{c}\boxed{\begin{array}{rl}& {\Gamma }_H^0\\ & \dots \end{array}}\otimes \boxed{\begin{array}{rl}& S\\ & z_i^A,z_i^B\stackrel{\$}{\leftarrow }{\mathbb{F}}_q(\forall i\in \mathcal{H}/\{1\})\\ & Z_i^A,Z_i^B\leftarrow z_i^A\cdot G,z_i^B\cdot G(\forall i\in \mathcal{H}/\{1\})\\ & z_i^A,z_i^B,Z_i^A,Z_i^B\leftarrow \perp (\forall i\in \mathcal{M})\\ & {\gamma }_i\stackrel{\$}{\leftarrow }{\mathbb{F}}_q(\forall i\ne 1)\\ & {\hat{z}}^C\_ij,x_i^A,x_i^B,x_i^C,F^{A,m},F^{B,m},F^{C,m},\hat{m}\_ij\leftarrow \perp \\ & {\text{ready}}^A\_ij,{\text{ready}}^B\_ij,{\text{ready}}^C\_ij\leftarrow \perp \\ & {\text{shared}}^A\_ij,{\text{shared}}^B\_ij,{\text{shared}}^C\_ij\leftarrow \perp \\ & \\ & \underline{{\text{Set}}_k^0(S,z,Z):}\\ & \text{assert }z\ne \perp \vee Z\ne \perp \\ & \text{if }{z}_k^A,Z_k^A=\perp \wedge z\ne \perp :z_k^A\leftarrow z,Z_k^A\leftarrow z\cdot G\\ & \text{elif }{Z}_k^A=\perp \wedge Z\ne \perp :Z_k^A\leftarrow Z\\ & {\text{ready}}^A\_kj\leftarrow \text{true }(\forall j\in S)\\ & {\text{Set?}}_k()\\ & \\ & \underline{{\text{Set}}_k^1(S,z,Z):}\\ & \text{assert }z\ne \perp \vee Z\ne \perp \\ & \text{if }{z}_k^B,Z_k^B=\perp \wedge z\ne \perp :z_k^B\leftarrow z,Z_k^B\leftarrow z\cdot G\\ & \text{elif }{Z}_k^B=\perp \wedge Z\ne \perp :Z_k^B\leftarrow Z\\ & {\text{ready}}^A\_kj\leftarrow \text{true }(\forall j\in S)\\ & {\text{ready}}^B\_kj\leftarrow \text{true }(\forall j\in S)\\ & {\text{Set?}}_k()\\ & \\ & \underline{{\text{SetMask}}_k(S):}\\ & {\text{ready}}^C\_kj\leftarrow \text{true }(\forall j\in S)\\ & {\text{Set?}}_k()\\ & \\ & \underline{{\text{Set?}}_k():}\\ & \text{for }j.\forall Y\in \{A,B,C\}.{\text{ready}}^Y\_kj:\\ & \text{super}.{\text{Set}}_k(\{j\})\\ & \\ & \underline{{\text{WaitSet}}_k^0(S,m):}\\ & \text{wait }\forall j\in S\cap \mathcal{M}.{\text{ready}}^A\_jk\\ & \text{super}.{\text{WaitSet}}_k(S\cap \mathcal{H})\\ & \\ & \underline{{\text{WaitSet}}_k^1(S,m):}\\ & \text{wait }\forall j\in S\cap \mathcal{M}.{\text{ready}}^B\_jk\\ & \text{super}.{\text{WaitSet}}_k(S\cap \mathcal{H})\\ & \\ & \underline{{\text{WaitMask}}_k(S,m):}\\ & \text{wait }\forall j\in S\cap \mathcal{M}.{\text{ready}}^C\_jk\\ & \text{super}.{\text{WaitSet}}_k(S\cap \mathcal{H})\\ & \\ & \underline{{\text{Share}}_k^0(S,z):}\\ & \text{assert }{Z}_k^A\ne \perp \\ & \text{if }{z}_k^A=\perp :\\ & \text{assert }z\cdot G=Z_k^A\\ & z_k^A\leftarrow z\\ & {\text{shared}}^A\_kj\leftarrow \text{true}(\forall j\in S)\\ & {\text{Share?}}_k^0()\\ & \\ & \underline{{\text{Share}}_k^1(S,z):}\\ & \text{assert }{Z}_k^B\ne \perp \\ & \text{if }{z}_k^B=\perp :\\ & \text{assert }z\cdot G=Z_k^B\\ & z_k^B\leftarrow z\\ & {\text{shared}}^B\_kj\leftarrow \text{true}(\forall j\in S)\\ & {\text{Share?}}_k^0()\\ & \\ & \underline{{\text{WaitShare}}_k^0(h):}\\ & (a_k,b_k)\leftarrow {\text{WaitShares}}_k^0()\\ & \text{return }{a}_k\\ & \\ & \underline{{\text{WaitShare}}_k^1(h):}\\ & (a_k,b_k)\leftarrow {\text{WaitShares}}_k^0()\\ & \text{return }{b}_k\\ & \\ & \underline{(1){\text{StartMultiply}}_k(a\_\bullet ,b\_\bullet ):}\\ & a\_kj\leftarrow a_j,b\_kj\leftarrow b_j\\ & \\ & \underline{(1){\text{Cheat}}_k^{\text{F[Multiply]}}(\Delta ):}\\ & \Delta \leftarrow \Delta \\ & \\ & \underline{{\text{EndMultiply}}_k():}\\ & \text{return }{\gamma }_k-z_k^A\cdot z_k^B\\ & \\ & \underline{{\text{Share}}_k(S,z\_\bullet ):}\\ & \text{for }j\in S.{\hat{z}}^C\_kj=\perp :\\ & \text{for }j\in S.{\hat{z}}^C\_kj=\perp :{\hat{z}}^C\_kj\leftarrow z_j\\ & \text{for }j\in \mathcal{H}.\forall i\in \mathcal{M}.{\hat{z}}^C\_ij\ne \perp :\\ & \text{if }\sum \_i\in \mathcal{H}\text{Z}(j)+\sum \_i\in \mathcal{M}{\hat{z}}^C\_ij\cdot G\ne F^{C,h}(0):\\ & \text{stop}(\{j\})\\ & \text{super}.{\text{Share}}_i^1(S)\\ & \\ & \underline{{\text{Share?}}_k^0():}\\ & \text{for }j.{\text{shared}}^A\_kj\wedge {\text{shared}}^B\_kj:\\ & \text{super}.{\text{Share}}_k^0(\{j\})\\ & \\ & \underline{{\text{WaitShare}}_k(h):}\\ & \text{if }h:\\ & \text{return }{\text{WaitShare}}_k^1()\\ & \text{else}:\\ & \text{wait }{x}_k^C\ne \perp \wedge \forall i\in \mathcal{M}.z^C\_ik\ne \perp \\ & \text{return }{\text{WaitShare}}_k^1()-\sum \_i\in \mathcal{M}{z}^C\_ik-x_k^C\\ & \\ & \underline{{\text{Prove}}^{\psi }(W,P,Q;w):}\\ & \text{assert }w\cdot G=W\wedge w\cdot P=Q\\ & \pi \stackrel{\$}{\leftarrow }{\text{01}}^{2\lambda }\\ & \mu [\pi ]\leftarrow (W,P,Q)\\ & \\ & \underline{{\text{Verify}}^{\psi }(\pi ,(W,P,Q)):}\\ & \text{return }\mu [\pi ]\stackrel{?}{=}(W,P,Q)\\ & \\ & \underline{{\Rsh }_k(S,m\_\bullet ,1)}\\ & \text{for }j\in S\cap \mathcal{H}:\\ & (C_k,\pi )\leftarrow m_j\\ & \text{if }\mu [\pi ]\ne (Z_k^B(),{\text{F}}^{A,h}(0),C_k):\\ & \text{stop}(\{j\})\\ & \hat{m}\_kj\leftarrow m_j(\forall j\in S)\\ & \\ & \underline{{\Lsh }_k(S,1):}\\ & \text{wait}\_(k,1)\forall j\in S\cap \mathcal{M}.\hat{m}\_kj\ne \perp \\ & r\_\bullet \leftarrow \perp \\ & \text{for }j\in S\cap \mathcal{H}.\nexists i.\hat{m}\_ij\ne \perp :\\ & \pi \stackrel{\$}{\leftarrow }{\text{01}}^{2\lambda }\\ & \mu [\pi ]\leftarrow ({\text{Z}}^1(j),F^{A,h}(0),\text{C}(j))\\ & r_j\leftarrow (C_j,\pi )\\ & r_j\leftarrow \hat{m}\_kj(\forall j\in S)\\ & \text{return }r\_\bullet \\ & \\ & \underline{(1){\text{Cheat}}^0(F):}\\ & \text{assert }F(0)=0\wedge \text{deg}(F)=t-1\\ & F^{A,m}\leftarrow F\\ & \text{Cheat?}()\\ & \\ & \underline{{\text{CheatShare}}^0(S,\hat{x}\_\bullet ):}\\ & \text{assert }{F}^{A,m}\ne \perp \wedge \forall j\in S.{\hat{x}}_j\cdot G=F^{A,m}(j)\\ & x_j^A\leftarrow {\hat{x}}_j(\forall j\in S)\\ & \text{CheatShare?}()\\ & \\ & \underline{{\text{F}}^{0,h}():}\\ & \text{return }{\text{F}}^{A,h}-{\text{F}}^{A,h}(0)\\ & \\ & \underline{(1){\text{Cheat}}^1(F):}\\ & \text{assert }F(0)=0\wedge \text{deg}(F)=t-1\\ & F^{B,m}\leftarrow F\\ & \text{Cheat?}()\\ & \\ & \underline{{\text{CheatShare}}^1(S,\hat{x}\_\bullet ):}\\ & \text{assert }{F}^{B,m}\ne \perp \wedge \forall j\in S.{\hat{x}}_j\cdot G=F^{B,m}(j)\\ & x_j^B\leftarrow {\hat{x}}_j(\forall j\in S)\\ & \text{CheatShare?}()\\ & \\ & \underline{{\text{F}}^{1,h}():}\\ & \text{return }{\text{F}}^{B,h}-{\text{F}}^{B,h}(0)\\ & \\ & \underline{(1){\text{Cheat}}^{\text{F[Convert]}}(F):}\\ & \text{assert }F(0)=0\wedge \text{deg}(F)=t-1\\ & F^{C,m}\leftarrow F\\ & \text{Cheat?}()\\ & \\ & \underline{\text{Cheat?}()}\\ & \text{if }{F}^{A,m},F^{B,m},F^{C,m}\ne \perp :\\ & \text{super}.\text{Cheat}(F^{A,m},F^{B,m},F^{C,m})\\ & \\ & \underline{\text{CheatShare?}():}\\ & \text{for }j.{\hat{x}}_j^A,{\hat{x}}_j^B\ne \perp :\\ & \text{super}.{\text{CheatShare}}^0(\{j\},{\hat{x}}^A\_\bullet ,{\hat{x}}^B\_\bullet )\\ & \\ & \underline{\text{CheatShare}(S,\hat{x}\_\bullet ):}\\ & \text{assert }{F}^{C,m}\ne \perp \wedge \forall j\in S.{\hat{x}}_j\cdot G=F^{C,m}(j)\\ & {\hat{x}}_j^C\leftarrow {\hat{x}}_j(\forall j\in S)\\ & \text{super}.{\text{CheatShare}}^1(S,\hat{x}\_\bullet )\\ & \\ & \underline{{\text{F}}^h():}\\ & \text{return }{\text{F}}^{C,h}-{\text{F}}^{C,h}(0)\\ & \\ & \underline{{\text{Z}}^0(i):}\\ & \text{return }{\text{F}}^{A,h}(0)-\sum _j{Z}_j^A\text{ if }i=1\text{ else }{Z}_i^A\\ & \\ & \underline{{\text{Z}}^1(i):}\\ & \text{return }{\text{F}}^{B,h}(0)-\sum _j{Z}_j^B\text{ if }i=1\text{ else }{Z}_i^B\\ & \\ & \underline{\text{C}(i):}\\ & \text{return }{\text{F}}^{C,h}(0)-\sum _j{z}_j^A\cdot {\text{F}}^{B,h}(0)\text{ if }i=1\text{ else }{z}_i^A\cdot {\text{F}}^{B,h}(0)\\ & \\ & \underline{\text{Z}(i):}\\ & \text{return }\hat{C}()-\sum _i{\gamma }_i\cdot G\text{ if }i=1\text{ else }{\gamma }_i\cdot {\text{F}}^{B,h}(0)\\ & \\ & \underline{\hat{C}():}\\ & \text{wait }\text{for all variables used below}\\ & O\_11={\text{F}}^{C,h}(0)-\sum \_i\in \mathcal{H}/\{1\}{z}_i^B\cdot {\text{F}}^{A,h}(0)-\sum \_i\in \mathcal{H}/\{1\}{z}_i^A\cdot {\text{F}}^{B,h}(0)-O\_hh\\ & O\_h1=\sum \_i\in \mathcal{H},j\in \mathcal{H}/\{1\}{z}_j^B\cdot Z_i^A\cdot G\\ & O\_h1=\sum \_i\in \mathcal{H}/\{1\},j\in \mathcal{H}{z}_i^A\cdot Z_j^B\cdot G\\ & O\_hh=\sum \_i,j\in \mathcal{H}/\{1\}{z}_i^A\cdot z_j^B\cdot G\\ & O\_hm=\sum \_i\in \mathcal{H},j\in \mathcal{M}{\text{Z}}^0(i)\cdot b\_ji\\ & O\_mh=\sum \_i\in \mathcal{M},j\in \mathcal{H}a\_ij\cdot {\text{Z}}^1(j)\\ & O\_mm=\sum \_i,j\in \mathcal{M}a\_ij\cdot b\_ji\cdot G\\ & \text{return }O\_11+O\_1h+O\_h1+O\_hh+O\_hm+O\_mh+O\_mm+\Delta \cdot G\\ & \\ & \dots \end{array}}\\ \circ \\ F[\text{Messages}]⊚F[\text{Stop}]\end{array}$$

The vast majority of this simulator is just mindless bookkeeping. The main part of interest is the $\hat{C}$ function, which basically simulates the expected result of the multiplication, based on the bad values used by the adversary. In essence, this reflects the fact that the adversary learns nothing about the other parties shares through the combination of the faulty multiplication protocol and share check phase, because they can calculate the results “in the exponent” already.

That’s the only real tricky part of the simulator, the rest is just adding in necessary checks ourselves, and coalescing contributions from adversaries, as we’ve done many times.

$■$