# HORSIC+: An Efficient Post-Quantum Few-Time Signature Scheme
## Appendix A Proof of Theorem 1
If it is, \(\mathcal{M}^{\mathcal{A}}\) returns \"fail\" (Line 19). Then, \(\mathcal{M}^{\mathcal{A}}\) looks for \(j\in\{1,2,\ldots,k\}\) where \(i^{\prime}_{j}=\alpha\). The forgery is only useful if such \(j\) exists and \(w-a^{\prime}_{j}<\beta\) (Line 20). If \(\beta=w\), the forgery contains a preimage of \(y_{c}\). In this case, \(sig^{\prime}_{j}\) is an intermediate value of the chain with the index \(\alpha\) that ends in \(y_{c}\). So \(\mathcal{M}^{\mathcal{A}}\) calculates the preimage and returns it (Line 23). Otherwise, the chain continuing at \(sig^{\prime}_{j}\) either has or does not have \(y_{c}\) as the \(\beta\)th intermediate value. In the first case, we can compute the preimage again (Line 25). In the second case, the chains continued from \(y_{c}\) and \(sig^{\prime}_{j}\) must collide somewhere between \(\beta+1\) and \(w\) according to the pigeonhole principle. If they collide at position \(\gamma\) for the first time, a second preimage for \(x_{c}\) can be calculated (Line 27). Otherwise, \(\mathcal{M}^{\mathcal{A}}\) returns \"fail\" (Line 28). To easily calculate the success probability of \(\mathcal{M}^{\mathcal{A}}\), we only calculate the probability for a certain success case. If there exists \(j\in\{1,2,\ldots,k\}\) such that \(i_{j}=\alpha\) obtained from \(\mathcal{A}\)'s query, we assume \(a_{j}=w-\beta\). If not, we assume \(\beta=w\). Since \(\beta\) is randomly chosen from a uniform distribution, the probability of \(a_{j}=w-\beta\) and \(\beta=w\) are both equal to \(\frac{1}{w}\). Modification of the verification key \(Y\) might lead to changing the input distribution of \(\mathcal{A}\), so we denote the probability that \(\mathcal{A}\) returns a valid forgery in line 16 of the Algorithm A1 as \(e^{\prime}_{\mathcal{A}}\). In case where the forged signature \((M^{\prime},\sigma^{\prime})\) is generated by using only already revealed secret values, the probability that \(\mathcal{A}\) returns a valid forgery is \(\frac{k!(k-1)!(z-k)!}{k^{k}(z-1)!}\)[15]. If not, the forged signature \((M^{\prime},\sigma^{\prime})\) contains at least one secret value which has not been revealed yet. The probability of the newly revealed secret value being in the chain with the index \(\alpha\) is at least \(\frac{1}{t}\). At this point there are two mutually exclusive cases, one of which occurs with probability \(p\) and the other with probability \((1-p)\). **Case 1:** Either \(\beta=w\) or the chain continuing at \(sig^{\prime}_{j}\) has \(y_{c}\) as the \(\beta\)th intermediate value. In this case, \(\mathcal{M}^{\mathcal{A}}\) returns a preimage for \(y_{c}\) with probability \(1\). **Case 2:**\(\beta<w\) and the chain continuing at \(sig^{\prime}_{j}\) does not have \(y_{c}\) as the \(\beta\)th intermediate value. In this case, \(\mathcal{M}^{\mathcal{A}}\) returns a second preimage for \(x_{c}\) if the chains continued from \(y_{c}\) and \(sig^{\prime}_{j}\) collide for the first time at position \(\gamma\). This occurs with a greater probability of \(\frac{1}{w}\) as \(\gamma\) was randomly and uniformly chosen within the interval \([\beta+1,w]\). Using the assumptions about the one-wayness and second preimage resistance of \(\mathcal{F}_{n}\) we can bound the success probability of \(\mathcal{A}\) if called by \(\mathcal{M}^{\mathcal{A}}\):  
\[ \begin{split} e^{\prime}_{\mathcal{A}}&\leq\max\{T \cdot\frac{k!(k-1)!(z-k)!}{t^{k}(z-1)!},\\ wt&\cdot\max\{\text{InSec}^{\text{OW}}(\mathcal{F}_{n };T^{\prime}),w\cdot\text{InSec}^{\text{SPR}}(\mathcal{F}_{n};T^{\prime})\} \}\end{split} \] (A1)  
where the time \(T^{\prime}=T+(t+2k)w\) is an upper bound obtained as the runtime of \(\mathcal{A}\) plus the time needed to run each algorithm of HORSIC+ once; \(K_{\text{\emph{G}HORSIC+}}\), \(Sign_{\text{\emph{HORSIC+}}}\), and \(Vf_{\text{\emph{HORSIC+}}}\) used in \(\mathcal{M}^{\mathcal{A}}\) require at most \(tw\), \(kw\), and \(kw\) calculations of \(f_{k}\), respectively.