SoK: Signatures With Randomization Features

As modern cryptography advances, digital signatures with versatility are developed to accommodate various requirements of specific applications. This renders them particularly interesting for more complex privacy-preserving protocol designs, including anonymous credentials and group signatures. Significant effort has been devoted to the study of different powerful variants of digital signatures that allow controlled transformations of message-signature pairs without destroying the validity of signatures. In this paper, we provide an extensive survey of the state-of-the-art constructions of signatures with randomization features in key-message-signature-triples. We categorize existing relevant signatures into two major types: with unchanged keys and with randomizable keys, and revisit contributions in terms of security notions and efficiency. Furthermore, we suggest open questions and challenges for future research on signatures with randomization features.