## 2 Preliminaries
### Digital Signatures
A passive adversary is only allowed to passively observe different executions of the scheme and to collect authentication messages generated by the prover, whereas an active one can also modify some authentication messages before they reach their destination. Moreover, they considered both static and adaptive adversaries. Informally, a static adversary randomly chooses the session to be attacked, whereas the adaptive one uses the information it progressively learns to makes its choice. For both passive and active attacks, [PERSON] et al. [1] examined the relationships between security definitions that arise from adaptive and static adversarial behaviors. In particular, they showed the equivalence between security against static adversaries and security against adaptive ones. On the other hand, they also proved that security against active static attacks implies security against passive static attacks, while the opposite does not hold. Thus, from now on, we will only consider active static adversaries. In the following, we recall the definition of such a kind of adversary. An active static adversary works in two phases, so it is denoted by \(\texttt{ACT-STAT}=(\texttt{ACT-STAT}_{1},\texttt{ACT-STAT}_{2})\). In the first phase \(\texttt{ACT-STAT}_{1}\), on inputs the security parameter \(1^{\tau}\) and the maximum number of sessions \(\ell\), it chooses a pair of session counters \((i,j)\) between \(1\) and \(t\), where \(t=t(\tau)\) is the polynomial corresponding to the running time of the adversary, such that \(j\leq i\). This models the fact that \(\texttt{ACT-STAT}\) has chosen to attack the \(i\)-th authentication session and to modify the last \(i-j\) authentication messages (clearly, if \(j=i\), the sequence of modified messages is empty). Notice that such a choice occurs before the algorithm \(Gen\) is run. For each \(1\leq i\leq\ell\), we define an algorithm \(Auth_{i-1}\) which, given the security parameter \(1^{\tau}\), the public information \(pub\), the private information \(priv\), and the sequence \(states_{i-1}=(s_{0},\ldots,s_{i-2})\) of the first \(i-1\) states, outputs the sequence \(hist_{i-1}=(a_{1},\ldots,a_{i-1})\) by running \(Auth(1^{\tau},j,pub,priv,s_{j-1})\) for \(j=1,\ldots,i-1\), where \(hist_{0}\) corresponds to the empty sequence. In the second phase, \(\texttt{ACT-STAT}_{2}\) is able to obtain the sequence \(hist_{i-1}=(a_{1},\ldots,a_{i-1})\) of authentication messages generated for the first \(i-1\) sessions. Afterwards, \(\texttt{ACT-STAT}_{2}\), on inputs \(1^{\tau}\), the public information \(pub\), the pair of session counters \((i,j)\), and the sequence \(hist_{i-1}\), outputs a sequence of _fake authentication messages_\((a^{\prime}_{j},\ldots,a^{\prime}_{i-1},a^{\prime}_{i})\) and succeeds if the verifier accepts all of them. In particular, \(a^{\prime}_{j},a^{\prime}_{j+1},\ldots,a^{\prime}_{i-1}\) will replace the authentication messages \(a_{j},a_{j+1},\ldots,a_{i-1}\), which are the last \(i-j\) elements of the sequence \(hist_{i-1}\); such a modified sequence \((a_{1},\ldots,a_{j-1},a^{\prime}_{j},\ldots a^{\prime}_{i-1})\) is denoted by \(hist^{\prime}_{h-1}\), for any \(h=j,\ldots,i\). The above security requirement is formalized in the next definition. **Definition 5** ([1] [\(\ell\)-Imp-A-St]). : _Let \(\Pi\) be an OM-UEA scheme. The active static impersonation experiment for an active static adversary \(\texttt{ACT-STAT}=(\texttt{ACT-STAT}_{1},\texttt{ACT-STAT}_{2})\) is as follows:_