## 2 Preliminaries
### Digital Signatures  
Digital signatures are a fundamental tool in different protocols designed to work in a distributed environment, since they provide message authentication and integrity. We start by recalling the definition of digital signature schemes. Definition 2: A triple \(\Sigma=(KGen,Sign,Vrfy)\) of polynomial time algorithms is a digital signature scheme if:  
* The probabilistic key-generation algorithm \(KGen\), given a security parameter \(1^{\tau}\), produces as outputs a public key \(pk\) and a secret key \(sk\). * The probabilistic signing algorithm \(Sign\), given the private key \(sk\) and a message \(m\in\{0,1\}^{*}\), produces as output a signature \(\sigma\). * The deterministic verification algorithm \(Vrfy\), given the public key \(pk\), a message \(m\), and a signature \(\sigma\), outputs a bit \(b\), where \(b=1\) means that the signature is valid, whereas \(b=0\) means that the signature is invalid. It is required that, for every pair \((pk,sk)\) which can be output by \(KGen(1^{\tau})\), every message \(m\in\{0,1\}^{*}\), and every \(\sigma\) which can be output by \(Sign(sk,m)\), it holds that \(Vrfy(pk,m,\sigma)=1\). Given the public key \(pk\) of a signer \(S\), a _forgery_ is a pair \((m,\sigma)\), where \(\sigma\) is a valid signature for \(m\) and \(m\) has not been previously signed by \(S\). We are interested in signature schemes where an adversary should be unable to forge a signature for any message \(m\) even if it is given access to signatures for a set of other messages not of his choice. In particular, for our goals it is sufficient to consider a weak notion of security known as _existential unforgeability under known message attack_[25]. We formalize such a goal in the next definition. Definition 3: Let \(\Sigma=(KGen,Sign,Vrfy)\) be a digital signature scheme. The signature-forgery experiment for an adversary \(A\) is as follows:  
\[\begin{array}{l}\text{Experiment }\textbf{Sig-Forge}_{A,\Sigma}(1^{\tau})\\ (pk,sk)\gets KGen(1^{\tau})\\ \text{ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  
* _The probabilistic message authentication algorithm_ \(Auth\)_, on inputs the security parameter_ \(1^{\tau}\)_, the current session counter_ \(i\)_, where_ \(1\leq i\leq\ell\)_, the public information_ \(pub\)_, the private information_ \(priv\)_, and the current state_ \(s_{i-1}\)_, outputs the pair_ \((a_{i},s_{i})\)_, where_ \(a_{i}\) _is the authentication message for the_ \(i\)_-th session and_ \(s_{i}\) _is the new state._
* _The deterministic verification algorithm_ \(Ver\)_, on inputs the security parameter_ \(1^{\tau}\)_, the current session counter_ \(i\)_, where_ \(1\leq i\leq\ell\)_, an authentication message_ \(a_{i}\)_, the public information_ \(pub\)_, and the sequence of authentication messages_ \(hist_{i-1}=(a_{1},\ldots,a_{i-1})\) _generated by the previous_ \(i-1\) _authentication sessions, where_ \(hist_{0}\) _corresponds to the empty sequence, outputs a bit_ \(b\)_, where a value of_ \(1\) _indicates a_ valid _authentication and a value of_ \(0\) _indicates an_ invalid _authentication._ _For every triple_ \((pub,priv,s_{0})\) _output by_ \(Gen(1^{\tau},\ell)\) _and every session counter_ \(1\leq i\leq\ell\)_, if we compute_ \((a_{j},s_{j})\) _using the function_ \(Auth(1^{\tau},j,pub,priv,s_{j-1})\) _for each_ \(j=1,\ldots,i\)_, then the function_ \(Ver(1^{\tau},i,a_{i},pub,hist_{i-1})\) _should return the value 1._  
[PERSON] et al. [1] formalized security requirements for OM-UEA schemes by considering different kinds of adversaries. In their model, the adversary is able to control the communication channel between the parties and its goal is to deceive the verifier into considering as valid an authentication message that was not actually generated by the prover. They considered both passive and active adversarial behaviors.