# HORSIC+: An Efficient Post-Quantum Few-Time Signature Scheme
## Appendix A Proof of Theorem 1  
In this appendix, we give the proof of Theorem 1. The proof follows similar lines of the proof of Theorem 1 in [16]. Since each HORSIC+ signature have to reveal \(z\) secret values, forging a signature can be accomplished in two mutually exclusive cases. **Case 1:** The adversary is able to forge a signature to any of the \(k!\) permutations of \((sig_{1},sig_{2},sig_{3},\ldots,sig_{k})\). For example, the adversary can create a valid signature \(\sigma^{\prime}=(ctr^{\prime},sig_{2},sig_{1},sig_{3},\ldots,sig_{k})\) for its own message \(M^{\prime}\) where \(H(M^{\prime}\mid ctr^{\prime})=(h_{2},h_{1},h_{3},\ldots,h_{k})\) and \(C_{k,z}(G(M^{\prime}))=(a_{2},a_{1},a_{3},\ldots,a_{k})\). In this case, the adversary is able to forge a signature by using only already revealed secret values by the signature to the signature query. **Case 2:** The adversary is able to forge a signature that contains at least one secret value which has not been revealed by the signature to the signature query. In this case, we try to guess the position of the revealed secret value and place the preimage challenge \(y_{c}\) there. So we can respond to the signature query and hopefully get a preimage of \(y_{c}\). We also place a second preimage challenge in the same chain to manipulate the randomization elements. We slightly modify the distribution of the public key to manipulate our challenges. It is proved that this does not significantly change the adversary's success probability if \(\mathcal{F}_{n}\) is undetectable [16]. Proof of Theorem 1.: We'll prove by contradiction. Suppose there exists an adversary \(\mathcal{A}\) that can produce existential forgeries for HORSIC+\((1^{u},t,k,z,w)\) by mounting an adaptive chosen message attack in time \(\leq T\) with success probability \(e_{\mathcal{A}}=\text{Succ}_{\text{HORSIC+}(1^{u},t,k,z,w)}^{\text{EU-CMK}}( \mathcal{A})\). Then we can construct an oracle machine \(\mathcal{M}^{\mathcal{A}}\) that either breaks the OW or SPR of \(\mathcal{F}_{n}\) using the adversary \(\mathcal{A}\). Algorithm A1 shows the pseudo-code description of \(\mathcal{M}^{\mathcal{A}}\) and Figure A1 shows its key structure. The oracle machine \(\mathcal{M}^{\mathcal{A}}\) first generates a pair of HORSIC+ keys \((X,Y)\) (Line 1). Then, \(\mathcal{M}^{\mathcal{A}}\) randomly selects the positions to place the OW and the SPR challenges in the key chain. The index of the key chain is \(\alpha\), the positions of the OW and the SPR challenges are \(\beta\) and \(\gamma\), respectively (Line 2, 6). \(\mathcal{M}^{\mathcal{A}}\) places the OW challenge \(y_{c}\) in the position \(\beta\). \(\mathcal{M}^{\mathcal{A}}\) also places the SPR challenge \(x_{c}\) at the input of the \(\gamma\)th evaluation of the chain, replacing \(r_{\gamma}\) (Line 7). The modified public key \(Y^{\prime}\) is computed using the manipulated randomization elements \(\vec{r}^{2}\) (Line 8, Figure A1). Then \(\mathcal{M}^{\mathcal{A}}\) runs \(\mathcal{A}\) on input \(Y^{\prime}\) (Line 9). The adversary \(\mathcal{A}\) can ask to provide the signature on a message \(M\) of the adversary's choice (Line 10). \(\mathcal{M}^{\mathcal{A}}\) knows the secret key values \(x_{i}\) for all \(i\in\{1,2,\ldots,t\}\) except for \(\alpha\), and \(\mathcal{M}^{\mathcal{A}}\) only knows the \(\beta\)th intermediate value for the chain with the index \(\alpha\). Thus, \(\mathcal{M}^{\mathcal{A}}\) can answer the query for the \(j\) where \(i_{j}=\alpha\), only when \(w-a_{j}\geq\beta\) (Line 12). Otherwise, \(\mathcal{M}^{\mathcal{A}}\) returns \"fail\" (Line 13). \(\mathcal{M}^{\mathcal{A}}\) generates signature \(\sigma\) of message \(M\) as described in the signature algorithm (Line 14). If the adversary \(\mathcal{A}\) returns an existential forgery \((M^{\prime},\sigma^{\prime})\) (Line 16), \(\mathcal{M}^{\mathcal{A}}\) first checks whether the forged signature is generated by using only already revealed secret values by the signature to the signature query (Line 18).