# HORSIC+: An Efficient Post-Quantum Few-Time Signature Scheme
## 2 Preliminaries and Related Works
### Preliminaries  
We start this subsection with several definitions and notions related to digital signature schemes and function families [16,18,19]. From now on, we write \(x\xleftarrow{\xi}S\) if \(x\) is chosen randomly from the finite set \(S\) using a uniform distribution. Definition 1: Let \(\mathcal{M}\) be a message space. A digital signature scheme \(\mathbf{Dss}=(\mathbf{Kg},\mathbf{Sign},\mathbf{Vf})\) is a triple of probabilistic polynomial time algorithms:  
* \(\mathbf{Kg}(\mathbb{1}^{n})\) takes as input a security parameter \(\mathbb{1}^{n}\) and outputs a signature key \(X\) and a verification key \(Y\);
* \(\mathbf{Sign}(X,M)\) outputs a signature \(\sigma\) under the signature key \(X\) for message \(M\in\mathcal{M}\);
* \(\mathbf{Vf}(Y,M,\sigma)\) outputs \(1\) iff \(\sigma\) is a valid signature on \(M\) under the verification key \(Y\);_such that \(\forall(X,Y)\leftarrow\mathbf{Kg}(1^{n}),\forall(M\in\mathcal{M}):\mathbf{Vf}(Y,M,\mathbf{Sign}( X,M))=1\)._  
Let \(\mathbf{Dss}(1^{n})\) be a digital signature scheme with security parameter \(n\). The standard definition of security for digital signature schemes is existential unforgeability under adaptive chosen message attack (EU-CMA). EU-CMA is defined using the following experiment. \(\text{\bf Experiment}\operatorname{Exp}_{\mathbf{Dss}(1^{n})}^{\text{EU-CMA}}( \mathcal{A})\)  
\((X,Y)\leftarrow\mathbf{Kg}(1^{n})\)  
\((M^{\prime},\sigma^{\prime})\leftarrow\mathcal{A}^{\mathbf{Sign}(X,\cdot)}(Y)\)  
Let \(\{(M_{i},\sigma_{i})\}_{1}^{q}\) be the query-answer pairs of \(\mathbf{Sign}(X,\cdot)\). Return 1 iff \(\mathbf{Vf}(Y,M^{\prime},\sigma^{\prime})=1\) and \(M^{\prime}\
otin\{M_{i}\}_{1}^{q}\). The success probability of an adversary \(\mathcal{A}\) in the above experiment can be written by:  
\[\operatorname{Succ}_{\mathbf{Dss}(1^{n})}^{\text{EU-CMA}}(\mathcal{A})=\Pr[ \operatorname{Exp}_{\mathbf{Dss}(1^{n})}^{\text{EU-CMA}}(\mathcal{A})=1]. \tag{1}\]  
Definition 2: Let \(n,T,q\in\mathbb{N}\) and \(T,q=poly(n)\). A digital signature scheme \(\mathbf{Dss}(1^{n})\) is EU-CMA secure if the success probability of any adversary \(\mathcal{A}\) running in time \(\leq T\) and making at most \(q\) queries to the oracle \(\mathbf{Sign}\) in the above experiment 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}\]  
We then discuss several security properties for function families: preimage resistance (one-wayness, OW), second preimage resistance (SPR), collision resistance (CR), and undetectability (UD). Let \(n\in\mathbb{N}\) be the security parameter and  
\[\mathcal{F}_{n}=\{f_{\kappa}:\{0,1\}^{n}\rightarrow\{0,1\}^{n}\mid\kappa\in \mathcal{K}\} \tag{3}\]  
be a family of functions. The elements of \(\mathcal{K}\) are called keys and each key \(\kappa\) specifies a particular function \(f_{\kappa}\) in the family \(\mathcal{F}_{n}\). A function is preimage resistant (or one-way) if it is easy to compute but difficult to invert. The success probability of an adversary against the preimage resistance of \(\mathcal{F}_{n}\) is  
\[\operatorname{Succ}_{\mathcal{F}_{n}}^{\text{OW}}(\mathcal{A})=Pr[\kappa \overset{\$}{\leftarrow}\mathcal{K};x\overset{\$}{\leftarrow}\{0,1\}^{n},y \gets f_{\kappa}(x);x^{\prime}\overset{\$}{\leftarrow}\mathcal{A}(\kappa, y):y=f_{\kappa}(x^{\prime})]. \tag{4}\]  
Definition 3: We call \(\mathcal{F}_{n}\) preimage resistant (or one-way), if the success probability of any adversary \(\mathcal{A}\) running in time \(\leq T\) against the preimage resistance of \(\mathcal{F}_{n}\) is negligible in \(n\):  
\[\operatorname{InSec}^{\text{OW}}(\mathcal{F}_{n};T)\overset{def}{=}\max_{ \mathcal{A}}\{\operatorname{Succ}_{\mathcal{F}_{n}}^{\text{OW}}(\mathcal{A}) \}=negl(n). \tag{5}\]  
A function is second preimage resistant if, given some \(x\) in the domain, it is difficult to find some \(x^{\prime}\) unequal to \(x\) that maps the same value.