Paper 2026/1796

UdMAC: Efficiently Updatable Message Authentication Codes

Abstract

Message authentication codes (MAC) are ubiquitous and are considered to be the most important tool employed to ensure authenticity of messages in the symmetric key setting. In this work, we aim to empower MACs with a newly added functionality of updatablility, i.e., the goal is to construct a MAC scheme where the authentication tag for a message can be updated with every update to the message without recomputing the tag for the entire message. Such a functionality can be useful in several scenarios, primarily where the storage of a frequently changing large message is delegated to an un-trusted server. In such a scenario it may be infeasible for an user to download the entire message and recompute the tag for every update. Bellare et al. [CRYPTO'94, STOC'95] introduced a new class of history-free updatable MACs, which can update a message tag without requiring any previous information. However, their update algorithm takes the entire document as an input, which can be impractical in many real-world scenarios. We introduce a new class of MACs called updatable message authentication codes (UdMACs). An UdMAC allows an existing message tag to be updated using only the previous tag, the message update, and a small state, without accessing the previous message. We systematically develop UdMACs, provide syntax for UdMAC, propose formal security notion. We then present two constructions: $\concatu$ and $\xoru$, which support two distinct message updates, namely, concatenation and xor difference. We analyze both the constructions in details and prove security of the construction in the newly proposed security model.

Note: A few typos and errors fixed in this version.