Paper 2023/1524

SoK: Signatures With Randomizable Keys

Sofía Celi, Brave Software
Scott Griffy, Brown University
Lucjan Hanzlik, CISPA Helmholtz Center for Information Security
Octavio Perez Kempner, NTT Social Informatics Laboratories
Daniel Slamanig, AIT Austrian Institute of Technology

Digital signature schemes with specific properties have recently seen various real-world applications with a strong emphasis on privacy-enhancing technologies. They have been extensively used to develop anonymous credentials schemes and to achieve an even more comprehensive range of functionalities in the decentralized web. Substantial work has been done to formalize different types of signatures where an allowable set of transformations can be applied to message-signature pairs to obtain new related pairs. Most of the previous work focused on transformations with respect to the message being signed, but little has been done to study what happens when transformations apply to the signing keys. A first attempt to thoroughly formalize such aspects was carried by Derler and Slamanig (ePrint '16, Designs, Codes and Cryptography '19), followed by the more recent efforts by Backes et. al (ASIACRYPT '18) and Eaton et. al (ePrint '23). However, the literature on the topic is vast and different terminology is used across contributions, which makes it difficult to compare related works and understand the range of applications covered by a given construction. In this work, we present a unified view of signatures with randomizable keys and revisit their security properties. We focus on state-of-the-art constructions and related applications, identifying existing challenges. Our systematization allows us to highlight gaps, open questions and directions for future research on signatures with randomizable keys.

Available format(s)
Public-key cryptography
Publication info
Digital signatureskey blindingkey randomization
Contact author(s)
cherenkov @ riseup net
scott_griffy @ brown edu
hanzlik @ cispa de
octavio perezkempner @ ntt com
daniel slamanig @ ait ac at
2023-10-09: approved
2023-10-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sofía Celi and Scott Griffy and Lucjan Hanzlik and Octavio Perez Kempner and Daniel Slamanig},
      title = {SoK: Signatures With Randomizable Keys},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1524},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.