# HORSIC+: An Efficient Post-Quantum Few-Time Signature Scheme
## 3 The HORSIC+ Signature Scheme  
In this section, we describe HORSIC+ focusing on the differences with HORSIC. Firstly, HORSIC+ does not apply \(f\) as a plain function to the signature key, but uses a member of a function family. Let \(\mathcal{F}_{n}=\{f_{\kappa}:\{0,1\}^{n}\to\{0,1\}^{n}\mid x\in\mathcal{K}\}\) be a family of functions which is second-preimage resistant, undetectable and one-way. The function key \(x\xleftarrow{\lx@overaccentset{{\text{\large$\xi$}}}{\leftarrow}} \mathcal{K}\) specifies a particular function \(f_{\kappa}\) in the family \(\mathcal{F}_{n}\). The function key \(x\) is chosen at random at key generation time and is the same for all function calls. In addition, HORSIC+ uses the chaining function \(c^{s}(x,\vec{r})\) similar to W-OTS\({}^{+}\)[16]. It enables the strict security proof without the need for the used function family to be collision resistant. \[c^{s}(x,\vec{r})= \begin{cases}x,&\text{if }s=0\\ f_{\kappa}(c^{s-1}(x,\vec{r})\oplus r_{s})&\text{if }1\leq s\leq w\end{cases}  \tag{27}\]  
where bitmasks \(\vec{r}\) is defined as  
\[\vec{r}=(r_{1},r_{2},\ldots,r_{w})\in\{0,1\}^{(w,n)} \tag{28}\]  
We denote \(\vec{r}_{a,b}\) as the substring \((r_{a},\ldots,r_{b})\) of \(\vec{r}\). We also define \(\vec{r}_{a,b}\) to be the empty string when \(a>b\). Let \(H:\{0,1\}^{*}\to\{0,1\}^{k\log_{2}t}\) and \(G:\{0,1\}^{*}\to\left[0,{{z-1}\choose{k-1}}\right)\) be cryptographic hash functions in the random oracle model. HORSIC+ uses a bijective function \(\mathrm{C}_{k,z}\) same as HORSIC. Algorithm 4 describes the implementation of the function \(\mathrm{C}_{k,z}(g)\). It is based on the following equation:  
\[{{z-1}\choose{k-1}}={{z-2}\choose{k-2}}+{{z-3}\choose{k-2}}+\ldots+{{k-2} \choose{k-2}}=\sum_{j=1}^{z-k+1}{{z-1-j}\choose{k-2}} \tag{29}\]  
In Equation (29), \({{z-2}\choose{k-2}}\), \({{z-3}\choose{k-2}}\) and \({{k-2}\choose{k-2}}\) are the number of solutions when \(a_{1}\) is 1, 2 and \(z-k+1\), respectively. First, Algorithm 4 checks whether \(g<{{z-2}\choose{k-2}}\). If so, \(a_{1}=1\) and \(z-1=\sum_{i=2}^{k}a_{i}\). If not, Algorithm 4 checks whether \(g<{{z-2}\choose{k-2}}+{{z-3}\choose{k-2}}\). If so, \(a_{1}=2\) and \(z-2=\sum_{i=2}^{k}a_{i}\), and so on. ```
System Parameters: Parameters \(k\) and \(z\) where \(k\leq z\) Input:\(g\) where \(0\leq g<{{z-1}\choose{k-1}}\) Output:\((a_{1},a_{2},\ldots,a_{k})\)
1:\(s=0\), \(r=k\)
2:for\(i=1\) to \(k-2\)do
3:for\(j=1\) to \(z-r+1\)do
4:if\(g<s+{{z-1-j}\choose{r-2}}\)then
5:\(a_{i}=j\), \(r=r-1\), \(z=z-j\)
6: break
7:\(s=s+{{z-1-j}\choose{r-2}}\)
8:\(a_{k-1}=g-s+1\), \(a_{k}=z-a_{k-1}\)
```
**Algorithm 4** Implementation of the function \(\mathrm{C}_{k,z}(g)\)  
Algorithm 5 represents the key generation of HORSIC+. It first chooses \(t\) and \(w\)\(n\)-bit strings uniformly at random. The first \(t\) bit strings are used as the signature key and the remaining \(w\) bit strings are used as the bitmasks \(\vec{r}=(r_{1},r_{2},\ldots,r_{w})\). Then it also chooses a function key \(x\xleftarrow{\lx@overaccentset{{\text{\large$\xi$}}}{\leftarrow}} \mathcal{K}\). The function key \(x\) specifies a particular function \(f_{\kappa}\) in the family \(\mathcal{F}_{n}\). It is important to note that the verification key \(Y\) includes \((\kappa,\vec{r})\) and thus known to everybody. ```
System Parameters: Parameters \(n\), \(t\), \(k\), \(z\), and \(w\) Output: Signature key \(X\) and verification key \(Y\)
1: Choose \(X=(x_{1},x_{2},\ldots,x_{t})\xleftarrow{\xi}\{0,1\}^{(t,n)}\)
2: Choose \(\vec{r}=(r_{1},r_{2},\ldots,r_{w})\xleftarrow{\xi}\{0,1\}^{(w,n)}\)
3: Choose \(\kappa\xleftarrow{\xi}\mathcal{K}\)
4: Compute \(Y=(y_{0},y_{1},y_{2},\ldots,y_{t})=((\kappa,\vec{r}),c^{w}(x_{1},\vec{r}),c^{ w}(x_{2},\vec{r}),\ldots,c^{w}(x_{t},\vec{r}))\)
5:return\((X,Y)\)
```
**Algorithm 5**Key generation of HORSIC+ (\(K_{B\text{HORSIC}+}()\))  
Figure 1 and Algorithm 6 represent the signing of HORSIC+. HORSIC+ uses a bijective function \(\mathbb{C}_{k,z}\) and two cryptographic hash functions \(H\) and \(G\).