# HORSIC+: An Efficient Post-Quantum Few-Time Signature Scheme
## 4 Analysis
### Comparison with HORS and Horst
#### 4.3.1 Security Parameters for HORSIC+  
In this sub-subsection, we choose security parameters for HORSIC+ having the same security levels as HORS/HORST. Figure 2 shows the security level of HORSIC+ for various choices of \(k\) and HORS/HORST for signing a single message. In this case, we set \(z=w+k-1\) for HORSIC+. The X-axis represents the parameter \(w\), which affects the computational cost. The Y-axis corresponds to the security level.  
The parameters for HORS/HORST in Figure 2 are chosen from (a) HORS [14] and (b) HORST as used in SPHINCS [13]. The original HORS scheme recommends to use SHA-1 [30] or RIPEMD-160 [31] as a cryptographic hash function \(H\) which has an output length of 160 bits [14]. Thus, the original HORS scheme uses \(t=2^{10}\) and \(k=16\) (\(10\times 16=160\)). The parameters for SPHINCS-256 (\(t=2^{16}\), \(k=32\)) are selected to provide long-term \(2^{128}\) security against attackers with access to quantum computers.  
The security level of HORS/HORST can be obtained from the following equation [14,32]:  
\[k(\log_{2}t-\log_{2}k). \tag{35}\]  
When using the parameters in Figure 2a,b, the security levels of \(\text{HORS}/\text{HORST}\) are 96 and 352, respectively.  
\[\begin{split} 16(\log_{2}2^{10}-\log_{2}16)&=16(10-4)=96. \\ 32(\log_{2}2^{16}-\log_{2}32)&=32(16-5)=352.\end{split} \tag{36}\]  
In Figure 2, 'HORSIC+ 1 st' refers to the first argument of the min function in Equation (34) (i.e., \(\log_{2}(\frac{t^{k}(z-1)!}{k(t-1)!(z-k)!})\)). 'HORSIC+ 2 nd' refers to the second argument of the min function in Equation (34) (i.e., \(n-\log_{2}(w^{2}t+w)\)). 'HORSIC+ 1 st' corresponds to the case where the adversary succeeds in forging only with already revealed secret values. As the number of signatures using the same HORSIC+ key increases, the number of revealed secret values also increases. Thus, the security level of 'HORSIC+ 1 st' decreases more rapidly than that  
Figure 2: Security level of HORSIC+ for various choices of \(k\) and HORS/HORST for signing a single message. The parameters are chosen from (**a**) HORS and (**b**) HORST as used in SPHINCS.  
of 'HORSIC+ 2 nd'. So it is more appropriate to compare the security level of 'HORSIC+ 1 st' with that of HORSIC+ 2 nd'. So it is more appropriate to compare the security level of 'HORSIC+ 1 st' with that of HORS/HORST.  
To get a security level of 96 bits for HORSIC+, \(w\) should be 3, 6, 13, 28, and 72, when \(k\) is 12, 11, 10, 9, and 8, respectively. See the diamond marker in Figure 2a. To get a security level of 352 bits for HORSIC+, \(w\) should be 2, 5, 10, 17, and 29, when \(k\) is 28, 27, 26, 25, and 24, respectively. See the diamond marker in Figure 2b.  
In HORSIC+, as the parameter \(k\) decreases, the signature size also decreases, but the parameter \(w\) should increase to offer the same security level. Figure 2 shows that increased \(w\) results in increased security level of 'HORSIC+ 1 st'. However, it also results in increased overhead in key generation, signing, and verification. We choose two sets of parameters taking into account the relative importance of speed and signature size. The first is \(n=128\), \(t=2^{10}\), \(k=10\), and \(w=13\), implying \(z=22\) which offers 96-bit security level. The second is \(n=256\), \(t=2^{16}\), \(k=26\), and \(w=10\), implying \(z=35\) which offers 352-bit security level. Based on these two sets of parameters, a comparison of HORSIC+ with HORS/HORST will be presented in Section 4.3.3.