Updatable Signatures and Message Authentication Codes

Abstract

Cryptographic objects with updating capabilities have been proposed by Bellare, Goldreich and Goldwasser (CRYPTO’94) under the umbrella of incremental cryptography. They have recently seen increased interest, motivated by theoretical questions (Ananth et al., EC’17) as well as concrete practical motivations (Lehmann et al., EC’18; Groth et al. CRYPTO’18; Klooß et al., EC’19). In this work, the form of updatability we are particularly interested in is that primitives are key-updatable and allow to update “old” cryptographic objects, e.g., signatures or message authentication codes, from the “old” key to the updated key at the same time without requiring full access to the new key (i.e., only via a so-called update token).

Inspired by the rigorous study of updatable encryption by Lehmann and Tackmann (EC’18) and Boyd et al. (CRYPTO’20), we introduce a definitional framework for updatable signatures (USs) and message authentication codes (UMACs). We discuss several applications demonstrating that such primitives can be useful in practical applications, especially around key rotation in various domains, as well as serve as building blocks in other cryptographic schemes. We then turn to constructions and our focus there is on ones that are secure and practically efficient. In particular, we provide generic constructions from key-homomorphic primitives (signatures and PRFs) as well as direct constructions. This allows us to instantiate these primitives from various assumptions such as DDH or CDH (latter in bilinear groups), or the (R)LWE and the SIS assumptions. As an example, we obtain highly practical US schemes from BLS signatures or UMAC schemes from the Naor-Pinkas-Reingold PRF.

1 Introduction

Updatable cryptographic primitives, initially introduced as incremental cryptography [10, 11], support the transformation of one cryptographic object to a related one without recomputing it entirely and have been widely studied (cf. [6] for an overview). Recently, Ananth et al. in [2] studied a unified approach towards adding updatability features to many cryptographic primitives such as attribute-based encryption, functional encryption or more generally cryptographic circuit compilers. Moreover, they study the updatability for classical protocols such as zero-knowledge proofs and secure multi-party computation. Their constructions thereby rely on a novel updatable version of randomized encodings [4, 33]. Besides exploring such updatable primitives from a rather theoretical perspective, there have been various interesting lines of work on specific updatable primitives inspired by concrete practical applications. For instance, Groth et al. in [32] introduce the notion of an updatable common reference string (CRS) and apply it to zk-SNARKs (used within many real world protocols in the cryptocurrency and distributed ledger domain) to reduce the trust in the generator of the CRS and cope with malicious CRS generators. Later in [43] Lipmaa studied quasi-adaptive NIZK (QA-NIZK) proofs in an updatable CRS setting where in addition to CRS updates “old” valid proofs can be updated to be still valid under an updated CRS. Another such primitive that is strongly motivated by practical applications and has recently been studied quite intensively is updatable encryption (UE) [14, 15, 18, 27, 35, 40, 42]. An UE scheme is a symmetric encryption scheme that allows the key holder to update keys and to compute an update token, which can be given to a party storing ciphertexts, and can be used to update existing ciphertexts to ones under the new key. UE is motivated by the fact that it is a good key management practice to change encryption keys periodically and it avoids the cumbersome requirement to download, decrypt and re-encrypt and upload all the data again.  

Motivation. Our work is now essentially motivated by this previous work on UE and the observation that it is equally important in context of signatures and message authentication codes (MACs) to follow good key management practices and to periodically switch keys. For instance, any kind of software distribution channels including App stores or operating system updates rely on signatures to ensure the authenticity of the software they distribute. Moreover, file systems or (outsourced) databases usually require signatures or MACs to ensure integrity of stored data (we discuss this in more detail later in this section). What we envision therefore are signatures and MACs that are updatable in a sense that, similar to UE, holders of a secret key can compute a token that allows some third party to update existing signatures and MACs to ones valid under the new key. Thereby, we want to guarantee unforgeability even if the adversary can see lots of different keys and tokens with the restriction that we exclude trivial forgeries (we discuss this possible leakage in more detail later).  

Related and Previous Work. While there are notions of signatures that support updating keys or even guarantee unforgeability when allowing queries under (adversarially) updated keys, none of them rigorously covers what we have sketched above and in particular guaranteeing security even if signatures can be updated between different keys. Closest are updatable signatures by Klooß et al. [40] implicitly used in one of their UE constructions. But they do not treat their security in the updatable setting and rather sketch how they can be obtained from unforgeable signatures in combination with generic properties of the token generation. Key-updatable signatures by Jaeger and Stepanovs [34] or key-updating signatures by Jost et al. [38] proposed in context of secure messaging allow to update keys and obtain signatures under updated keys, but do not consider signature updates. Similarly, signatures with re-randomizable keys by Fleischhacker et al. [29] consider adversarially chosen updates of the secret key (and access to a signing oracle under updated keys), but do not consider updating existing signatures. Somewhat orthogonal, key-homomorphic signatures by Derler and Slamanig [25] consider updating keys as well as updating existing signatures (this concept is similar to key-homomorphic PRFs [15]). But they only study the required properties functional-wise and do not consider an unforgeability notion (rather they implicitly prove them for their respective applications). Nevertheless, as we will see these key-homomorphic signatures and key-homomorphic PRFs [8, 15, 39] can be used as the basis for some constructions of US and UMACs, respectively. Finally, there is a recent notion of updatable signatures by Abdolmaleki et al. [1], which however focuses on key-update tokens that serve as a proof of correct update and allow extractability of update keys in order to be used within zk-SNARKs with updatable CRS.  

Our Framework for Updatable Signatures and MACs. Since none of the existing works cover updatable signatures with strong security guarantees (and there is to the best of our knowledge no work related to updatable MACs), our goal is to design a comprehensive framework and security model. Therefore, similar to models for UE [18, 42], we use the concept of epochs, where each epoch e has an associated key-pair $(sk _e,pk _e)$ of a signature scheme starting with an initial key-pair in epoch 1 (all the discussion below analogously applies to UMACs). An US scheme then provides the functionality that in epoch e given $(sk _e,pk _e)$ we can compute a key-pair $(sk _{e+1},pk _{e+1})$ for the next epoch together with an update token $\varDelta _{e+1}$ that is capable of updating signatures under a key from epoch e to $e+1$. Our focus is on schemes where these update tokens are independent of the signature and so $\varDelta _{e+1}$ can be used for any signature from epoch e. We want that the schemes support an arbitrary number of epochs (any polynomial in the security parameters) but to support schemes from lattice assumptions we also consider a bounded number of epochs (bounded US) with a concrete bound T that usually depends on some parameters of the scheme. The goal is now to achieve strong security guarantees, in particular, the US scheme stays secure even after signing keys are compromised (a feature which is called post-compromise secrecy) and also before signing keys get corrupted (a feature called forward secrecy). Furthermore, outside of our model, we consider as an additional practical feature of US and UMAC the so called message-independence. This means that the update functionality only requires the update token and a signature, but does not need to access the respective message.

For unforgeability, we allow the adversary to trigger arbitrary signature computations, computations of next keys and updates adaptively and also adaptively compromise tokens and signing keys. We thereby use the concept of leakage profiles originally defined in [42] and also used in [18] to capture key, token, and signature “leakage” that cannot be captured by the oracles in the security experiment. The reason is that due to the nature of updates, US schemes inherently allow for information leakage of updated message-signature pairs, keys, and tokens besides what is modeled in the security experiment. For instance, if the adversary compromises a secret key $sk _e$ and a token $\varDelta _{e+1}$ it might be possible to derive $sk _{e+1}$ (or $sk _e$ from key $sk _{e+1}$ and token $\varDelta _{e+1}$). Also, a token $\varDelta _e$ besides allowing to update signatures into the next epoch may also allow to switch signatures back to previous epochs. However, we stress that in contrast to UE, where no-directional UE schemes are highly desirable, for US it does not seem to be that useful. The reason is that upgrading old signatures is covered by correctness (and thus cannot be prevented) and preventing switching keys or signatures back to previous epochs is only required if old public keys are not considered revoked (and we currently do not see such applications).

In addition to the unforgeability notion, we also provide an unlinkability notion that essentially says that updated signatures cannot be distinguished from fresh signatures. More precisely, we require that an adversary even when given all signing keys, tokens as well as signatures is not able to distinguish a fresh signature from an updated version of the signature that it already holds. While this property does not seem essential to the practical applications discussed below, we discuss cryptographic applications where this notion is important.  

Exploring Applications. We will now discuss practical as well as cryptographic applications of US and UMACs.  

Key Rotation in Software Distributions with US. Software distribution channels including App stores such as Google Play [26, 31, 52], Apple’s App Store [3], or Microsoft’s Windows Apps [45] and Windows Updates, or Linux distributions such as Debian [41], Ubuntu, Red Hat [49] and Arch Linux [5] rely on signatures to ensure the authenticity of their software packages. In one way or another, they either sign indices including hashes of the software packages or sign the software packages directly. For the latter, packages are often signed by individual developers whose keys are either signed by some central party like the app store provider or are shipped to the user directly via keyring packages containing all trusted keys. In this setting, key rotation of individual developer keys becomes an issue, since, if keys are rotated, all software packages signed by the old key have to be re-signed with the new one. The same issue can also be observed in the context of signed boot loaders and kernels for secure boot [44]. When relying on US, key rotation of developer keys becomes less of a burden on the developer. Indeed, the developer would update the key and produce an update token which is then used to update all signatures from this developer. Thus, instead of the developer having to re-sign all their packages, the signature adaption can be outsourced to a service run by the app store. Note that the effort for certifying new or updated keys would be the same in both settings.  

File System and (Outsourced) Database Integrity with UMACs. Modern file systems including zfs [54] ensure the on-disk data integrity by storing hashes of the data. Additionally, when replicating data from one storage pool to another, the digests ensure integrity during transport. Similarly, databases support integrity checks which are helpful for replication and backups. Especially interesting is the application to outsourced databases [46, 53], where in case of key-rotation the use of an UMAC enables these updates to be performed without re-computing all the authentication tags from scratch and without giving the actual key to the third party hosting the database.  

Malleable Signatures and Revocation in Privacy Protocols. Redactable signatures (RS) [37, 51] and sanitizable signatures (SS) [7, 19] are malleable signatures that allow to remove parts from signed messages or replace designated parts of signed messages by designated parties without invalidating the signatures. They have numerous applications, but due to their selective disclosure functionality are especially attractive to protect privacy in medical documents when shared with other parties. Replacing the conventional EUF-CMA secure signature scheme that typically serves as a building block in such schemes with an US can, similar to the above applications, help to reduce re-signing effort in case of a key-rotation. This is particularly interesting when large amounts of signed medical documents are involved. US providing unlinkability can firstly help if one requires unlinkability from the respective RS or SS scheme (cf. [20] for a discussion of the linkability problem when joining different versions of a document to derive additional information) even over different versions of one document under different (updated) keys. Secondly, unlinkable RS [21, 50] serve as a building block to construct anonymous credentials (ACs). In this context, unlinkable US allow to realize credential revocation in the following way: the issuer can provide an update token to a service that receives signatures from users and only updates credentials of non-revoked users to the current issuer key. Unlinkability of the US thereby in particular guarantees that it is hard to distinguish between credentials of non-revoked users from that of newly joined users. The same revocation idea can also be applied to replace re-issuing based revocation [17] in group signatures that follow the sign-randomize-prove paradigm [12, 24, 48]. Moreover, UMACs seem to be suitable for the same purpose in keyed-verification ACs [22], i.e., ACs where issuer and verifier are the same entity, typically constructed from algebraic MACs instead of signatures. An in-depth study of these cryptographic applications of US and UMACs is considered as future work.  

CCA-Secure UE with Ciphertext Integrity Using UMACs. Klooß et al. [40] showed how to achieve CCA security and ciphertext integrity for UE using the Encrypt-and-MAC transformation. Their transformation requires encryption and MAC schemes that support key-rotation. In [40] the key-rotatable MAC was instantiated using the DDH-based PRF (NPR) [47] using a key-switching akin to the proxy re-encryption approach due to Blaze et al. [13]. We note that a UMAC satisfies the key-rotatable property, and hence, can be directly plugged into the described transformation to obtain CCA-secure UE with ciphertext integrity by using a suitable encryption scheme and any UMAC.  

Further Contributions. Besides the already discussed comprehensive framework for US and UMACs, we provide the following contributions:  

US and UMAC from KH Primitives. We construct US from key-homomorphic (KH) signatures [25], which satisfy some additional requirement that all natural schemes provide. Due to the properties of KH signatures, they are unlinkable. With respect to provable security, we use a proof-technique that is inspired by the key-insulation technique due to Klooß et al. [40], where we essentially can use the unlinkability property of the underlying KH signature. Similarly, we obtain fixed-length UMACs from key-homomorphic PRFs [15], which we generically turn into variable-input UMACs and our proof technique essentially follows the ones for signatures. This allows us to instantiate US and UMACs from various assumptions such as DDH or CDH (latter in bilinear groups). For instance, we achieve instantiations for highly practical US schemes from BLS signatures [16] or UMAC schemes from the Naor-Pinkas-Reingold PRF [47]. Interestingly, by using some tricks, we can show how to generically construct UMACs from “almost” key-homomorphic PRFs [15] leading to constructions from the (R)LWE assumption, and thus, post-quantum UMACs. Unfortunately, there are no known key-homomorphic signatures with the required properties from post-quantum assumptions. Consequently, we investigate direct constructions of US from lattices. On the positive side we are able to provide a US construction based on the probabilistic GPV scheme [30] under the SIS assumption. On the negative side, we therefore have to weaken the adversarial capabilities to prove it secure. While we provide formal evidence that this does not seem to be too problematic in practice, we consider it as a challenging open issue to construct US schemes from post-quantum assumptions being provable secure without any such restrictions.  

Message-Independent US and UMAC. We further discuss message-independent constructions of US and UMAC from the BLS signature scheme [16], from the Pointcheval-Sanders signature scheme [48], and from the Naor-Pinkas-Reingold PRF [47]. These overcome the limitations of the respective constructions directly obtained from them viewed as KH-signatures and -PRFs, which are message-dependent. Message-independence can be a desirable property in practical applications, as access to the message is not required for updating signatures and MACs, i.e., if they are verified and then stored and at a later point updated (in a batch) one does not need to access the respective messages and improves update performance.

2 Preliminaries

Notation. For $n\in \mathbb {N}$, let $[n]:=\{1,\ldots ,n\}$, and let $\lambda \in \mathbb {N}$ be the security parameter. For a finite set $\mathcal {S}$, we denote by $s\leftarrow \mathcal {S}$ the process of sampling $s$ uniformly from $\mathcal {S}$. For an algorithm $A$, let $y\leftarrow A(\lambda ,x)$ be the process of running $A$ on input $(\lambda ,x)$ with access to uniformly random coins and assigning the result to $y$ (we may omit to mention the $\lambda$-input explicitly and assume that all algorithms take $\lambda$ as input). To make the random coins $r$ explicit, we write $A(\lambda ,x;r)$. We use $\bot$ to indicate that an algorithm terminates with an error and $A^B$ when A has oracle access to B, where B may return $\top$ as a distinguished special symbol. We say an algorithm $A$ is probabilistic polynomial time (PPT) if the running time of $A$ is polynomial in $\lambda$. Given $\mathbf {x}\in \mathbb {Z}^n$, we denote by $||\mathbf {x}||$ its infinity norm, i.e., for $\mathbf {x}=(x_1,x_2,\dots ,x_n)$, we have $||\mathbf {x}||:=\max (|x_1|,\dots ,|x_n|)$. A function $f$ is negligible if its absolute value is smaller than the inverse of any polynomial (i.e., if $\forall c\exists k_0\forall \lambda \ge k_0:|f(\lambda )|<1/ \lambda ^c$). We may write $q=q(\lambda )$ if we mean that the value $q$ depends polynomially on $\lambda$.

Basic Primitives. Due to the lack of space we recall PRFs, signature schemes and MACs in the full version.

Key-homomorphic Signatures. We recall relevant parts of the definitional framework of key-homomorphic signatures as introduced in [23, 25]. Let $\varSigma = (\mathsf{KGen},\mathsf{Sign}, \mathsf{Verify})$ be a signature scheme and the secret and public key elements live in groups $(\mathbb {H}, +)$ and $(\mathbb {E}, \cdot )$, respectively. For these two groups it is required that group operations, inversions, membership testing as well as sampling from the uniform distribution are efficient.

Definition 1

(Secret Key to Public Key Homomorphism [25]). A signature scheme $\varSigma$ provides a secret key to public key homomorphism, if there exists an efficiently computable map $\mu : \mathbb {H}\rightarrow \mathbb {E}$ such that for all $sk, sk ' \in \mathbb {H}$ it holds that $\mu (sk +sk ') = \mu (sk) \cdot \mu (sk ')$, and for all $(sk, pk)\leftarrow \mathsf {Gen} (\lambda )$, it holds that $pk = \mu (sk)$.

In the discrete logarithm setting, it is usually the case $sk \leftarrow \mathbb {Z} _p$ and $pk =g^{sk}$ with g being the generator of some group $\mathbb {G}$ of prime order p.

Definition 2

(Key-Homomorphic Signatures [23]). A signature scheme is called key-homomorphic, if it provides a secret key to public key homomorphism and an additional PPT algorithm $\mathsf Adapt$, defined as:

• $\mathsf{Adapt}(pk, M, \sigma , \varDelta ):$ Given a public key $pk$, a message M, a signature $\sigma$, and a shift amount $\varDelta$ outputs a public key $pk '$ and a signature $\sigma '$,

such that for all $\varDelta \in \mathbb {H}$ and all $(pk,sk) \leftarrow \mathsf {Gen} (\lambda )$, all messages $M\in \mathcal {M}$ and all $\sigma$ with $\mathsf {Ver} (pk, M,\sigma )=1$ and $(pk ',\sigma ') \leftarrow \mathsf{Adapt}(pk, M,\sigma ,\varDelta )$ it holds that

$$\begin{aligned} \Pr [\mathsf {Ver} (pk ',M,\sigma ') =1] = 1 ~~\wedge ~~ pk ' = \mu (\varDelta )\cdot pk. \end{aligned}$$

The following notion covers whether adapted signatures look like freshly generated ones, even if the initial signature used in $\mathsf Adapt$ is known.

Definition 3

(Perfect Adaption [25]). A key-homomorphic signature scheme provides perfect adaption, if for every $\kappa \in \mathbb {N}$, every message $M\in \mathcal {M}$, it holds that

$$ \left[ \sigma , (sk, pk), \mathsf{Adapt}(pk, M, \sigma , \varDelta ) \right] , $$

where $(sk, pk) \leftarrow \mathsf {Gen} (\lambda ),~\sigma \leftarrow \mathsf{Sign}(sk, M),~\varDelta \leftarrow \mathbb {H}$, and

$$ \left[ \sigma , (sk, \mu (sk)), (\mu (sk) \cdot \mu (\varDelta ), \mathsf{Sign}(sk + \varDelta , M)) \right] , $$

where $sk \leftarrow \mathbb {H},~\sigma \leftarrow \mathsf{Sign}(sk, M),~\varDelta \leftarrow \mathbb {H}$, are identically distributed.

Key-homomorphic PRFs. Key-homomorphic PRFs (KH-PRFs) are PRFs which satisfy additional algebraic properties. More precisely, the key space $\mathcal {K}$ and the range $\mathcal {Y}$ of the PRF exhibit certain group structures such that the evaluation of the PRF on any fixed input $x \in \mathcal {X}$ is homomorphic with the respect to these group structures. More precisely:

Definition 4

(Key-Homomorphic PRFs [15, 47]). Let $(\mathcal {K},\oplus ), (\mathcal {Y},+)$ be groups. Then, a keyed function $F :\mathcal {K} \times \mathcal {X} \rightarrow \mathcal {Y}$ is a key-homomorphic PRF (KH-PRF) if F is a secure PRF and for every key $k_1, k_2 \in \mathcal {K}$ and every input $x \in \mathcal {X}$, we have

$$ F(k_1,x) + F(k_2,x) = F(k_1 \oplus k_2, x). $$

We note that KH-PRFs constructed from assumptions such as Learning with Errors (LWE) as proposed in [14, 15, 39] do not achieve the perfect homomorphism as described in the definition above, but are only “almost” key-homomorphic in that $F(k_1,x) + F(k_2,x) = F(k_1 \oplus k_2, x) + e$, where e is a small error term. For them one needs to bound the number of successive applications and provide T-time correctness for a pre-specified $T\ge 1$ (cf. [15, 39] for a comprehensive treatment). Note also, that only achieving an “almost” key-homomorphic property allows to distinguish fresh evaluations of the PRF from ones obtained via the key-homomorphic property.

3 Updatable MACs and Signatures

In this section, we present our definitional framework of updatable MACs and signatures. In order to make the illustration compact and avoid redundancy, we try to unify the notation as much as possible and will, whenever necessary, point to the differences between the two primitives.

3.1 Updatable MACs

We define updatable message authentication codes (UMACs) next and their security model in Sect. 3.3. An UMAC scheme $\mathsf {UMAC}$ with message space $\mathcal {M}$ is a tuple of the PPT algorithms $(\mathsf {Setup}$, $\mathsf {Next}$, $\mathsf {Sig}$, $\mathsf {Update}$, $\mathsf {Ver})$:

• $\mathsf {Setup} (\lambda ,n)$: On input security parameter $\lambda \in \mathbb {N}$ and the maximum number of epochs $n \in O(2^\lambda )$, the setup algorithm outputs a (secret) key $k_1$¹.

• $\mathsf {Next} (k_e)$: On input key $k_e$ for epoch $e\in [n-1]$, the key-update algorithm outputs an updated key $k_{e+1}$ together with an update token $\varDelta _{e+1}$.

• $\mathsf {Sig} (k_e,M)$: On input key $k_e$ for epoch $e\in [n ]$ and a message $M \in \mathcal {M}$, the signing algorithm outputs a tag $\sigma _e$².

• $\mathsf {Update} (\varDelta _{e+1},M,\sigma _e)$: On input an update token $\varDelta _{e+1}$, a message $M$, and a tag $\sigma _e$ for epoch $e<n$, the update algorithm outputs an updated message-tag pair $(M,\sigma _{e+1})$ or $\bot$.

• $\mathsf {Ver} (k_e,M,\sigma _e)$: On input key $k_e$, a message $M$, and a tag $\sigma _e$ for epoch $e\in [n ]$, the verification algorithm outputs a verdict $b\in \{0,1\}$.

Correctness of $\mathsf {UMAC}$. Correctness ensures that an update of a valid tag $\sigma _e$ (via $\varDelta _{e+1}$) from epoch e to $e + 1$ yields a valid tag $\sigma _{e+1}$ that can be verified under the epoch key $k_{e+1}$ which is derived from $k_e$. More formally, we require that for all $\lambda ,n \in \mathbb {N}$, for all $k_1\leftarrow \mathsf {Setup} (\lambda ,n)$, for all $e\in [n-1]$, for all $(k_{e+1},\varDelta _{e+1})\leftarrow \mathsf {Next} (k_e)$, for all $M \in \mathcal {M}$, for all $\sigma _e$ with $\mathsf {Ver} (k_e,M,\sigma _e)=1$, for all $(M,\sigma _{e+1})\leftarrow \mathsf {Update} (\varDelta _{e+1},M,\sigma _e)$, we have that $\Pr \big [\mathsf {Ver} (k_{e'},M,\sigma _{e'}) \ne 1\big ] \le \varepsilon (\lambda )$ holds, for all $e'\in [n ]$, where $\varepsilon (\lambda )=\mathsf {negl}(\lambda )$, and we call it perfectly correct if $\varepsilon (\lambda )=0$.

3.2 Updatable Signatures

We define updatable signatures (US) next and their security model in Sect. 3.3. An US scheme $\mathsf {US}$ with message space $\mathcal {M}$ is a tuple of the PPT algorithms $(\mathsf {Setup}$, $\mathsf {Next}$, $\mathsf {Sig}$, $\mathsf {Update}$, $\mathsf {Ver})$:

• $\mathsf {Setup} (\lambda ,n)$: On input security parameter $\lambda$ and the maximum number of epochs $n \in O(2^\lambda )$, the setup algorithm outputs a public and secret key pair $(pk _1,sk _1)$.³

• $\mathsf {Next} (pk _e, sk _e)$: On input a public key $pk _e$ and secret key $sk _e$ for epoch $e\in [n-1]$, the key-update algorithm outputs an updated public key $pk _{e+1}$, an updated secret key $sk _{e+1}$ and an update token $\varDelta _{e+1}$.

• $\mathsf {Sig} (sk _e,M)$: On input secret key $sk _e$ for epoch $e\in [n ]$ and a message $M \in \mathcal {M}$, the signing algorithm outputs a signature $\sigma _e$.

• $\mathsf {Update} (\varDelta _{e+1},M,\sigma _e)$: On input an update token $\varDelta _{e+1}$, a message $M$, and a signature $\sigma _e$ for epoch $e<n$, the update algorithm outputs an updated message-signature pair $(M,\sigma _{e+1})$ or $\bot$.

• $\mathsf {Ver} (pk _e,M,\sigma _e)$: On input public key $pk _e$, a message $M$, and a signature $\sigma _e$ for epoch $e\in [n ]$, the verification algorithm outputs a verdict $b\in \{0,1\}$.

Correctness of $\mathsf {US}$. For all $\lambda ,n \in \mathbb {N}$, for all $(pk _1,sk _1)\leftarrow \mathsf {Setup} (\lambda ,n)$, for all $e\in [n-1]$, for all $(pk _{e+1},sk _{e+1},\varDelta _{e+1})\leftarrow \mathsf {Next} (pk _e,sk _e)$, for all $M \in \mathcal {M}$, for all $\sigma _e$ with $\mathsf {Ver} (pk _e,M,\sigma _e)=1$, for all $(M,\sigma _{e+1})\leftarrow \mathsf {Update} (\varDelta _{e+1},M,\sigma _e)$, we have that $\Pr \big [\mathsf {Ver} (pk _{e'},M,\sigma _{e'}) \ne 1\big ] \le \varepsilon (\lambda )$ holds, for all $e'\in [n ]$, where $\varepsilon (\lambda )=\mathsf {negl}(\lambda )$, and we call it perfectly correct if $\varepsilon (\lambda )=0$.

3.3 Security of UMAC and US

We are now ready to define the security notions of UMAC and US where we will use U$\mathsf X$ with $\mathsf X\in \{$MAC, S$\}$ to distinguish between those two primitives. In order to make the description as compact as possible, we will use $pk _e$ and $sk _e$, for $e\in [n ]$, as handles to the public and secret key, respectively; where for UMACs we have $pk _e:=\bot$ and $sk _e:=k_e$. Moreover, we will also call the tags in UMACs signatures henceforth.

We introduce security definitions for existential unforgeability under chosen-message attack (U$\mathsf X$-EUF-CMA) and unlinkable updates under chosen-message attack (U$\mathsf X$-UU-CMA). Loosely speaking, the U$\mathsf X$-EUF-CMA notion ensures that signatures cannot be forged even when the PPT adversary sees many signatures of chosen messages while the U$\mathsf X$-UU-CMA notion guarantees that signatures derived from $\mathsf {Update}$ are unlinkable even when the PPT adversary sees many (updated) signatures of chosen messages.

In our security experiments, let $q\in \mathbb {N}$ be the number of signature queries and e the current epoch. Furthermore, we introduce a global state $\mathbf {S} =(\mathcal {I},\mathcal {K},\mathcal {T},\mathcal {S})$:

When the experiment is initialized, we set $\mathcal {I} =\{((pk_1,sk_1),\varDelta _1)\}$, for $(pk_1,sk_1)\leftarrow \mathsf {Setup} (\lambda ,n)$ and $\varDelta _1:=\bot$, and let $\mathcal {S}$, $\mathcal {K}$, and $\mathcal {T}$ be initially empty sets. Additionally, we require the following oracles which are eligible to change sets in $\mathbf {S}$ for any epoch $e'\in [e]$:

Leakage Profile $(\mathcal {K} ^*,\mathcal {T} ^*,\mathcal {S} ^*)$ . We use the concept of a leakage profile originally defined in [42] to capture key, token, and signature “leakage” that cannot be directly captured via oracles. The reason is that due to the nature of signature updates, U$\mathsf X$ schemes inherently allow for information leakage of updated message-signature pairs, keys, and tokens besides what is modeled via the global state $\mathbf{S}$. For example, one token $\varDelta _{e'+1}$ alone in such schemes is capable of updating polynomially many message-signature pairs $((M _{1},\sigma _{1,e'}),\dots ,(M _{\ell },\sigma _{\ell ,e'}))$, for all $\ell =\ell (\lambda )$ and for each epoch $e'\in [n-1]$. As this is required by the correctness of the scheme, we cannot capture which particular signature $\sigma '$ the adversary retrieves (via an update token) and, hence, cannot include it into $\mathcal {S}$.

Furthermore, signatures, keys, and tokens cannot only be “upgraded” but also potentially “downgraded”, e.g., a token $\varDelta _{e'}$ and key $sk _{e'}$ or a token $\varDelta _{e'}$ and a message-signature pair $(M,\sigma _{e'})$ for epoch $e'\in [n ]$ might be used to derive a key $sk _{e'-1}$ or message-signature pair $(M,\sigma _{e'-1})$ of the previous epoch $e'-1$, respectively. Hence, we cannot capture which particular key $sk '$ or signature $\sigma '$ the adversary retrieves (via an update token) and, hence, cannot include those as well into $\mathcal {K}$ or $\mathcal {S}$, respectively.

We want to emphasize that the directionality of updates, i.e., either bidirectional or unidirectional, is subject to discussion in updatable encryption [36]. In context of US or UMACs, we observe that due to correctness one always can upgrade signatures (so leakage in this direction does not add anything), and stronger schemes could only prevent to derive keys or signatures “into the past”. This, however, seems of limited interest in authentication primitives, where old keys are typically assumed to be invalidated. Consequently, we opted for the arguably simpler bidirectional setting.

When looking ahead, we will construct US from key-homomorphic (KH) signatures. Now, in [25], the authors also provide a number of constructions of KH signatures that provide a property being weaker than the one we are using and which is called adaption of signatures. Now, one could wonder why we do not support such schemes. Firstly, it would only allow to achieve a very weak notion of unlinkability. Secondly, and more importantly, all known KH signatures with this “weak” adaption (e.g., Schnorr or Guillou-Quisquater signatures) have the property that a signature and its updated version leak the update token. Consequently, an adversary who obtains a signing key in some old epoch and then sees a signature and its updated versions, can compute all the signing keys up to the epoch of the latest updated version it sees. As this results in very weak security guarantees, we decided that our framework should not support schemes with these weak security guarantees.

Now, let us consider an U$\mathsf X$ scheme with optimal leakage to be the one where we only have signature upgrade (but no downgrade) and tokens are not useful to upgrade or downgrade keys in any way. The leakage would be limited for such schemes, however, the model would still need to restrict the adversary to retrieve the update token in epoch $e^*-1$, i.e., $\varDelta _{e^*}$, where $e^*$ is the forgery epoch. The reason is that otherwise the adversary could trivially win the game by updating any signature computed under a corrupted key to epoch $e^*$. Hence, also such strong schemes with so-called no-directional key updates would not achieve any stronger security in our model; at least with the applications we have in mind.

Now we are ready to introduce the leakage profile. We model leakage via key-update, token, and signature-update inferences where the leakage profile $(\mathcal {K} ^*,\mathcal {T} ^*,\mathcal {S} ^*)$ of a concrete scheme is specified by the respective sets.

Key-Update Inferences. Key-update inferences of a specific U$\mathsf {X}$ scheme can be formally captured as $\mathcal {K} ^*$ with corrupted-key set $\mathcal {K}$ and corrupted-token set $\mathcal {T}$ maintained by the oracles:

$$\begin{aligned} \mathcal {K} ^*:= {\left\{ \begin{array}{ll} \{e\in [n ]~|~\mathsf{corrupt}\text {-}\mathsf{key}(e) = \mathsf{true}\} \text { with }\mathsf{true} = \mathsf{corrupt}\text {-}\mathsf{key}(e)\text { iff:}\\ ~~~(e\in \mathcal {K})\vee (e-1\in \mathcal {K} \wedge e\in \mathcal {T}) \vee (e+1\in \mathcal {K} \wedge e+1 \in \mathcal {T}). \end{array}\right. } \end{aligned}$$

Token Inferences. Token inferences can be formally captured as $\mathcal {T} ^*$ with corrupted-token set $\mathcal {T}$ and key-leakage set $\mathcal {K} ^*$:

$$\begin{aligned} \mathcal {T} ^*:=\{e\in [n ]~|~(e\in \mathcal {T})~\vee ~(e-1\in \mathcal {K} ^*~\wedge ~e \in \mathcal {K} ^*)\}. \end{aligned}$$

Signature-Update Inferences. Signature-update inferences can be formally captured as $\mathcal {S} ^*$ with corrupted-signature set $\mathcal {S}$ maintained by the oracles and sets $\mathcal {K} ^*$ and $\mathcal {T} ^*$ with $M \in \mathcal {M} \cup \{\top \}$⁴:

$$\begin{aligned} \mathcal {S} ^*:= {\left\{ \begin{array}{ll} \{(e,M)~|~\mathsf{corrupt}\text {-}\mathsf{sig}(e,M) = \mathsf{true}\}\text { with }\mathsf{true} = \mathsf{corrupt}\text {-}\mathsf{sig}(e,M)\text { iff:}\\ ~~~((e,M,\cdot )\in \mathcal {S})~\vee ~((e,M)\in \mathcal {K} ^*\times \{\top \})~\vee ~(\mathsf{corrupt}\text {-}\mathsf{sig}(e-1,M)~\wedge \\ ~~~e\in \mathcal {T} ^*)~\vee ~(\mathsf{corrupt}\text {-}\mathsf{sig}(e+1,M)~\wedge ~ e+1 \in \mathcal {T} ^*), \end{array}\right. } \end{aligned}$$

where $\mathsf{corrupt}\text {-}\mathsf{sig}(0,M)=\mathsf{false}$.

In Fig. 1 we provide an example of potential leakage in U$\mathsf {X}$ schemes with our leakage profile.

Fig. 1.

Example of directly obtained (green) and inferable information (blue) for U$\mathsf {X}$ schemes.

Existential Unforgeability Under Chosen-Message Attacks (U$\mathsf X$-EUF-CMA). Informally, the U$\mathsf X$-EUF-CMA notion ensures that no PPT adversary can non-trivially forge signatures even when the adversary adaptively compromises a number of keys and tokens. We say that an U$\mathsf X$ scheme is U$\mathsf X$-EUF-CMA-secure if any PPT adversary succeeds in the following experiment only with negligible probability. The experiment starts by computing the initial keys $(pk _1,sk _1)\leftarrow \mathsf {Setup} (\lambda ,n)$. During the experiment, via the oracles, the adversary may query signatures for any epoch $e'$ up to the current epoch e, iterate to the next epoch $e+1$, update signatures, and corrupt tokens or keys for any epoch $e'$ up to the current epoch e (note that the global state $\mathbf {S}$ is changed by the oracles). Eventually, the adversary outputs a message-signature pair $(M ^*,\sigma _{e^*}^*)$, for epoch $e^*\in [n]$, and succeeds if $\mathsf {Ver} (pk _{e^*},M ^*,\sigma _{e^*}^*)=1$ in the US case and $\mathsf {Ver} (sk _{e^*},M ^*,\sigma _{e^*}^*)=1$ in the UMAC case, and the adversary is valid which we define in Definition 5.

Definition 5

Validity of $A$ for U$\mathsf X$-EUF-CMA). Depending on $(\mathcal {S} ^*,\mathcal {K} ^*,\mathcal {T} ^*)$, a PPT adversary $A$ is valid in the U$\mathsf X$-EUF-CMA experiment if

$$\begin{aligned} \{\{(e^*,\top )\}\cup \{(e^*,M ^*)\}\}\cap \mathcal {S} ^*=\emptyset , \end{aligned}$$

(1)

i.e., $A$ has not learned any useful forgery-message information for epoch $e^*$.

Remark. Definition 5 essentially says that the adversary is not able to derive a valid message-signature pair for epoch $e^*$ which excludes trivial wins. The leftmost term in Eq. (1) “checks” that $A$ does not possess a valid (derived) secret key in $e^*$ while the middle term “checks” that $A$ is not able to derive a valid signature for $M ^*$ in epoch $e^*$ via corrupted tokens.

See that the keys $(pk_{e^*},sk _{e^*})$ for any $e^*\in [n]$ can be derived, i.e., if $e^*\le e$, we have that $((pk _{e^*},sk _{e^*}),\cdot )\in \mathcal {I}$, otherwise, if $e^*>e$, we can derive $(pk _{e^*},sk _{e^*})$ iteratively by invoking $\mathsf {Next} '$ starting with $(pk _e,sk _e)$. If $e^*\le e$ we set $e_{\max }:=e$, else $e_{\max }:=e^*$. Figure 2 depicts the U$\mathsf X$-EUF-CMA experiments.

Definition 6

(U$\mathsf X$-EUF-CMA security of U$\mathsf X$). A U$\mathsf X$ scheme $\mathsf {UX}$ is U$\mathsf X$-EUF-CMA-secure iff for any valid PPT adversary $A$ the advantage function

$$\mathsf {Adv}^{\mathsf {ux}\text {-}\mathsf {euf}\text {-}\mathsf {cma}}_{\mathsf {UX},A}(\lambda ,n):=\Pr \left[ {\mathsf {Exp}^{\mathsf {ux}\text {-}\mathsf {euf}\text {-}\mathsf {cma}}_{\mathsf {UX},A}(\lambda ,n)=1}\right] ,$$

is negligible in $\lambda$, where $\mathsf {Exp}^{\mathsf {ux}\text {-}\mathsf {euf}\text {-}\mathsf {cma}}_{\mathsf {US},A}(\lambda ,n)$ is defined in Fig. 2.

Fig. 2.

The U$\mathsf X$-EUF-CMA security notions for $\mathsf {UX}$. For $\mathsf {US}$, we verify $\mathsf {Ver} (pk _{e^*},M ^*,\sigma ^*_{e^*})=1$; for $\mathsf {UMAC}$, we use $\mathsf {Ver} (sk _{e^*},M ^*,\sigma ^*_{e^*})=1$ in the last step.

Unlinkable Updates Under Chosen-Message Attacks (U$\mathsf X$-UU-CMA). Informally, the U$\mathsf X$-UU-CMA notion ensures that no PPT adversary can distinguish fresh signatures from updated signatures even seeing (all) keys, update tokens and signatures from the past. We say that an U$\mathsf X$ scheme is U$\mathsf X$-UU-CMA-secure if any PPT adversary succeeds in the following experiment only with negligible probability. The experiment starts by computing the initial keys $(pk _1,sk _1)\leftarrow \mathsf {Setup} (\lambda ,n)$. During the experiment, via the oracles, the adversary may query signatures for any epoch $e'$ up to the current epoch e, iterate to the next epoch $e+1$, update signatures, and corrupt tokens or keys for any epoch $e'$ up to the current epoch e, and has access to a verification oracle (note that the global state $\mathbf {S}$ is changed by the oracles). Then, the adversary outputs a message $M^*$ and epoch $e^*$ for which it queried $\mathsf {Sig} '$ in some epoch $e'< e^*$. It receives a challenge signature $\sigma ^{(b)}$ which is either a fresh signature on $M^*$, $\sigma ^{(0)}$, or the existing signature for $M^*$ updated to epoch $e^*$, $\sigma ^{(1)}$. For the latter case, we use the compact notation of $\mathsf{UpdateCh}(M^*)$ to denote the repeated application of $\mathsf Update'$ starting with $\sigma _{e'}$ for $M^*$ and finally resulting in $\sigma ^{(1)}$ as signature for $M^*$ in epoch $e^*$ (note that $\mathsf Update'$ implicitly checks the condition $\mathsf {Ver} (pk _{e'},M^*,\sigma _{e'})=1$). In both cases, this might require calling repeatedly $\mathsf {Next}$ until $(sk _{e^*},pk _{e^*})$ is defined. Eventually it outputs a bit $b^*$ and wins if $b=b^*$. Note that the adversary can call $\mathsf{Corrupt}$ arbitrarily. We call an adversary valid if it queried $M^*$ to $\mathsf {Sig} '$ in some epoch $e'<e^*$. Figure 3 depicts the U$\mathsf X$-UU-CMA experiments.

Definition 7

(U$\mathsf X$-UU-CMA security of U$\mathsf X$). A U$\mathsf X$ scheme $\mathsf {UX}$ is U$\mathsf X$-UU-CMA-secure iff for any valid PPT adversary $A$ the advantage function

$$\mathsf {Adv}^{\mathsf {ux}\text {-}\mathsf {uu}\text {-}\mathsf {cma}}_{\mathsf {UX},A}(\lambda ,n):=|\Pr \left[ {\mathsf {Exp}^{\mathsf {ux}\text {-}\mathsf {uu}\text {-}\mathsf {cma}}_{\mathsf {UX},A}(\lambda ,n)=1}\right] -1/2|,$$

is negligible in $\lambda$, where $\mathsf {Exp}^{\mathsf {ux}\text {-}\mathsf {uu}\text {-}\mathsf {cma}}_{\mathsf {US},A}(\lambda ,n)$ is defined in Fig. 3.

Fig. 3.

The U$\mathsf X$-UU-CMA security notions for $\mathsf {UX}$.

4 Construction of Updatable Signatures

In this section, we will present different instantiations of updatable signatures from different assumptions (see Sect. 4.4 for an overview and discussion.)

4.1 Updatable Signatures from KH Signatures

Subsequently, we show how to generically construct US with polynomially many updates from key-homomorphic (KH) signatures. Let $\varSigma = (\mathsf {Gen},\mathsf {Sig},\mathsf {Adapt},\mathsf {Ver})$ be a KH signature scheme providing perfect adaption, where we denote the secret key space by $\mathbb {H}$ and the secret key to public key homomorphism by $\mu$. The so-obtained US scheme $\mathsf US$ is depicted in Fig. 4. Before discussing the security, we will note that correctness straightforwardly follows from inspection.

Theorem 1

Let $\varSigma = (\mathsf {Gen},\mathsf {Sig},\mathsf {Adapt},\mathsf {Ver})$ be a uniform-keys key-homomorphic signature scheme. If $\varSigma$ is EUF-CMA secure and provides perfect adaption, then the updatable signature scheme $\mathsf US$ from Fig. 4 is US-EUF-CMA-secure and US-UU-CMA secure.

In the above theorem, we require uniform-keys KH signatures, which we introduce now. This notion is satisfied by all natural schemes and in particular the ones discussed in [25]:

Definition 8 (Uniform-Keys Key-Homomorphic Signatures)

. A key-homomorphic signature scheme $\varSigma$ is said to be uniform-keys if the distribution of $sk$ with $(sk,pk)\leftarrow \varSigma .\mathsf {Gen} (1^{\lambda })$ is the uniform distribution over the secret key space $\mathbb {H}$.

Fig. 4.

US from KH signatures.

Helper Lemmas. Notice that a valid adversary should not trivially forge signatures using the updatable property of the US scheme and the information provided by the leakage profile (e.g., produce a valid signature for epoch $e'\in \mathcal {K} ^*$ using $sk _{e'}$ and update it to a valid signature for epoch $e^*$ using the update tokens in $\mathcal {T} ^*$) for epochs in an appropriate window containing epoch $e^*$. More formally, we can define

$$\begin{aligned} e^-&:=\max _{1\le e\le e^*}\left\{ e\mid e\not \in \mathcal {T} ^*\cup \mathcal {K} ^*\text { and }e'\not \in \mathcal {K} ^*,\; e'\in \mathcal {T} ^* \quad \forall ~e<e'\le e^*\right\} ,\\ e^+&:=\min _{ e^*< e\le e_{\max }}\left\{ e\mid e\not \in \mathcal {T} ^*\text { and }e'\not \in \mathcal {K} ^*,\; e'\in \mathcal {T} ^* \quad \forall ~e^*< e'<e\right\} , \end{aligned}$$

and let the interval $[e^-,e^+[$ denote such a window and notice that $e^-$ is well-defined. Suppose on the contrary that the set

$$E:=\left\{ e\in [1,e^*]\mid e\not \in \mathcal {T} ^*\cup \mathcal {K} ^*~\wedge ~ e'\not \in \mathcal {K} ^*,\; e'\in \mathcal {T} ^* \quad \forall ~ e<e'\le e^*\right\} ,$$

is empty (if it is not empty then it has a maximum element). We claim, by backward induction on the epoch number k and starting from $e^*$, that this implies that $[k,e^*]\subseteq \mathcal {T} ^*$ for all $k\in [1,e^*]$ which is a contradiction as $1\notin \mathcal {T} ^*$ by construction of $\mathcal {T} ^*$. The base case is $k=e^*$. Indeed if E is empty then $e^*\notin E$ which implies that $e^*\in \mathcal {T} ^*$ as $\not \exists \, e'$ with $e^*<e'\le e^*$ and it cannot be that $e^*\in \mathcal {K} ^*$. Now assume by induction hypothesis that $[k,e^*]\subseteq \mathcal {T} ^*$ for $k<e^*$. We deduce from it, using that $k-1\notin E$, that $k-1\in \mathcal {T} ^*$ as $k-1$ cannot be in $\mathcal {K} ^*$ by validity of the adversary when $[k,e^*]\subseteq \mathcal {T} ^*$. Hence, $[k-1,e^*-1]\subseteq \mathcal {T} ^*$ which concludes the proof. A similar argument also proves the well-definedness of $e^+$. We can summarize the above discussion in the following lemma.

Lemma 1

Let A be a valid adversary that produces a forgery in epoch $0<e^*\le e_{\max }$ in the U$\mathsf S$-EUF-CMA experiment, then there exists a maximum integer $0< e^-\le e^*$ and a minimum integer $e^*< e^+\le e_{\max }$ s.t. A

• 1) does not obtain tokens $\varDelta _{e^-}$ and $\varDelta _{e^+}$,

• 2) obtains no secret key $sk _{e}$ for all $e^-\le e<e^+$ and

• 3) can obtain all tokens $\varDelta _{e}$ for $e^-<e<e^+$,

from the queries made to the oracles. Subsequently, we often denote the interval $[e^-,e^+[$ as the window.

From Definition 8, the following lemma easily follows.

Lemma 2

Let $\varSigma$ be a uniform-keys key-homomorphic signature scheme. Then the following hold:

• 1) For every $(sk,pk)\leftarrow \varSigma .\mathsf {Gen} (1^{\lambda })$ the distributions of $sk +\varDelta$ with $\varDelta \leftarrow \mathbb {H}$ and $sk '$ with $(sk ',pk ')\leftarrow \varSigma .\mathsf {Gen} (1^{\lambda })$ are identical.

• 2) For every $(sk,pk)\leftarrow \varSigma .\mathsf {Gen} (1^{\lambda })$ and $\varDelta \in \mathbb {H}$ we have that $(sk +\varDelta ,pk \cdot \mu (\varDelta ))\in \varSigma .\mathsf {Gen} (1^{\lambda })$.

Now we are ready for the proof of Theorem 1.

Proof

First we observe that correctness follows straightforwardly from inspection.

For US-UU-CMA security, we can observe that in the US-UU-CMA experiment all keys, signing operations, updates and token computations are performed honestly by the experiment. Any adversary A is given access to all keys, tokens and signatures and what we need to consider is the computation of the challenge signature $\sigma ^{(b)}$. Now, due to the adaption property of $\varSigma$, the outputs of $\varSigma .\mathsf {Sig}$ and $\varSigma .\mathsf {Adapt}$ are identical and thus also the outputs of $\mathsf US.\mathsf {Sig}$ and $\mathsf US.\mathsf {Update}$. By repeatedly applying Definition 3 within $\mathsf{US.UpdateCh}$ for computing $\sigma ^{(1)}$ and using Lemma 2 we are done. More formally, let us consider the sequence of games as outlined below:

• Game 0. This is the experiment $\mathsf {Exp}^{\mathsf {us}\text {-}\mathsf {uu}\text {-}\mathsf {cma}}_{\mathsf {US},A}(\lambda ,n)$ with $b=0$, i.e., we always return $\sigma ^{(0)} \leftarrow \mathsf {Sig} (sk _{e^*},M^*)$.

• Game 1. This is the experiment $\mathsf {Exp}^{\mathsf {us}\text {-}\mathsf {uu}\text {-}\mathsf {cma}}_{\mathsf {US},A}(\lambda ,n)$ with $b=1$, i.e., we always return $\sigma ^{(1)}\leftarrow \mathsf{UpdateCh}(M^*)$.

Lemma 3 (Game 0 to Game 1)

For any adversary $A$ it holds that

$$|\Pr \left[ {S_{A,0}}\right] -\Pr \left[ {S_{A,1}}\right] |=0.$$

Observe that in both games the adversary A is given access to all keys, tokens and signatures and outputs a message $M^*$ and epoch $e^*$ for which it queried $\mathsf {Sig} '$ in some epoch $e'\le e^*$. Now, in $\mathbf{Game}~0$ we finally output $\sigma ^{(0)} \leftarrow \mathsf {Sig} (sk _{e^*},M^*)$, i.e., a fresh signature of $M^*$ that verifies under $pk _{e^*}$ to $A$. In $\mathbf{Game}~1$ let us denote by $\sigma _{e'}$ the signature for $M^*$ under $(sk _{e'},pk _{e'})$ that the adversary queried for message $M^*$ during the experiment. Let us w.l.o.g. assume that $(sk _{e^*},pk _{e^*})$ is already defined (otherwise repeatedly call $\mathsf {Next}$ until it is defined) and let $(sk _{e'+1},pk _{e'+1},\varDelta _{e'+1}),\ldots ,(sk _{e^*},pk _{e^*},\varDelta _{e^*})$ be the sequence of keys and update tokens. Now, $\mathsf UpdateCh$ does the following:

• For $i=e',\ldots ,e^*-1$ compute $\sigma _{i+1}\leftarrow \mathsf {Update} (\varDelta _{i+1},M^*,\sigma _{i})$, where $\mathsf {Update}$ parses $\varDelta _{i+1}=(\varDelta _{i+1}',pk _{i})$ and calls $\sigma _{i+1} \leftarrow \varSigma .\mathsf {Adapt} (pk _{i},M^*,\sigma _{i},\varDelta _{i+1}')$.

By using Lemma 2, we know that every key pair in the sequence $(sk _{e'},pk _{e'}),\ldots ,(sk _{e^*},pk _{e^*})$ is distributed identical as one obtained from $\varSigma .\mathsf {Gen}$. Now, this allows us to repeatedly apply the perfect adaption notion to the output of the previous $\mathsf {Update}$ in this sequence to conclude that in the sequence of signatures $(\sigma _{e_i},\ldots ,\sigma _{e^*}=:\sigma ^{(1)})$ the last signature $\sigma ^{(1)}$ is distributed identically to a fresh signature computed as $\mathsf {Sig} (sk _{e^*},M^*)$.

This lets us conclude that $\mathsf {Adv}^{\mathsf {us}\text {-}\mathsf {uu}\text {-}\mathsf {cma}}_{\mathsf {US},A}(\lambda ,n)=0$ for any adversary $A$, which concludes the proof of US-UU-CMA security.   $\square$

To prove US-EUF-CMA security, we reduce US-EUF-CMA security to the EUF-CMA security of $\varSigma$, where the challenger will be associated to period $e^-$. While we can use the $\mathsf {Sig}$ oracle of the EUF-CMA challenger for period $e^-$, we have to answer $\mathsf {Sig}$ queries for epoch $e^*$ and adjacent ones, and $\mathsf {Update}$ queries from older epochs to $e^*$ and from $e^*$ to newer epochs. Moreover, we have to provide secret keys and tokens on $\mathsf {Corrupt}$ queries to the adversary. By Lemma 1 we know that in order for an adversary to be valid and to rule out a trivial forgery, there needs to be a maximum epoch $1\le e^-\le e^*$ and a minimum epoch $e^*< e^+\le e_{\max }$ for which A does not query tokens $\varDelta _{e^-}$ and $\varDelta _{e^+}$ and consequently does not know any secret key but knows all tokens for the window of epochs $[e^-,e^+[$. We now can use the key insulation technique from Klooß et al. [40] for optimization, so that instead of guessing the challenge epoch $e^*$ and the window to the left and to the right, we only guess the boundaries of this region $e^-$ and $e^+$ (containing the challenge epoch somewhere) and we can just associate the EUF-CMA challenger of $\varSigma$ to some epoch in this interval (lets say $e^-$). This reduces the overall reduction loss from $e_{\max }^2(e_{\max }+1)$ to $e_{\max }(e_{\max }+1)$.

Outside of the window, i.e., for epochs up to $e^--1$ and starting from $e^+$ upwards, we will behave in our simulation as in the original game and in particular choose and know all secret keys and update tokens (except $\varDelta _{e^+}$). For all epochs inside the window, our strategy will be as follows: we do not know the secret keys associated to the epochs, but they are implicitly set by choosing for every epoch $e_i$ in the window a random token $\varDelta _{e_i}$ as in the real $\mathsf {Next}$ algorithm. Then for every epoch $e_i$ in the window starting from $e^-$ we use the secret key to public key homomorphism of $\varSigma$ and set the corresponding public key as $pk_{e_i}= pk_{e_{i-1}}\cdot \mu (\varDelta _{e_i})$ (for $e^-< e_i < e^+$). Now for any signature query for message M and epoch $e_i$ within the window, we query M to the EUF-CMA challenger of $\varSigma$ associated to $e^-$ and use the $\varSigma .\mathsf {Adapt}$ algorithm in the forwards direction to obtain the signature for M in epoch $e_i$ within the window. Note that due to the adaption property of $\varSigma$ and thus the identical distribution of signatures from $\varSigma .\mathsf {Sig}$ and $\varSigma .\mathsf {Adapt}$, this is indistinguishable for A. The $\mathsf {Update} '$ oracle is performed as in the original game for all those epochs where the update token is knows. For the remaining epochs, i.e., $e^-$ and $e^+$, when asked to update $(M, \sigma _{e^--1})$ (or $(M, \sigma _{e^+-1})$, respectively), we query M to the EUF-CMA challenger of $\varSigma$ associated to $e^-$ (or produce a fresh signature using $sk _{e^+}$, respectively) and return it to the adversary. Again by the adaption property of $\varSigma$ and thus the identical distribution of freshly generated signatures and updated ones, this is indistinguishable. Now if A outputs a valid forgery $(M^*,\sigma ^*_{e^*})$ for epoch $e^*$, if $e^*=e^-$ we can directly output it. Otherwise we use $\varSigma .\mathsf {Adapt}$ to adapt the forgery backwards into epoch $e^-$ and output it. Note that in any case a valid forgery output by A represents a valid forgery for $\varSigma$, as validity guarantees that we have never queried $M^*$ throughout the game for any epoch inside the window.

More formally, let us consider the following sequence of games.

• Game 0. This is the experiment $\mathsf {Exp}^{\mathsf {us}\text {-}\mathsf {euf}\text {-}\mathsf {cma}}_{\mathsf {US},A}(\lambda ,n)$.

• Game 1. This is identical to the previous game with the exception that we guess the window $[e^-,e^+[$ in which the epoch $e^*$ for which $A$ outputs the forgery is located and abort if our guess is incorrect.

• Game 2. This is identical to the previous game up to the following differences:

  • For call to $\mathsf {Next} '$ in epoch $e^--1$ we set $\varDelta _{e^-}:=\bot$ and run $(sk _{e^-},pk _{e^-})\leftarrow \varSigma .\mathsf {Gen} (1^\lambda )$ to obtain an independent key for epoch $e^-$. The same is done for a call to $\mathsf {Next} '$ in epoch $e^+-1$.

  • For each call to the $\mathsf {Next} '$ oracle for epoch $e\in \{e^-,\ldots ,e^+-2\}$, we run $\mathsf {Next} (pk _{e},\bot )$ where we ignore the secret key and just set the key implicitly via the public-key, i.e., choose random $sk ' \in \mathbb {H}$ and set $\varDelta _{e+1}':=sk '$ and $\varDelta _{e+1}:=(\varDelta _{e+1}',pk _{e})$, compute $pk _{e+1}:=pk _e\cdot \mu (\varDelta _{e+1})$, set $sk _{e+1}=\bot$.

  • For each call to the $\mathsf {Sig} '$ oracle for message M in any epoch e within $[e^-,e^+[$, we compute $\sigma \leftarrow \varSigma .\mathsf {Sig} (sk _{e^-},M)$ and then call $\varSigma .\mathsf {Adapt}$ using the respective public keys to adapt it to a signature $\sigma _e$ valid under $pk _e$ and add $(e,M,\sigma _e)$ to $\mathcal S$.

  • For each call to the $\mathsf {Update} '$ oracle for signature $(M, \sigma _e)$ in epoch $e\in \{e^--1,e^+-1\}$, we compute $\sigma _{e+1}\leftarrow \varSigma .\mathsf {Sig} (sk _{e+1}, M)$. We then add $(e+1, M, \sigma _{e+1})$ to $\mathcal S$ and $\mathcal U$, and return $\sigma _{e+1}$ to the adversary.

Now, let us analyze the transitions:

Lemma 4

For any adversary $A$ it holds that

$$\left( \frac{1}{(e_{max}+1)e_{max}}\right) \Pr \left[ {S_{A,0}}\right] \le \Pr \left[ {S_{A,1}}\right] .$$

Proof

We guess the window by simply drawing $e^-\leftarrow \{0,...,e_{max}\}$ and $e^+\leftarrow \{e^-+1,...,e_{max}\}$ uniformly at random. Thus, this guess is correct with probability at least $\frac{1}{(e_{max}+1)e_{max}}$ and if the guess turns out to be wrong, we abort. Note that such a window always exists for a valid adversary $A$ due to Lemma 1.   $\square$

Lemma 5

For any adversary $A$ it holds that

$$|\Pr \left[ {S_{A,1}}\right] -\Pr \left[ {S_{A,2}}\right] |=0.$$

Proof

We observe that due to having a valid adversary $A$ w.r.t. window $[e^-,e^+[$ and due to Lemma 1 we recall that $A$

• 1) does not obtain tokens $\varDelta _{e^-}$ and $\varDelta _{e^+}$,

• 2) obtains no secret key $sk _{e}$ for all $e^-\le e< e^+$ and

• 3) can obtain all tokens $\varDelta _{e}$ for $e^-<e<e^+$,

from the queries made to the oracles, given the leakage profile. Note that due to 1) we know that there implicitly exists a token mapping keys and signatures from $e^--1$ to $e^-$ and from $e^+-1$ to $e^+$ (but we do not need to know them) and all (implicit) keys due to Lemma 2 are distributed as expected. Also, all the tokens $\varDelta _{e}$ in this window that are given to $A$ are distributed as expected. Finally, we can use the same argumentation as in the proof of Lemma 3 to show all signatures given to the adversary within the window in $\mathbf{Game}~2$ are distributed identical to the ones in $\mathbf{Game}~1$.    $\square$

Lemma 6

For any adversary $A$ it holds $\Pr \left[ {S_{A,2}}\right] \le \mathsf {Adv}^{\mathsf {euf}\text {-}\mathsf {cma}}_{\varSigma ,A}(\lambda )$.

Proof

Now we are at the point where we can associate an EUF-CMA challenger for $\varSigma$ to the keys in time slot $e^-$. Now, for every signature query for message M and epoch e within the window to the $\mathsf {Sig} '$ oracle, we query M to the EUF-CMA challenger of $\varSigma$ and then execute the remaining parts of the $\mathsf {Sig} '$ oracle to adapt the so obtained signature in the forwards direction to obtain the signature for M in epoch e within the window. Now if $A$ eventually outputs a valid forgery $(M^*,\sigma ^*_{e^*})$ for epoch $e^*$, we know that in order to be valid, $A$ did not query message $M^*$ for any epoch within the window (otherwise, since it knows all tokens this would be a trivial forgery). In case $e^*=e^-$, we can directly output $(M^*,\sigma ^*_{e^*})$ to the EUF-CMA challenger of $\varSigma$. Otherwise, we use $\varSigma .\mathsf {Adapt}$ to adapt the forgery backwards into epoch $e^-$ and then output the message $M^*$ and the adapted signature $\sigma$ as forgery to the EUF-CMA challenger.

Taking all together this concludes the proof.   $\square$

4.2 Message-Independent US from the BLS Signature Scheme

Next, we discuss US schemes that do not require the message in order to update signatures, a feature which we call message-independence (MI). We prove that they are secure US in the conventional sense, i.e., in the model we always have access to the messages and verify their validity and we rather consider MI to be a practical feature in the following sense. In many practical applications, signatures can be verified offline at some point and then when performing (a batch of) updates at a later point in time, one does not need to access all the messages and verify the signatures. This helps to improve the performance of the updating procedure.

In Fig. 5, we provide a message-independent US scheme from the BLS signature. In contrast to BLS viewed as a KH signature scheme, where key updates are additive and the next public key is $pk ' = pk \cdot \tilde{g}^{\varDelta '} = \tilde{g}^{sk +\varDelta '}$, we here consider a slight variation where the key update is multiplicative, i.e., $pk ' = pk ^{\varDelta '} = \tilde{g}^{sk \cdot \varDelta '}$. While this does not anymore yield a KH signature scheme in the framework of [25], due to the absence of the secret to public key homomorphism, it is easy to see that this variant provides an $\mathsf {Adapt}$ algorithm satisfying Definition 2, i.e., given a signature $\sigma = H(M)^{sk}$ the update is computed as $\sigma ' = \sigma ^{\varDelta '} = H(M)^{sk \cdot \varDelta '}$. It is also easy to see that the BLS scheme with this $\mathsf {Adapt}$ algorithm satisfies perfect adaption (cf. Definition 3), where in the definition $\mu (sk)$ is replaced by $\tilde{g}^{sk}$ and $\mu (sk) \cdot \mu (\varDelta )$ is replaced by $\tilde{g}^{sk \cdot \varDelta }$.

Fig. 5.

US with message-independent updates from BLS signatures.

Consequently, we can exactly follow the proof of Theorem 1 with the only exception that we do not use $\mu$ for computing the $pk$’s in the window, but choose $\varDelta _{e_{i}}\leftarrow \mathbb {Z} _p$ and compute $pk_{e_i}=pk_{e_{i-1}}^{\varDelta _{e_{i}}}$ (for all $e^-\le e_i< e^+$). Moreover, it is easy to see that we adapt Lemma 2 with the same changes as discussed above. Checking correctness is straightforward. Hence, we obtain the following:

Corollary 1

Let $\varSigma = (\mathsf {Gen},\mathsf {Sig},\mathsf {Adapt},\mathsf {Ver})$ be the BLS signature scheme with the $\mathsf {Adapt}$ algorithm defined as $\left( pk ^{\varDelta '},\sigma ^{\varDelta '}\right) \leftarrow \mathsf {Adapt} (pk,M,\sigma , \varDelta ')$, then the updatable signature scheme $\mathsf US$ from Fig. 5 is US-EUF-CMA secure and US-UU-CMA secure.

MI US from PS Signatures. We note that the same technique (i.e., using multiplicative updates to obtain MI) can be applied to other KH signatures, such as Pointcheval-Sanders (PS) [48]. More precisely, for PS we can set the public key to $pk:= (\tilde{X}, \tilde{Y}) = (\tilde{g}^x, \tilde{g}^y)$ for the secret key $sk:= (x, y)$ with $x \leftarrow \mathbb {Z} _p$ and $y \leftarrow \mathbb {Z} _p^*$. The signature is computed by sampling $h \leftarrow \mathbb {G}_1^*$ and setting $\sigma := (\sigma _1, \sigma _2) = (h, h^{x + y \cdot m})$. The verification holds for $e(\sigma _1, \tilde{X} \cdot \tilde{Y}^m) = e(\sigma _2, \tilde{g})$. In order to provide message-independent updates, we can sample $\varDelta _1 \leftarrow \mathbb {Z} _p^*$ and $\varDelta _2 \leftarrow \mathbb {Z} _p$, set the update token to $\varDelta := (\varDelta _1, \varDelta _2)$, and compute the updated key pair as $sk ' := (x \cdot \varDelta _1 + \varDelta _2, y \cdot \varDelta _1)$ and $pk ' := (\tilde{X}', \tilde{Y}') = (\tilde{X}^{\varDelta _1} \cdot \tilde{g}^{\varDelta _2}, \tilde{Y}^{\varDelta _1})$. Then, the update procedure is performed by sampling a random $r \leftarrow \mathbb {Z} _p^*$ and computing $\sigma ' := (\sigma _1',\sigma _2') = (\sigma _1^r, \sigma _2^{r \cdot \varDelta _1} \cdot \sigma _1^{r \cdot \varDelta _2})$.

4.3 Towards Updatable Signatures from Lattices

In this section, we aim to construct an US scheme from lattices. In particular, we start from the well-known GPV signature scheme [30] and, by using methods inspired by the lattice-based proxy re-signature approach in [28], we obtain an US scheme that we call $\mathsf {US} _\mathsf {GPV}$. In order to prove its U$\mathsf S$-EUF-CMA security, however, we have to restrict the capabilities of the adversary, but will provide evidence that this does not seem to make a huge difference in the practical use of the scheme compared to the original leakage profile.

Let us briefly recall the construction of the GPV signature scheme in its probabilistic full-domain hash (FDH) variant. For a recollection of lattice preliminaries we refer the reader to the full version. In the following let $H: \{0,1\}^*\rightarrow \mathbb {Z}_q^n$ be a hash function modeled as a random oracle. The GPV signature scheme consists of the following algorithms:

• $\mathsf {Gen} (1^n)$: Run $\mathsf {TrapGen}(n,m,q,s)$ to get pair $(\mathbf {A},\mathbf {T}_{\mathbf {A}})$ ($\mathbf {A}$ is an $n\times m$ matrix over $\mathbb {Z}_q$ and $\mathbf {T}_{\mathbf {A}}$ is a short basis of $\Lambda ^\perp (\mathbf {A})$). Output $(pk=\mathbf {A},sk=\mathbf {T}_{\mathbf {A}})$.

• $\mathsf {Sig} (M,sk=\mathbf{T} _{\mathbf {A}})$: Sample $t\leftarrow \{0,1\}^n$, compute $\mathbf {y}=H(M||t)$, and output $(\mathbf{u} , t)$, where $\mathbf{u}$ is a short vector computed via $\mathbf{u} \leftarrow \mathsf {SamplePre}(\mathbf {A},\mathbf {T}_{\mathbf {A}},s,\mathbf {y})$.

• $\mathsf {Ver} ((\mathbf {u}, t),M,pk=\mathbf {A})$: Compute $\mathbf {y}=H(M||t)$. Output 1 if and only if $\mathbf {A}\cdot \mathbf {u}=\mathbf {y}$ and $\left\Vert \mathbf {u}\right\Vert$ is small enough, and 0 otherwise.

To transform this scheme into an updatable one, we can apply a method similar to the one used in [28] to generate the re-signing keys and re-sign signatures: given the secret key of epoch $e+1$, using the $\mathsf {SamplePre}$ algorithm, it is possible to compute a small norm matrix $\varDelta _{e+1}$ (for the sake of conciseness, we do not include the old public key as part of the update token) that maps, by left multiplication, the current public key to the previous one, i.e., $pk _{e+1}\cdot \varDelta _{e+1} = pk _e$. Then, we can use this matrix to map, by right multiplication, a signature valid in the previous epoch to a signature valid in the current one. The small norm of $\varDelta _{e+1}$ ensures that, in the update process, the norm of the signature does not increase “too much”. Figure 6 describes the so obtained lattice-based US scheme $\mathsf {US} _\mathsf {GPV}$.

Fig. 6.

Message-independent unidirectional US from GPV.

Correctness and Leakage Profile. In the $\mathsf {Next}$ algorithm, the token $\varDelta _e$ is computed by running $\mathsf {SamplePre}(\mathbf{A} _{e+1},\mathbf{T} _\mathbf{A _{e+1}},s,\mathbf{A} _e)$. In this way we obtain an $m\times m$ matrix $\varDelta _{e+1}$ (of short norm) such that

$$ \mathbf{A} _{e+1}\cdot \varDelta _{e+1} = \mathbf{A} _e. $$

If $\sigma _e=(\tau _e,t)$ is a valid signature of M under the public key $\mathbf{A} _e$, we must have that $\mathbf{A} _e \cdot \tau _e = H(M||t)$, and that $\tau _e$ is of small norm. When we update the signature $\sigma _e$ we get $\tau _{e+1}=\varDelta _{e+1}\cdot \tau _e$. Since both $\varDelta _e$ and $\tau _e$ are of small norm, so is $\tau _{e+1}$. Moreover

$$\begin{aligned} \begin{aligned} \mathbf{A} _{e+1}\cdot \tau _{e+1}&= \mathbf{A} _{e+1}\cdot (\varDelta _{e+1}\cdot \tau _e)=(\mathbf{A} _{e+1}\cdot \varDelta _{e+1})\cdot \tau _e\\&= \mathbf{A} _{e}\cdot \tau _e= H(M||t), \end{aligned} \end{aligned}$$

which proves correctness of the updated signature. As a signature produced by algorithm $\mathsf {Sign}$ has size $O(s\sqrt{m})$, and after each update, the size grows at the rate of O(sm), as in [28], we set the parameter used in verification to be $B=\omega (2^T)$. The US construction can support $T=\text {polylog}(\lambda )$ updates using the subexponential SIS assumption.

Modified Leakage Profile. As far as the leakage profile is concerned, in order to be able to prove the U$\mathsf S$-EUF-CMA security of $\mathsf {US} _\mathsf {GPV}$, we need to add a restriction that the adversary is not allowed to query the update oracle at epoch $e^--1$ to obtain signatures at epoch $e^-$. We note that this restriction is needed to allow the challenger to simulate all responses to the oracle queries of the adversary. In the general case, this weakened model would allow to prove US schemes US-EUF-CMA which leak the token when seeing a signature and its updated version (such as Schnorr type signatures). However, as proven in Proposition 1 below, even updating a large but limited amount of signatures will not leak the token for the $\mathsf {US} _\mathsf {GPV}$ scheme. Consequently, weakening the model merely seems to be an artifact that results from our proof technique, but does not seem to represent a significant weakness in practice.

Moreover, as updated signatures are distinguishable from fresh ones, one has to keep track of the different signatures given to the adversary: for this reason, in the security proof we will split the set $\mathcal {S}$ into sets $\mathcal {S} '$ and $\mathcal {U} '$, which will consist of the fresh and updated signatures respectively. In addition to also supporting the feature of message-independence, interestingly, the $\mathsf {US} _\mathsf {GPV}$ scheme satisfies also unidirectional updates: by construction, the secret key of epoch e alone is required to produce the update token $\varDelta _e$. In particular this implies that the token cannot be used to backward adapt signatures, since this will contradict the unforgeability of the underlying signature scheme. This “feature” can be seen as one reason for the weakening of the model, as it is incompatible with the proof technique used for the other US constructions.

Security of $\mathsf {US} _{\mathsf {GPV}}$. For this construction, we can prove the following theorem:

Theorem 2

Assuming the hardness of $\mathsf {SIS}_{q,n,m,2B}$, the US scheme $\mathsf {US} _{\mathsf {GPV}}$ from Fig. 6 is U$\mathsf S$-EUF-CMA secure, with the above discussed restriction on the adversary, in the random oracle model.

Proof (Sketch)

We can follow, here as well, the proof of Theorem 1: we guess the forgery period $e^*$ and the window $[e^-,e^+[$ (by the above discussion regarding the uni-directionality of the US under consideration, the window will be, in this case, one-sided, i.e., we can even assume that $A$ has access to $\varDelta _{e^+}$). Outside of the window, we will behave in our simulation as in the original game and will know all secret keys and update tokens. Inside the window, we start by embedding the $\mathsf {SIS}$ matrix $\mathbf {A}^*$ as public key of the forgery epoch $e^*$. We then have to distinguish the right part of the window, $e\in ]e^*,e^+[$, from the left part, $e\in [e^-,e^*[$. For all epochs e in the right part, we can produce $pk_e$ and $\varDelta _{e}$ as in the real game (and thus we also have the corresponding secret key $sk_e$). For those in the left part, we start by sampling $\varDelta _{e^*}\leftarrow \mathcal {D}_{\mathbb {Z}^{m\times m},s}$ and set $pk _{e^*-1}:=pk _{e^*}\cdot \varDelta _{e^*}$. Since this distribution is statistically close to the one of the matrices output by the $\mathsf {SamplePre}$ algorithm, the adversary will not be able to distinguish the simulation from the real game. We then iterate this process till we obtain $pk _{e^-}$. In this way we can respond to all secret key and token corruption queries. As far as the signature queries are concerned, we rely on the programmability of the random oracle model: when the adversary queries the signature oracle, we first sample the short vector that will serve as signature and then program the random oracle H accordingly. The presence of the “salt” t guarantees us that, except with negligible probability, we will be able to reply to all signing queries (e.g., even if the adversary asks for signature of the same message in different epochs, which would not be possible if there was no “salt” involved in the signing algorithm). The update queries can be answered as in the real game as, by the restriction imposed on the adversary, we will know all the tokens require to run the allowed update queries. Since simulation and real game are computationally indistinguishable, the reduction can derive a SIS solution from the forgery tuple.   $\square$

We provide a full proof in the full version.

Remark 1

The above $\mathsf {US} _\mathsf {GPV}$ scheme does not achieve US-UU-CMA security: Firstly, the tag associated to a signature is not changed during the update and, secondly, the norm of the signature acts as distinguishing feature between fresh and updated signatures.

The following proposition shows that, under the parameter restriction required by the $\mathsf {TrapGen}$ algorithm, i.e., $m\ge 5n\log q$, we can update a large but limited amount of signatures, namely k, without leaking the update token $\varDelta$ to the adversary.

Proposition 1

Let $m\ge 5n\log q$ and $k\le n$. For any PPT adversary $\mathcal {A}$, the probability that $\mathcal {A}$ on input $(pk_e, sk_e, pk_{e+1})$ and any k pairs of updated signatures $(\tau _{M_i,t_i,e}, \varDelta _{e+1}\cdot \tau _{M_i,t_i,e})$ outputs the update token $\varDelta _{e+1}$ is negligible.

Proof

By the second claim of Lemma 5.2 from [30], $\varDelta _{e+1}$ is distributed according to a discrete Gaussian over $\mathbb {Z}^{m\times m}$, which has, by Lemma 2.10 from [30], at least min-entropy $m(m-1)$. By the chain rule of min-entropy, every pair of updated signatures $(\tau _e, \varDelta _{e+1}\cdot \tau _e)$ lowers the entropy of $\varDelta _{e+1}$ by $m\log q$. Hence the min-entropy of $\varDelta _{e+1}$ conditioned on the view of the adversary is at least $m(m-1)-k\cdot m\log q$, which is greater than n by our bounds on k and m.    $\square$

4.4 Overview and Discussion

We provide a compact overview of US schemes obtained from different KH signatures as well as our dedicated BLS-, PS- and GPV-based constructions in Table 1. We present the scheme along with the required hardness assumption, whether it is in the standard model, in the generic group model (GGM) or require random oracles (RO), whether it is unlinkable (UU-CMA), whether it is message-dependent or -independent (MD/MI) and whether it supports an unbounded number of epochs (UB), i.e.,. at least polynomially many in the security parameter, or a concrete bound T on the number of updates.

Table 1. Overview of updatable signature schemes.

As far as efficiency is concerned (counting only expensive operations), and in order to provide some intuition, the BLS construction requires 1 exponentiation for the $\mathsf{Next}$ algorithm, while the $\mathsf{Update}$ algorithm needs 1 hash to group operation and 1 exponentiation. On the other hand, the message-independent BLS from Sect. 4.2 requires 1 exponentiation in the $\mathsf{Next}$ algorithm and only 1 exponentiation in the $\mathsf{Update}$ algorithm. PS requires 2 exponentiations for the $\mathsf{Next}$ algorithm, followed by 3 exponentiations in the $\mathsf{Update}$ algorithm. On the other hand, message-independent PS from Sect. 4.2 requires 3 exponentiations for the $\mathsf{Next}$ algorithm, followed by 3 exponentiations in $\mathsf{Update}$.

5 Construction of Updatable MACs

In this section we present a generic constructions of UMACs from (almost) key-homomorphic PRFs and then present a dedicated construction of a UMAC from the Naor, Pinkas, and Reingold (NPR) PRF [47].

Before we start, we will discuss a well-known approach to turn a PRF $F:\mathcal{K}\times \mathcal{X}\rightarrow \mathcal{Y}$ into a MAC by setting $\sigma \leftarrow \varPi .\mathsf {Sig} (sk,M):=F(sk,M)$ with the canonical verification that recomputes the tag $\sigma$ and compares it to the obtained one. Analogously, a KH-PRF gives a KH-MAC due to the key-homomorphism property and security of the PRF. However, if we use an “almost” KH-PRF, then the canonical verification needs to be replaced with an “approximate” canonical verification (i.e., noisy equality check), where the verification involves a metric function (e.g., Euclidean distance) that gives the distance between input tag and recomputed tag, and verification only succeeds if the distance is smaller than some bound $\delta$.

Clearly, the above discussed approach only yields a fixed-length MAC with message space $\mathcal X$. If the message space is too small, however, we can use a collision-resistant hash function family $(\mathsf {Gen} _H,H)$ with $H:S\times \{0,1\}^* \rightarrow \mathcal{X}$ to obtain a variable-length MAC that supports arbitrary length messages by defining $\varPi '.\mathsf {Sig} (sk,M):=F(sk,H(s,M))$. For that construction we can show the following (cf. [9]):

Lemma 7

If $\varPi$ is a fixed-length EUF-CMA secure MAC for message space $\mathcal X$ and $(\mathsf {Gen} _H,H)$ a collision resistant hash function family, then $\varPi '$ is a variable-length EUF-CMA secure MAC for messages of arbitrary length.

Proof (Sketch)

Let $A$ be the adversary in the experiment $\mathsf {Exp}^{\mathsf {euf}\text {-}\mathsf {cma}}_{\varPi ,A}$ and let $(M_1 ,\ldots ,M_q)$ be the messages queried by $A$ to oracle $\mathsf {Sig} '$ and $(M^*,\sigma ^*)$ be the valid forgery output by the adversary. Now, we have two cases: In the first case i) we have that $H(s,M^*)=H(s,M_i)$ for some $i\in [q]$, which yields a collision pair $(M^*,M_i)$ for H, contradicting collision-resistance of $(\mathsf {Gen} _H,H)$. In the second case ii) we have that $H(s,M^*)\ne H(s,M_i)$ for all $i\in [q]$. However, this means that $(H(s,M^*),\sigma ^*)$ represents a valid tag (signature) for a new message $H(s,M^*)$ and thus a valid forgery for $\varPi$.    $\square$

Subsequently, in our generic construction we consider KH PRFs, which we can equivalently view as KH MACs for fixed-length inputs. We will not make it explicit in our construction, but straightforwardly applying Lemma 7 to our generic construction in Sect. 5.1 will yield UMACs for variable-length inputs.

5.1 UMACs from KH PRFs

Now we show how to obtain UMACs from (almost) KH-PRFs generically. For $\mathcal{K}$ we write $\oplus$ as the group operation and $-k$ as the inverse of k. For the group $\mathcal {Y}$, we use the common addition. The UMAC obtained from a KH-PRF can be seen in Fig. 7, where the text in is only required when using “almost” KH-PRF and $\mathcal {D}_\chi$ represents the error distribution (e.g., error distribution used in lattice-based constructions).

Fig. 7.

Bi-directional UMAC from (almost) KH-PRF. correspond to the changes when using almost KH-PRF.

We can show the following:

Theorem 3

If $F:\mathcal{K}\times \mathcal{X}\rightarrow \mathcal{Y}$ is a secure (almost) key-homomorphic PRF (equivalently an EUF-CMA secure (approximate) MAC for message space $\mathcal X$), then the UMAC construction in Fig. 7 is UMAC-EUF-CMA secure and UMAC-UU-CMA secure.

The proof of UMAC-EUF-CMA security follows exactly the strategy in the proof of Theorem 1 with the only exceptions that within the window we need to simulate the $\mathsf {Ver} '$ oracle, and for the almost KH-PRF we need to account for the additional error terms. For completeness, we provide a sketch of the proof in the full version.

A Note on Almost KH-PRFs. In the notion of almost KH-PRFs such as those from the (R)LWE assumption [14, 15, 39] every homomorphic operations increases the error $\chi$ and thus the constructions are only T-time correct. This means, that UMACs constructed from such KH-PRFs by default will not satisfy the UMAC-UU-CMA notion, while the tags obtained from the $\mathsf {Update}$ algorithm will have higher error compared to fresh tags obtained from the $\mathsf {Sig}$ algorithm, thus making them trivially distinguishable. In order to circumvent this issue, in Fig. 7, we use the trick to make the error depend on the epoch e that we are in. Hence, freshly computed tags and updated ones have the same amount of error, which makes them indistinguishable, and allows us to achieve the UMAC-UU-CMA notion.

Another issue to consider is the effect of the approximate canonical verification on the security of the UMAC. Since we have a noisy equality check during the verification algorithm, we can consider that we have a ball centered around the tag $\sigma$, such that verification accepts any vector within this ball as a valid tag. This implies that an adversary can just change the low-order bits of a valid tag $\sigma$ to produce another valid tag $\sigma '$ that will be within this ball and pass the verification, and hence, break the strong unforgeability. However, since in this work we are only interested in conventional unforgeability of the MAC (i.e., do not require strongly unforgeable MACs), this approach is not useful to a valid adversary against our UMAC. The adversary in our case is required to come up with a valid tag that lies sufficiently far away from any tags that it was provided with. Though, the adversary cannot do this due to the security of the underlying KH-PRF. Nevertheless, the security of the KH-MAC obtained from KH-PRF is correlated with the verification bound. If the verification bound is extremely large, then we have that the balls around the valid tags are overlapping (i.e., the balls are so large that they cover the entire space), and then with high probability any random vector is sufficiently close to a random tag. However, by setting the parameters appropriately we can bound this probability to be negligible. More precisely, when using lattice-based almost KH-PRFs as MACs, for a MAC verification bound $\delta$, modulus q and lattice dimension n, we have that the ball around a valid tag $\sigma$ takes up $(\delta / q)^n$ of the area, where the entire space has area of $q^n$. If the space taken by the ball is negligible, then it is hard for the adversary to forge a valid tag. Since this will depend on the instantiation and parameters of the almost KH-PRF, we leave it as an open problem to setup tighter bounds and compute exact parameters. For our construction in Fig. 7, we can set the verification bound to $\delta = T \cdot B$, for a constant T denoting the maximum number of epochs for our UMAC, and B the bound on the errors sampled from $\mathcal {D}_\chi$.

5.2 Message-Independent UMAC from the NPR PRF

Since UMACs from KH-PRFs are inherently message-dependent, we now present a dedicated construction of a variable-length UMAC scheme that is message-independent (MI) from the PRF due to Naor, Pinkas, and Reingold (NPR) [47]. Let us recall the NPR PRF and therefore let $\mathbb {G}$ be a cyclic group of prime oder p in which the DDH assumption holds and $H:\{0,1\}^*\rightarrow \mathbb {G}$ a hash function modeled as a random oracle, then the NPR PRF with $F:\mathbb {Z} _p^* \times \{0,1\}^*\rightarrow \mathbb {G}$ is defined as $F({k},M):=H(M)^{k}$. It is secure under the DDH assumption in the random oracle model. In contrast to the key-homomorphic variant of the NPR PRF which considers keys from the additive group $\mathbb {Z} _p$, we consider key updates multiplicatively with $\varDelta \in \mathbb {Z} _p^*$, in the vein of the multiplicative variant of the US from the BLS scheme in Sect. 4.2. Note that as in Sect. 4.2 we consider MI to be a feature of UMACs for practical applications where one can assume that one operates on valid UMACs.

To show the security of this construction, we can exactly follow the proof of Theorem 3 with the only exception that we do not use the key-homomorphic property of the PRF in $\mathsf {Update}$, but choose $\varDelta _{e_i + 1}\leftarrow \mathbb {Z} _p^*$ and compute $\sigma =\sigma ^{\varDelta _{e_i + 1}^{-1}}$ or $\sigma =\sigma ^{\varDelta _{e_i + 1}}$ if we have to switch PRF evaluations back (from epoch $e_i+1$ to epoch $e_i$) or forth (from epoch $e_i$ to epoch $e_i+1$). Checking correctness is straightforward and we obtain the following:

Fig. 8.

Bi-directional variable-length UMAC from NPR PRF.

Corollary 2

Let F be the NPR PRF, then the construction in Fig. 5 is an UMAC-EUF-CMA-secure and UMAC-UU-CMA secure UMAC.

5.3 Overview and Discussion

We provide a compact overview of UMACs obtained from different KH-PRFs as well as our dedicated NPR-based construction in Table 2. We use the same criteria for comparison as in Sect. 4.4.

Table 2. Overview of updatable MACs.

Regarding efficiency (again only counting expensive operations), for the key-homomorphic NPR UMAC for instance $\mathsf{Update}$ requires 1 hashing to the group as well as 1 exponentiation and $\mathsf{Next}$ only cheap operations. The variant of the NPR UMAC from Sect. 5.2 requires instead 1 exponentiation for $\mathsf {Update}$ and $\mathsf {Next}$ also only cheap operations.