Fast Updatable Message Authentication Codes and Signatures with Public Tokens

Updatable message authentication codes (UMAC) and updatable signatures (US) schemes introduced by Cini et al. (PKC 2021) enable the rotation of authenticated data to new secret keys, without requiring either the download of the authentication data or the full recomputation of tags or signatures. Instead, the original signer passes along a short token to update the authentication data. The token was originally supposed to be kept secret by the updating party. Later, Yin et al. (JISA 2025) discussed applications that require public update tokens, e.g., when tokens are published on blockchains. Besides the additional trust in the transforming party to keep the token secret, embedded in most private-key solutions so far, all prior work used public-key operations for the update step. This leaves open the question of whether one can build UMACs based on symmetric-key primitives, ideally with public tokens. We answer this in the affirmative, showing that one can construct such UMACs that achieve the strong security notions of existential unforgeability under chosen-message attacks (UX-EUF-CMA) and unlinkability of updates under chosen-message attacks (UX-UU-CMA), both for public tokens. As part of this, we also identify a flaw in the unforgeability definition of Yin et al. (JISA 2025), rendering their notion unachievable. In our construction, the update mechanism is message-dependent, i.e., it relies on some (short) information about the authenticated message. This provides additional security guarantees, as public tokens can only be used to update specific authentication data. Our solution can be instantiated smoothly with HMAC, for example, and can be extended to updatable signatures in the hash-and-sign format. Unlike prior approaches, our constructions support direct updates to arbitrary future epochs, potentially skipping intermediate epochs, enabling flexible deployment in distributed and outsourced scenarios.