Cait-Sith Security (4): Signing

For the sake of simplicity, we use a simpler key generation and triple protocol as ideal functionalities, to isolate the analysis of our presignature and signature protocols.

Presigning

Definition (Presignatures):

$$\boxed{\begin{array}{c}\mathcal{P}[\text{Presign}]\\ \\ \boxed{\begin{array}{rl}& P_i\\ & \\ & \underline{(1){\text{Presign}}_i^{\tau }():}\\ & (a_i,b_i,c_i,A,B,C)\leftarrow {\text{Triple}}_i^{(\tau ,0)}()\\ & (k_i,d_i,{\text{kd}}_i,K,D,\text{KD})\leftarrow {\text{Triple}}_i^{(\tau ,1)}()\\ & {\Rsh }_i^{\tau }(\star ,\lambda (\mathcal{P})\cdot {\text{kd}}_i,1)\\ & {\Rsh }_i^{\tau }(\star ,\lambda (\mathcal{P})\cdot (k_i+a_i),2)\\ & {\Rsh }_i^{\tau }(\star ,\lambda (\mathcal{P})\cdot (x_i+b_i),3)\\ & \\ & \text{kd}\_\bullet {\Lsh }_i^{\tau }(\star ,1)\\ & \text{ka}\_\bullet {\Lsh }_i^{\tau }(\star ,2)\\ & \text{xb}\_\bullet {\Lsh }_i^{\tau }(\star ,3)\\ & \text{kd}\leftarrow \sum _j{\text{kd}}_j\\ & \text{if }\text{kd}\cdot G\ne \text{KD}:\text{stop}(\star ,1)\\ & \text{ka}\leftarrow \sum _j{\text{ka}}_j\\ & \text{if }\text{ka}\cdot G\ne K+A:\text{stop}(\star ,2)\\ & \text{xb}\leftarrow \sum _j{\text{xb}}_j\\ & \text{if }\text{xb}\cdot G\ne X+B:\text{stop}(\star ,3)\\ & \\ & R\leftarrow \frac{1}{\text{kd}}\cdot D\\ & {\sigma }_i\leftarrow \text{ka}\cdot x_i-\text{xb}\cdot a_i+c_i\\ & \text{return }(X,x_i,R,k_i,{\sigma }_i)\end{array}}\begin{array}{c}\boxed{\begin{array}{rl}& F[\text{Setup}]\\ & \\ & f\stackrel{\$}{\leftarrow }{\mathbb{F}}_q[X]\_\le t-1\\ & \\ & \underline{{\text{Key}}_i():}\\ & \text{return }(f(0)\cdot G,f(i))\end{array}}\\ \otimes \\ \boxed{\begin{array}{rl}& F[\text{Triple}]\\ & \\ & f^{A,\tau },f^{B,\tau }\stackrel{\$}{\leftarrow }{\mathbb{F}}_q[X]\_\le t-1\\ & f^{C,\tau }\stackrel{\$}{\leftarrow }\{f\in {\mathbb{F}}_q[X]\_\le t-1\mid f(0)=f^{A,\tau }(0)\cdot f^{B,\tau }\}\\ & \\ & \underline{{\text{Triple}}_i^{\tau }():}\\ & (a_i,b_i,c_i)\leftarrow (f^{A,\tau }(i),f^{B,\tau }(i),f^{C,\tau }(i))\\ & (A,B,C)\leftarrow (f^{A,\tau }(0)\cdot G,f^{B,\tau }(0)\cdot G,f^{C,\tau }(0)\cdot G)\\ & \text{return }(a_i,b_i,c_i,A,B,C)\end{array}}\\ \otimes \\ F[\text{Triple}]\\ \otimes \\ F[\text{SyncComm}{]}^{\mathbb{N}}\\ ⊚\\ F[\text{Stop}]\end{array}\\ \\ \text{Leakage}:=\{\text{stop}\}\end{array}}$$

$\square$

The functionalities we use here are perfect, in essence. The idea behind the presignature functionality is relatively simple. One triple is used to help multiply $k$ and $x$, and the other contains $k$ itself, which we use to help invert $k$ for the signature formula.

For convenience, we make it so that the presignature gives us $X$ and $x$ (secret shared).

Another convention is that the same key $x$ is used for an arbitrary number of signatures, hence $\mathbb{N}$ instances. We use $\tau$ as index to denote this instances.

Definition (Ideal Presignatures):

$$\boxed{\begin{array}{c}\mathcal{P}[\text{IdealPresign}]\\ \\ \boxed{\begin{array}{rl}& P_i\\ & \\ & \underline{(1){\text{Presign}}_i^{\tau }():}\\ & {\text{Sync}}_i^{\tau }(\star ,0)\\ & {\text{WaitSync}}_i^{\tau }(\star ,0)\\ & \text{return }{\text{Presign}}_i^{\tau }()\end{array}}\begin{array}{c}\boxed{\begin{array}{rl}& F[\text{Presign}]\\ & \\ & f^X,f^{K,\tau },\stackrel{\$}{\leftarrow }{\mathbb{F}}_q[X]\_\le t-1\\ & f^{\Sigma ,\tau },\stackrel{\$}{\leftarrow }\{f\in {\mathbb{F}}_q[X]\_\le t-1\mid f(0)=0\}\\ & \\ & \underline{{\text{Presign}}_i^{\tau }():}\\ & X\leftarrow f^X(0)\cdot G\\ & x_i\leftarrow f^X(i)\\ & R\leftarrow \frac{1}{f^{K,\tau }(0)}\cdot G\\ & k_i\leftarrow f^{K,\tau }(i)\\ & {\sigma }_i\leftarrow f^X(0)\cdot f^{K,\tau }(0)+f^{\Sigma ,\tau }(i)\\ & \text{return }(X,x_i,R,k_i,{\sigma }_i)\\ & \\ & \underline{{\text{K}}^{\tau }():}\\ & \text{return }{f}^{K,\tau }(0)\cdot G\\ & \underline{{\text{XK}}^{\tau }():}\\ & \text{return }{f}^X(0)\cdot f^{K,\tau }(0)\cdot G\end{array}}\\ \otimes \\ F[\text{Sync}{]}^{\mathbb{N}}\\ ⊚\\ F[\text{Stop}]\end{array}\\ \\ \text{Leakage}:=\{\text{stop}\}\end{array}}$$

$\square$

The ideal functionality basically spits out presignatures at will, all under the same key. We also get access to $k\cdot G$ and $kx\cdot G$, in addition to $k^{-1}\cdot G$. $kx\cdot G$ is actually something you learn from a signature anyhow, once it’s completed.

Lemma: For a negligible $ϵ$, and up to $t-1$ malicious corruptions, we have:

$$\mathcal{P}[\text{Presign}]\stackrel{ϵ}{⇝}\mathcal{P}[\text{IdealPresign}]$$

Proof:

First, we note that $\mathcal{P}[\text{Presign}]⇝{\mathcal{P}}^0$, which modifies $P_i$ to consolidate message sending:

$$\boxed{\begin{array}{rl}& P_i\\ & \\ & \underline{(1){\text{Presign}}_i^{\tau }():}\\ & (a_i,b_i,c_i,A,B,C)\leftarrow {\text{Triple}}_i^{(\tau ,0)}()\\ & (k_i,d_i,{\text{kd}}_i,K,D,\text{KD})\leftarrow {\text{Triple}}_i^{(\tau ,1)}()\\ & {\Rsh }_i^{\tau }(\star ,(\lambda (\mathcal{P})\cdot {\text{kd}}_i,\lambda (\mathcal{P})\cdot (k_i+a_i),\lambda (\mathcal{P})\cdot (x_i+b_i)),0)\\ & \\ & (\text{kd}\_\bullet ,\text{ka}\_\bullet ,\text{xb}\_\bullet ){\Lsh }_i^{\tau }(\star ,0)\\ & \text{kd}\leftarrow \sum _j{\text{kd}}_j\\ & \text{if }\text{kd}\cdot G\ne \text{KD}:\text{stop}(\star ,0)\\ & \text{ka}\leftarrow \sum _j{\text{ka}}_j\\ & \text{if }\text{ka}\cdot G\ne K+A:\text{stop}(\star ,0)\\ & \text{xb}\leftarrow \sum _j{\text{xb}}_j\\ & \text{if }\text{xb}\cdot G\ne X+B:\text{stop}(\star ,0)\\ & \\ & R\leftarrow \frac{1}{\text{kd}}\cdot D\\ & {\sigma }_i\leftarrow \text{ka}\cdot x_i-\text{xb}\cdot a_i+c_i\\ & \text{return }(X,R,k_i,{\sigma }_i)\end{array}}$$

A sketch of the simulator here would be to delay sending messages from malicious to honest parties until all three bundles have been sent, and to detect failures early to make all aborts look the same.

From ${\mathcal{P}}^0$, we can jump to $\mathcal{P}[\text{IdealPresign}]$ directly.

$$\begin{array}{c}\boxed{\begin{array}{rl}& {\Gamma }_H^0\\ & \dots \end{array}}\otimes \boxed{\begin{array}{rl}& S\\ & {\alpha }_j^{\tau },{\beta }_j^{\tau },d_j^{\tau },{\delta }_j^{\tau }\stackrel{\$}{\leftarrow }{\mathbb{F}}_q\\ & {\alpha }^{\tau }\leftarrow \sum _j{\alpha }_j^{\tau },{\beta }^{\tau }\leftarrow \sum _j{\beta }_j^{\tau },{\delta }^{\tau }\leftarrow \sum _j{\delta }_j^{\tau }\\ & {\gamma }_j^{\tau }\stackrel{\$}{\leftarrow }\{({\gamma }_1,\dots ,{\gamma }_n)\mid \sum _j{\gamma }_j=\alpha \cdot \beta \}\\ & (X,x_k^{\tau },R^{\tau },k_k^{\tau },{\sigma }_k^{\tau })\leftarrow {\text{Presign}}_k^{\tau }()\\ & K^{\tau }\leftarrow {\text{K}}^{\tau }(),{\text{XK}}^{\tau }\leftarrow {\text{XK}}^{\tau }()\\ & \\ & A^{\tau }\leftarrow {\alpha }^{\tau }\cdot G-K^{\tau }\\ & B^{\tau }\leftarrow {\beta }^{\tau }\cdot G-X\\ & C^{\tau }\leftarrow {\alpha }^{\tau }{\beta }^{\tau }-{\alpha }^{\tau }\cdot X-{\beta }^{\tau }\cdot K^{\tau }+{\text{XK}}^{\tau }\\ & D^{\tau }\leftarrow {\delta }^{\tau }\cdot R^{\tau },{\text{KD}}^{\tau }\leftarrow {\delta }^{\tau }\cdot G\\ & \\ & \underline{{\text{Triple}}_k^{\tau ,0}():}\\ & a_k\leftarrow {\alpha }_k^{\tau }-k_k^{\tau }\\ & b_k\leftarrow {\beta }_k^{\tau }-k_k^{\tau }\\ & c_k\leftarrow {\gamma }_k^{\tau }-\alpha \cdot x-\beta \cdot k+{\sigma }_k^{\tau }\\ & \text{return }(a_k,b_k,c_k,A^{\tau },B^{\tau },C^{\tau })\\ & \\ & \underline{{\text{Triple}}_k^{\tau ,1}():}\\ & \text{return }(k_k^{\tau },d_k^{\tau },{\delta }_k^{\tau },K^{\tau },D^{\tau },{\text{KD}}^{\tau })\\ & \\ & \\ & m^{\tau }\_ij\leftarrow \perp \\ & \\ & \underline{{\Rsh }_k^{\tau }(S,\hat{m}\_\bullet =(\text{kd}\_\bullet ,\text{ka}\_\bullet ,\text{xb}\_\bullet ),0):}\\ & m^{\tau }\_kj\leftarrow \hat{m}\_kj(\forall j\in S)\\ & {\text{Sync}}_k(S\cap \mathcal{H},0)\\ & \text{for }j\in \mathcal{H}.\forall k\in \mathcal{M}.m^{\tau }\_kj\ne \perp :\\ & ({\text{kd}}_k,{\text{ka}}_k,{\text{xb}}_k)\leftarrow m\_kj\\ & \widehat{\text{kd}}=\sum \_j\in \mathcal{H}{\delta }_j^{\tau }+\sum \_k\in \mathcal{M}{\text{kd}}_k\\ & \widehat{\text{ka}}=\sum \_j\in \mathcal{H}{\alpha }_j^{\tau }+\sum \_k\in \mathcal{M}{\text{ka}}_k\\ & \widehat{\text{xb}}=\sum \_j\in \mathcal{H}{\beta }_j^{\tau }+\sum \_k\in \mathcal{M}{\text{xb}}_k\\ & \text{if }\widehat{\text{kd}}\cdot G\ne {\text{KD}}^{\tau }\vee \widehat{\text{ka}}\cdot G\ne K^{\tau }+A^{\tau }\vee \widehat{\text{xb}}\cdot G\ne X+B^{\tau }:\\ & \text{stop}(\{j\},0)\\ & \\ & \underline{{\Lsh }_k^{\tau }(S,0):}\\ & {\text{WaitSync}}_k(S\cap \mathcal{H},0)\\ & \text{wait}\_(k,0)\forall j\in S.m^{\tau }\_jk\ne \perp \\ & r_j\leftarrow m^{\tau }\_jk(j\in S\cap \mathcal{M})\\ & r_j\leftarrow ({\delta }_j^{\tau },{\alpha }_j^{\tau },{\beta }_j^{\tau })(j\in S\cap \mathcal{H})\\ & \text{return }r\_\bullet \\ & \\ & \dots \end{array}}\\ \circ \\ F[\text{Presign}]⊚F[\text{Stop}]\end{array}$$

The idea behind the simulator is that you generate random values for the messages you’re going to receive, and then use those to reverse engineer what the large values like $A,B$ should be.

$■$

Signing

Signatures are pretty straightforward once you have presignatures.

Definition (Signing):

$$\boxed{\begin{array}{c}\mathcal{P}[\text{Sign}]\\ \\ \boxed{\begin{array}{rl}& P_i\\ & \\ & \underline{(1){\text{Sign}}_i^{\tau }():}\\ & (X,\bullet ,R,k_i,{\sigma }_i)\leftarrow {\text{Presign}}_i^{\tau }()\\ & m\leftarrow {\text{GetMessage}}^{\tau }()\\ & s_i\leftarrow \text{Hash}(m)\cdot k_i+x(R)\cdot {\sigma }_i\\ & {\Rsh }_i(\star ,s_i,1)\\ & s\_\bullet \leftarrow {\Lsh }_i(\star ,1)\\ & s\leftarrow \sum _j{s}_j\\ & \text{if }\neg \text{ECDSA}.\text{Verify}(X,m,(R,s)):\\ & \text{stop}(\star ,1)\\ & \text{return }s\end{array}}\begin{array}{c}\boxed{\begin{array}{rl}& F[\text{Messages}]\\ & \\ & m^{\tau }\leftarrow \perp \\ & \underline{{\text{SetMessage}}^{\tau }(m):}\\ & \text{if }{m}^{\tau }=\perp :m^{\tau }\leftarrow m\\ & \\ & \underline{{\text{GetMessage}}^{\tau }():}\\ & \text{wait }{m}^{\tau }\ne \perp \\ & \text{return }{m}^{\tau }\end{array}}\\ \otimes \\ F[\text{SyncComm}{]}^{\mathbb{N}}\\ ⊚\\ F[\text{Stop}]\end{array}\\ \\ \text{Leakage}:=\{\text{stop},{\text{SetMessage}}^{\tau }\}\end{array}}⊲\mathcal{P}[\text{Presign}]$$

$\square$

We assume that there’s a separate functionality which provides consensus on the message to sign in each instance.

Definition (Ideal Signing):

$$\boxed{\begin{array}{c}\mathcal{P}[\text{IdealSign}]\\ \\ \boxed{\begin{array}{rl}& P_i\\ & \\ & \underline{(1){\text{Sign}}_i^{\tau }():}\\ & {\text{Sync}}_i^{\tau }(\star ,0)\\ & {\text{WaitSync}}_i^{\tau }(\star ,0)\\ & {\text{Ready}}_i^{\tau }(\star )\\ & \text{return }{\text{Sig}}_i^{\tau }()\end{array}}\begin{array}{c}\boxed{\begin{array}{rl}& F[\text{Sign}]\\ & \\ & \text{ready}\_{ij}^{\tau }\leftarrow \text{false}\\ & x,k^{\tau }\stackrel{\$}{\leftarrow }{\mathbb{F}}_q\\ & \\ & \underline{{\text{Ready}}_i^{\tau }(S):}\\ & {\text{ready}}^{\tau }\_ij\leftarrow \text{true}(\forall j\in S)\\ & \\ & \underline{{\text{WaitReady}}_i^{\tau }(S):}\\ & \text{wait}\_(i,1)\forall j\in \mathcal{S}.{\text{ready}}^{\tau }\_ji\\ & \\ & \underline{{\text{Sig}}_i^{\tau }():}\\ & \text{wait}\_(i,1)\forall j\in \mathcal{P}.\exists i.{\text{ready}}^{\tau }\_ji\\ & m\leftarrow {\text{GetMessage}}^{\tau }()\\ & R\leftarrow \frac{1}{k^{\tau }}\cdot G\\ & s\leftarrow k\cdot (\text{Hash}(m)+x(R)\cdot x)\\ & \text{return }(R,s)\\ & \\ & \underline{{\text{Leak}}^{\tau }():}\\ & \text{return }(x\cdot G,x{k}^{\tau }\cdot G,k^{\tau }\cdot G,\frac{1}{k^{\tau }}\cdot G)\end{array}}\\ ⊚\\ F[\text{Messages}]\\ \otimes \\ F[\text{Sync}{]}^{\mathbb{N}}\\ ⊚\\ F[\text{Stop}]\end{array}\\ \\ \text{Leakage}:=\{\text{stop},{\text{SetMessage}}^{\tau },{\text{GetMessage}}^{\tau },{\text{Leak}}^{\tau }\}\end{array}}⊲\mathcal{P}[\text{Presign}]$$

The ideal functionality unfortunately has to reflect the round timing of the protocol itself.

Lemma:

For a negligible $ϵ$, and up to $t-1$ malicious corruptions, we have:

$$\mathcal{P}[\text{Sign}]\stackrel{ϵ}{⇝}\mathcal{P}[\text{IdealSign}]$$

Proof:

First, we can replace $\mathcal{P}[\text{Presign}]$ with $\mathcal{P}[\text{IdealPresign}]$.

From there, we can use a similar simulator as last time:

$$\begin{array}{c}\boxed{\begin{array}{rl}& {\Gamma }_H^0\\ & \dots \end{array}}\otimes \boxed{\begin{array}{rl}& S\\ & x_i,k^{\tau }\_i,{\sigma }^{\tau }\_i\stackrel{\$}{\leftarrow }{\mathbb{F}}_q(i\in \mathcal{M})\\ & k^{\tau }\_i,{\sigma }^{\tau }\_i\leftarrow \perp (i\in \mathcal{H})\\ & s\_ij\leftarrow \perp \\ & (X,{\text{XK}}^{\tau },K^{\tau },R^{\tau })\leftarrow {\text{Leak}}^{\tau }()\\ & \\ & \underline{{\text{Presign}}_k^{\tau }():}\\ & {\text{Ready}}_k^{\tau }(\mathcal{M})\\ & \text{return }(X,x_i,K^{\tau },R^{\tau },k_k^{\tau },{\sigma }_k^{\tau })\\ & \\ & \underline{{\text{K}}^{\tau }():}\\ & \text{return }{K}^{\tau }\\ & \\ & \\ & \underline{{\text{XK}}^{\tau }():}\\ & \text{return }{\text{XK}}^{\tau }\\ & \\ & \underline{{\Lsh }_k^{\tau }(S,m\_\bullet ,1):}\\ & \text{wait}\_(k,1)\forall j\in S\cap \mathcal{M}.s\_jk\ne \perp \\ & r\_\bullet \leftarrow \perp \\ & r_j\leftarrow s\_jk(j\in S\cap \mathcal{M})\\ & {\text{WaitReady}}_k^{\tau }(S\cap \mathcal{H})\\ & \text{for }j\in S\cap \mathcal{H}:\\ & m\leftarrow {\text{GetMessage}}^{\tau }()\\ & \text{if }|\{i\in \mathcal{H}\mid k_i^{\tau }=\perp \}|=1:\\ & k_j^{\tau }\stackrel{\$}{\leftarrow }{\mathbb{F}}_q\\ & s\leftarrow {\text{Sig}}_k^{\tau }()\\ & {\sigma }_j^{\tau }\leftarrow \frac{1}{x(R)}\cdot \left(s-\text{Hash}(m)\cdot \sum _i{k}_i^{\tau }-x(R)\cdot \sum \_i\ne j{\sigma }_j^{\tau }\right)\\ & \text{else}:\\ & k_j^{\tau },{\sigma }_j^{\tau }\stackrel{\$}{\leftarrow }{\mathbb{F}}_q\\ & r_j\leftarrow \text{Hash}(m)\cdot k_j^{\tau }+x(R)\cdot {\sigma }_j^{\tau }\\ & \text{return }r\_\bullet \\ & \\ & \underline{{\Rsh }_k^{\tau }(S,m\_\bullet ,1):}\\ & {\text{Ready}}_k^{\tau }(S)\\ & \text{for }j\in S.s\_kj=\perp :s\_kj\leftarrow m_j\\ & \text{for }j\in \mathcal{H}.\forall k\in \mathcal{M}.s\_kj\ne \perp :\\ & \text{if }\sum \_k\in \mathcal{M}s\_kj\ne \text{Hash}(m^{\tau })\cdot \sum _k{k}_k^{\tau }+x(R^{\tau })\cdot \sum _k{\sigma }_k^{\tau }:\\ & \text{stop}(\{j\},1)\\ & \dots \end{array}}\\ \circ \\ F[\text{Messages}]⊚F[\text{Stop}]\end{array}$$

The strategy is the same as other simulators in this section, where we use the fact that only the sum has to verify correctly, in order to give junk values up until the last moment.

$■$

The security of using presignatures

Here, we’ve limited ourselves to showing that our protocol implements “ECDSA with presignatures”, as far as the security of “ECDSA with presignatures” as a threshold signature scheme, see Groth & Shoup 2021.