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@ait ac at, daniel slamanig@ait ac at, christoph striecks@ait ac at, erkan tairi@tuwien ac at Available format(s): PDF | BibTeX Citation Version: 20210322:192908 (All versions of this report) Short URL: ia.cr/2021/365