### Updatable Signatures and Message Authentication Codes

Valerio Cini, Sebastian Ramacher, Daniel Slamanig, 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.

Available format(s)
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in Pkc 2021
Keywords
updatable cryptographydigital signaturesmessage authentication codes
Contact author(s)
valerio cini @ ait ac at
sebastian ramacher @ ait ac at
daniel slamanig @ ait ac at
christoph striecks @ ait ac at
erkan tairi @ tuwien ac at
History
Short URL
https://ia.cr/2021/365

CC BY

BibTeX

@misc{cryptoeprint:2021/365,
author = {Valerio Cini and Sebastian Ramacher and Daniel Slamanig and Christoph Striecks and Erkan Tairi},
title = {Updatable Signatures and Message Authentication Codes},
howpublished = {Cryptology ePrint Archive, Paper 2021/365},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/365}},
url = {https://eprint.iacr.org/2021/365}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.