Cryptology ePrint Archive: Report 2021/365

Updatable Signatures and Message Authentication Codes

Valerio Cini and Sebastian Ramacher and Daniel Slamanig and Christoph Striecks and Erkan Tairi

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; Klooss 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.

Category / Keywords: public-key cryptography / updatable cryptography, digital signatures, message authentication codes

Original Publication (with major differences): IACR-PKC-2021

Date: received 18 Mar 2021

Contact author: valerio cini at ait ac at, sebastian ramacher at ait ac at, daniel slamanig at ait ac at, christoph striecks at ait ac at, erkan tairi at tuwien ac at

Available format(s): PDF | BibTeX Citation

Version: 20210322:192908 (All versions of this report)

Short URL: ia.cr/2021/365