## 3 A Construction Based on Digital Signatures  
In this section, we consider the problem of constructing an OM-UEA scheme by using a different primitive, compared to the constructions in [1]. We propose a construction, resulting in an OM-UEA for \(\ell\) sessions, which uses as a building block a digital signature scheme. We refer to the proposed construction as the Digital Signature-based Entity Authentication Construction (DS-EAC). **The Digital Signature-based Entity Authentication Construction (DS-EAC)**. Let \(\Sigma=(KGen,Sign,Vrfy)\) be a digital signature scheme and let \(\ell=\ell(\tau)\), where \(\ell(\cdot)\) is a polynomially-bounded function. We construct a one-message unilateral entity authentication scheme, \(\Pi=(Gen,Auth,Ver)\), for \(\ell\) sessions as follows:  
* The parameter-generation algorithm \(Gen\), on inputs a security parameter \(1^{\mathtt{T}}\) and the number of sessions \(\ell\), outputs the tuple \((pub,priv,s_{0})\) constructed as follows:
* Runs the key-generation algorithm \(KGen(1^{\mathtt{T}})\) to obtain the pair \((pub,priv)\);
* Sets \(pub=pk\) and \(priv=sk\);
* Sets the initial state \(s_{0}\) to be empty. * The authentication message-generation \(Auth\), on inputs a security parameter \(1^{\mathtt{T}}\), a session counter \(1\leq i\leq\ell\), the public value \(pub\), the secret key \(priv\) for the prover, and the previous state \(s_{i-1}\), outputs the authentication message \(a_{i}\) and the state \(s_{i}\), as follows:
* Runs the signing algorithm \(Sign\), on inputs the private key \(sk\) and the message \(i\), in order to produce the signature \(\sigma_{i}=Sign(sk,i)\);
* Sets \(a_{i}\) to the pair \((i,\sigma_{i})\);
* Outputs \(a_{i}\) and an empty state \(s_{i}\). * The verification algorithm \(Ver\), on inputs a session counter \(i\) such that \(1\leq i\leq\ell\), an authentication message \(a_{i}\), the public value \(pub\), and the sequence of authentications \(hist_{i-1}\) obtained by the first \(i-1\) sessions, where \(hist_{0}\) is the empty sequence, runs the verification algorithm \(Vrfy\) on inputs the public key \(pk\), the session counter \(i\) and the signature \(\sigma_{i}\), and outputs the same output as \(Vrfy(pk,i,\sigma_{i})\). Notice that the DS-EAC construction also supports an arbitrary polynomial number of authentication sessions, i.e., the construction works even in the case where the parameter \(\ell\) is not fixed in advance. A pictorial representation of the DS-EAC is shown in Figure 1.  
We analyze the security of the DS-EAC against active static attacks. In particular, we are interested in establishing which security properties have to be satisfied by the underlying signature scheme in order for the resulting OM-UEA scheme to be secure against attacks carried out by active static adversaries. The next theorem shows that a weak form of unforgeability for the digital signature scheme, i.e., the existential unforgeability against a known-message attack, is sufficient to achieve the desired level of security for the DS-EAC. If \(\Sigma=(KGen,Sign,Vrfy)\) is a digital signature scheme that is existentially unforgeable under known-message attack, then the OM-UEA scheme for \(\ell\) sessions \(\Pi=(Gen,Auth,Ver)\) produced by the DS-EAC is secure in the sense of \(\ell\)-IMP-A-ST.  
Let us suppose, for the sake of contradiction, that the OM-UEA scheme \(\Pi\) produced by the DS-EAC is not secure in the sense of \(\ell\)-IMP-A-ST. Therefore, there exists a polynomial time adversary \(\texttt{ACT-STAT}=(\texttt{ACT-STAT}_{1},\texttt{ACT-STAT}_{2})\) whose advantage \(\mathbf{Adv}^{\mathbf{Imp}}_{\texttt{ACT-STAT},\Pi}(1^{\tau})\) in the experiment \(\mathbf{Imp}_{\texttt{ACT-STAT},\Pi}(1^{\tau})\) is non-negligible. We will show that there exists a polynomial time adversary \(A\) which, on input a public key \(pk\) along with a set \(Q\) of pairs consisting of a message and the corresponding signature, uses the adversary ACT-STAT to forge a valid signature on a message \(m\) which does not belong to \(Q\).