# HORSIC+: An Efficient Post-Quantum Few-Time Signature Scheme
## 2 Preliminaries and Related Works
### Preliminaries
The success probability of an adversary against the second preimage resistance of \(\mathcal{F}_{n}\) is  
\[\operatorname{Succ}_{\mathcal{F}_{n}}^{SPR}(\mathcal{A})=Pr[\kappa \overset{\$}{\leftarrow}\mathcal{K};x\overset{\$}{\leftarrow}\{0,1\}^{n};x ^{\prime}\overset{\$}{\leftarrow}\mathcal{A}(\kappa,x):x\
eq x^{\prime}\wedge f _{\kappa}(x)=f_{\kappa}(x^{\prime})]. \tag{6}\]  
Definition 4: We call \(\mathcal{F}_{n}\) second preimage resistant, if the success probability of any adversary \(\mathcal{A}\) running in time \(\leq T\) against the second preimage resistance of \(\mathcal{F}_{n}\) is negligible in \(n\):  
\[\operatorname{InSec}^{\text{SPR}}(\mathcal{F}_{n};T)\overset{def}{=}\max_{ \mathcal{A}}\{\operatorname{Succ}_{\mathcal{F}_{n}}^{\text{SPR}}(\mathcal{A}) \}=negl(n). \tag{7}\]A function is collision resistant if it is hard to find any pair \((x,x^{\prime})\) in the domain that maps to the same value. The success probability of an adversary against the collision resistance of \(\mathcal{F}_{n}\) is  
\[\text{Succ}^{CR}_{\mathcal{F}_{n}}(\mathcal{A})=Pr[\kappa\stackrel{{ \mathcal{S}}}{{\leftarrow}}\mathcal{K};(x,x^{\prime})\stackrel{{ \mathcal{S}}}{{\leftarrow}}\mathcal{A}(\kappa):x\
eq x^{\prime}\wedge f_{ \kappa}(x)=f_{\kappa}(x^{\prime})]. \tag{8}\]  
**Definition 5**. : _We call \(\mathcal{F}_{n}\) collision resistant, if the success probability of any adversary \(\mathcal{A}\) running in time \(\leq T\) against the collision resistance of \(\mathcal{F}_{n}\) is negligible in \(n\):_  
\[\text{InSec}^{\text{CR}}(\mathcal{F}_{n};T)\stackrel{{ def}}{{=}}\max_{\mathcal{A}}\{\text{Succ}^{\text{CR}}_{\mathcal{F}_{n}}( \mathcal{A})\}=negl(n). \tag{9}\]  
To define the undetectability property, we need to define the (distinguishing) advantage of an adversary. **Definition 6**. : _Let \(\mathcal{X}\) and \(\mathcal{Y}\) be two distributions. The advantage \(\text{Adv}_{\mathcal{X},\mathcal{Y}}(\mathcal{A})\) of an adversary \(\mathcal{A}\) in distinguishing between these two distributions is defined as_  
\[\text{Adv}_{\mathcal{X},\mathcal{Y}}(\mathcal{A})=|\Pr[1\leftarrow\mathcal{A} (\mathcal{X})]-\Pr[1\leftarrow\mathcal{A}(\mathcal{Y})]~{}|~{}. \tag{10}\]  
A function family is undetectable if no adversary can distinguish its outputs from uniformly random values. Consider two distributions \(\mathcal{D}_{\text{UD},\mathcal{U}}\) and \(\mathcal{D}_{\text{UD},\mathcal{F}_{n}}\) over \(\{0,1\}^{n}\times\mathcal{K}\). A sample \((u,\kappa)\) from the first distribution \(\mathcal{D}_{\text{UD},\mathcal{U}}\) is obtained in the following way: \(u\stackrel{{\mathcal{S}}}{{\leftarrow}}\{0,1\}^{n}\), \(\kappa\stackrel{{\mathcal{S}}}{{\leftarrow}}\mathcal{K}\). A sample \((u,\kappa)\) from the second distribution \(\mathcal{D}_{\text{UD},\mathcal{F}_{n}}\) is obtained in the following way: \(x\stackrel{{\mathcal{S}}}{{\leftarrow}}\{0,1\}^{n}\), \(\kappa\stackrel{{\mathcal{S}}}{{\leftarrow}}\mathcal{K}\), and then calculating \(u=f_{\kappa}(x)\). The advantage of an adversary against the undetectability of \(\mathcal{F}_{n}\) is defined as the distinguishing advantage for these two distributions:  
\[\operatorname{InSec}^{\text{EU-CMA}}(\operatorname{Dss}(1^{n});T,q)\overset{def }{=}\max_{\mathcal{A}}\{\operatorname{Succ}_{\mathbf{Dss}(1^{n})}^{\text{EU-CMA} }(\mathcal{A})\}=negl(n). \tag{2}\]0  
**Definition 7**. : _We call \(\mathcal{F}_{n}\) undetectable, if the advantage of any adversary \(\mathcal{A}\) running in time \(\leq T\) against the undetectability of \(\mathcal{F}_{n}\) is negligible in \(n\):_  
\[\operatorname{InSec}^{\text{EU-CMA}}(\operatorname{Dss}(1^{n});T,q)\overset{def }{=}\max_{\mathcal{A}}\{\operatorname{Succ}_{\mathbf{Dss}(1^{n})}^{\text{EU-CMA} }(\mathcal{A})\}=negl(n). \tag{2}\]1  
Table 1 summarizes the best known generic attacks against different functions given different environments [20]. Using generic(brute-force) classical attacks, one requires \(\Theta(2^{n})\) evaluations of the function to compute preimages or second preimages.