International Association
for Cryptologic Research

Identity-based signature ($\textsf{IBS}$) schemes eliminate the need for certificate management, reducing both signature size and verification time. However, the challenge of updating stolen identity-based signature keys (or revoking and re-issueing them) has received limited attention. Existing generic solutions, such as managing revocation lists or periodically renewing user keys, are inefficient and introduce significant networking overhead in dynamic environments. In this work, we address this gap by introducing a symmetric element that enables key updates in $\textsf{IBS}$ schemes via a single multicast message. The network overhead of our solutions scales logarithmic with the number of system users, while computation and memory overhead are constant. Furthermore, we generalize our method by proposing a framework to transform any $\textsf{IBS}$ scheme into a key-updatable signature scheme ($\textsf{KUSS}$), and we define the token security (unforgeability), forward security, and post-compromise security requirements for such transformations. We demonstrate the versatility of our framework by providing five instantiations of $\textsf{KUSS}$ based on Schnorr-type $\textsf{IBS}$, pairing-based $\textsf{IBS}$, and isogeny-based $\textsf{IBS}$. Finally, we analyze the security of these instantiations.