## 4 A Construction Based on the Discrete-Logarithm Problem  
In this section, we propose an OM-UEA scheme for \(\ell\)-sessions whose security relies on the hardness of the discrete-logarithm problem. We refer to the proposed construction as the _Discrete-Logarithm Problem-based Entity Authentication Construction (DLP-EAC)_. **The Discrete-Logarithm Problem -based Entity Authentication Construction (DLP-EAC)**. Let \(p\) and \(q\) be two large primes such that \(q\) divides \(p-1\); let \(G\) be a subgroup of \(Z_{p}^{*}\) having order \(q\), and let \(g\) be a generator of \(G\). We build an OM-UEA scheme \(\Pi=(Gen,Auth,Ver)\) as follows:  
* The parameter-generation algorithm \(Gen\), on inputs the security parameter \(1^{\tau}\) and the maximum number of sessions \(\ell\), outputs the tuple \((pub,priv,s_{0})\) constructed as follows:
* Uniformly chooses at random \(r_{i}\in Z_{q}\), for each \(i=1,\ldots,\ell\);
* Computes \(h_{i}=g^{r_{i}}\bmod p\), for each \(i=1,\ldots,\ell\);
* Sets \(pub\) to the tuple \((h_{1},h_{2},\ldots,h_{\ell})\);
* Sets \(priv\) to the tuple \((r_{1},\ldots,r_{\ell})\);
* Sets the initial state \(s_{0}\) to be empty. * The authentication message-generation \(Auth\), on inputs a session counter \(1\leq i\leq\ell\), the public information \(pub\), the secret key \(priv\) held by the prover, and the previous state \(s_{i-1}\), outputs the authentication message \(a_{i}=r_{i}\) and an empty state \(s_{i}\). * The verification algorithm \(Ver\), on inputs a session counter \(i\) (where \(1\leq i\leq\ell\)), an authentication message \(a_{i}\), public information \(pub\), and the sequence of authentication messages \(hist_{i-1}\), which was generated by the previous \(i-1\) authentication sessions, where \(hist_{0}\) is the empty sequence, extracts the value \(h_{i}\) from \(pub\) and checks whether \(h_{i}=g^{a_{i}}\bmod p\). A pictorial representation of the DLP-EAC is shown in Figure 2.  
In the following, we prove that the DLP-EAC resists active static attacks. Theorem 4.1: _Assuming the hardness of the discrete-logarithm problem, the OM-UEA scheme \(\Pi\) produced by the DLP-EAC is secure in the sense of \(\ell\)-IMP-A-ST._  
Proof: Let us suppose, for the sake of contradiction, that the OM-UEA scheme \(\Pi=(Gen,Auth,Ver)\) produced by DLP-EAC is not secure in the sense of \(\ell\)-IMP-A-ST. There  
Figure 2: A Pictorial Representation of the DLP-EAC. fore, there exists a polynomial time adversary \(\texttt{ACT-STAT}=(\texttt{ACT-STAT}_{1},\texttt{ACT-STAT}_{2})\) whose advantage \(\textbf{Adv}_{\texttt{ACT-STAT},\Pi}^{\textbf{Imp}}(1^{\texttt{T}})\) in the experiment \(\textbf{Imp}_{\texttt{ACT-STAT},\Pi}(1^{\texttt{T}})\) is non-negligible. We will prove that there exists a polynomial time adversary \(A\) that takes as input the tuple \((G,q,g,h)\), where \(h\) is an element which has been uniformly chosen at random in \(G\), and uses the adversary ACT-STAT to obtain a value \(x\in Z_{q}\) such that \(g^{x}\bmod p=h\). The adversary \(A\) runs ACT-STAT\({}_{1}\), which, taking as inputs the security parameter \(1^{\texttt{T}}\) and the maximum number of sessions \(\ell\), outputs the indexes \(i\) and \(j\) such that \(1\leq j<i\leq\ell\). Afterwards, \(A\) first chooses at random a value \(r_{t}\in Z_{q}\) for each \(t=1,\ldots,i-1\) and each \(t=i+1,\ldots,\ell\) and then sets \(pub\) to be equal to the tuple \((h_{1},\ldots,h_{\ell})=(g^{r_{1}}\bmod p,\ldots,g^{r_{i-1}}\bmod p,h,g^{r_{i +1}}\bmod p,\ldots,g^{r_{\ell}}\bmod p)\) and \(hist_{i-1}\) to be equal to the tuple \((r_{1},\ldots,r_{i-1})\). On inputting \(1^{\texttt{T}}\), \(pub\), \(i\), \(j\), and \(hist_{i-1}\), ACT-STAT\({}_{2}\) eventually outputs the tuple \((a^{\prime}_{j},\ldots,a^{\prime}_{i})\) of forgeries and the adversary \(A\) outputs \(a^{\prime}_{i}\). Since ACT-STAT is able to break the OM-UEA scheme generated by the DLP-EAC, then \(Ver(1^{\texttt{T}},i,a^{\prime}_{i},pub,hist_{i-1})=1\).