# HORSIC+: An Efficient Post-Quantum Few-Time Signature Scheme
## 2 Preliminaries and Related Works
### Horsic  
HORSIC [15] is basically an extension of HORS [14]. Whereas HORS uses only a cryptographic hash function \(H\), making it infeasible to find two different messages that will produce the same \(k\)-element subset, HORSIC decreases the probability of forgery by using another cryptographic hash function \(G\) and a bijective function \(\text{C}_{k,z}\) as well as \(H\) to make it infeasible to find two different messages that will produce the same \(k\)-part integer composition as well as the same \(k\)-element subset. Let \(f:\{0,1\}^{n}\to\{0,1\}^{n}\) be a one-way permutation operating on \(n\)-bit strings. Let \(H:\{0,1\}^{*}\to\{0,1\}^{k\log_{2}t}\) and \(G:\{0,1\}^{*}\to\{0,(\hat{z}-1)\choose k-1}\) be cryptographic hash functions in the random oracle model [26]. \(t\), \(k\), and \(z\) are security parameters. The public key size is linear in \(t\), and the signature size is linear in \(k\). HORSIC uses a bijective function \(\text{C}_{k,z}\) that, on input \(g\), where \(0\leq g<(\hat{z}-1)\), outputs the \(g\)-th solution of the following equation:  
\[z=\sum_{i=1}^{k}a_{i},a_{i}\text{ is an integer such that }a_{i}\geq 1. \tag{26}\]  
Note that the number of solutions to the above equation, which is the number of compositions of \(z\) into exactly \(k\) parts, is denoted by the binomial coefficient \((\hat{z}-1)\)[27]. For example, suppose \(k=3\) and \(z=5\). The equation \(a_{1}+a_{2}+a_{3}=5\) has 6 solutions \((\hat{z}-1)=(\hat{z}-1)=(\hat{z}-1)=(\hat{z})=(\hat{z}):\text{C}_{3,5}(0)=(1,1,3)\), \(\text{C}_{3,5}(1)=(1,2,2)\), \(\text{C}_{3,5}(2)=(1,3,1)\), \(\text{C}_{3,5}(3)=(2,1,2)\), \(\text{C}_{3,5}(4)=(2,2,1)\), and \(\text{C}_{3,5}(5)=(3,1,1)\). Algorithm 1 represents the key generation of HORSIC. If first generates \(t\) random \(n\)-bit numbers and then creates a one-way chain of length \(w\) for each \(n\)-bit number. ```
**Algorithm 1**Key generation of HORSIC (\(Kg_{HORSIC}()\))

Algorithm 2 represents the signing of HORSIC. HORSIC uses a bijective function \(C_{k,z}\) and two cryptographic hash functions \(H\) and \(G\). A cryptographic hash function \(H\) is used to map each message \(M\) to a \(k\)-element ordered subset \((i_{1},i_{2},\ldots,i_{k})\) of a \(t\)-element set \(\{1,2,\ldots,t\}\). A counter \(ctr\) is used to ensure that all \(i_{j}\) are distinct. A cryptographic hash function \(G\) and a bijective function \(C_{k,z}\) are used to map each message \(M\) to a \(k\)-part integer composition \((a_{1},a_{2},\ldots,a_{k})\) of \(z\). ```  
```
```
```

```
1:Signature key \(X\) and message \(M\)
```
1:Compute \(g=G(M)\)
2:Compute \((a_{1},a_{2},\ldots,a_{k})=C_{k,z}(g)\)
3:Set \(ctr=0\)
4:Compute \(h=H(M\mid ctr)\)
5:Split \(h\) into \(k\) pieces \((h_{1},h_{2},\ldots,h_{k})\) of length \(\log_{2}t\) bits each
6:Interpret each \(h_{j}\) as an integer \(i_{j}\) for all \(j\in\{1,2,\ldots,k\}\)
7:if there exist \(p\) and \(q\) with \(p,q\in\{1,2,\ldots,k\}\) such that \(i_{p}=i_{q}\) and \(p\
eq q\)then
8:\(ctr=ctr+1\) and go to Step 4
9:Compute \(sig_{j}=f^{w-i_{j}}(x_{i_{j}})\) for all \(j\in\{1,2,\ldots,k\}\)
10:return\(\sigma=(ctr,sig_{1},sig_{2},\ldots,sig_{k})\) ```
```  
**Algorithm 2**Signing of HORSIC (\(Sign_{HORSIC}(X,M)\))  
Algorithm 3 represents the verification of HORSIC. Each \(sig_{j}\) is verified by applying the one-way permutation \(a_{j}\) times and comparing it with the verification key.