## 3 A Construction Based on Digital Signatures
### A Lightweight Instance  
OM-UEA schemes are particularly suitable to providing resistance to impersonation attacks in applications requiring continuous verification of user/device identities. This is of paramount importance, especially in the context of the Internet of Things (IoT), where continuous entity authentication is becoming essential. In such settings, given the limited computing power of the parties (especially the prover) and the often limited bandwidth channel, it is desirable to build one-message unilateral entity authentication schemes that require light computations.  
In order to have a fast signing procedure and an optimal storage requirement on the signer's side, [PERSON] et al. [2] proposed the LiS1 signature scheme, which is based on chameleon hash functions [26]. A chameleon hash function \(\mathcal{CH}\) is a one-way hash function with trapdoor: if we do not know the associated trapdoor, it is hard to compute pre-images and collisions for the function. On the other hand, with knowledge of the trapdoor, collisions are efficiently computable. The main idea of the LiS1 scheme is to compute the signature verification key as a sequence of \(\ell\) chameleon hash values corresponding to a set of dummy message/randomness pairs \((m_{i},r_{i})\), for \(1\leq i\leq\ell\), where \(\ell\) is the maximum number of messages that can be signed. In order to sign a message \(m_{i}^{\prime}\), which is different from each dummy message, the signer can easily compute a collision \(r_{i}^{\prime}\) for the dummy pair \((m_{i},r_{i})\), i.e., such that \(\mathcal{CH}(m_{i},r_{i})=\mathcal{CH}(m_{i}^{\prime},r_{i}^{\prime})\). Such a value \(r_{i}^{\prime}\) is then sent to the verifier, along with the message \(m_{i}^{\prime}\). The LiS1 scheme has been shown to be existentially unforgeable under a non-adaptive chosen message attack [2]; thus, when used in our DS-EAC, it gives rise to an OM-UEA scheme for \(\ell\)-sessions, which is secure in the sense of \(\ell\)-IMP-A-ST.  
In order to reduce the size of the signing key in the LiS1 scheme, [PERSON] et al. [2] proposed to fix all dummy messages \(m_{i}\) as a constant \(M\), and to use a universal hash function \(\mathcal{UHF}\)[27] to chain up all dummy randomness, i.e., each value \(r_{i}\) is computed as \(r_{i}=\mathcal{UHF}(k,r_{i-1})\) for \(1\leq i\leq\ell\), where \(r_{0}\) is chosen at random and \(k\) is the key of \(\mathcal{UHF}\). With such a modification, the signer is only required to store the initial value \(r_{0}\), along with the key \(k\) for the universal hash family, in addition to the message \(M\) and the trapdoor of the chameleon hash function. Moreover, in order to reduce the size of the signature verification key in the LiS1 schemes, [PERSON] et al. also proposed using a Bloom filter [28] to efficiently represent the set of hash values stored in it. Such a data structure allows us to efficiently test whether an element belongs to a set but, due to its probabilistic nature, false positives are possible. With such a modification, the signature verification key in the LiS1 scheme only consists of the public key of the chameleon hash function along with the Bloom filter.  
[PERSON] et al. [2] proposed instantiating the chameleon hash function by using a slight variant of the original discrete logarithm-based chameleon hash function proposed in [26], whereas the universal hash function is instantiated with the multiply modular scheme in [27]. The resulting scheme requires the signer to compute only two modular multiplications and three modular additions in order to sign a message. Moreover, the signing key in such a scheme is a bit string having a small size; indeed, it consists of five values chosen in \(Z_{q}^{*}\).