Paper 2025/1094

Key-Updatable Identity-Based Signature Schemes

Abstract

Identity-based signature (IBS) schemes eliminate the need for certificate management, thereby reducing communication and computational overhead. A major challenge, however, is the efficient update or revocation of compromised keys, as existing approaches such as revocation lists or periodic key renewal incur significant network costs in dynamic settings. We address this challenge by introducing a symmetric element that enables key updates in IBS schemes through a single multicast message. Our approach achieves logarithmic network overhead in the number of keys, with constant computation and memory costs. We further propose a general framework that transforms any IBS scheme into a key-updatable IBS scheme ($\mathsf{KUSS}$), and formalize the associated security requirements, including token security, forward security, and post-compromise security. The versatility of our framework is demonstrated through five instantiations based on Schnorr-type, pairing-based, and isogeny-based IBS, and we provide a detailed security analysis.