International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Updatable Signatures and Message Authentication Codes

Authors:
Valerio Cini
Sebastian Ramacher
Daniel Slamanig
Christoph Striecks
Erkan Tairi
Download:
Search ePrint
Search Google
Presentation: Slides
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; KlooƟ 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.
Video from PKC 2021
BibTeX
@article{pkc-2021-30992,
  title={Updatable Signatures and Message Authentication Codes},
  booktitle={Public-Key Cryptography - PKC 2021},
  publisher={Springer},
  author={Valerio Cini and Sebastian Ramacher and Daniel Slamanig and Christoph Striecks and Erkan Tairi},
  year=2021
}