Key-Updatable Identity-Based Signature Schemes

Guggemos T., Renan F.

26th International Conference on Cryptology in India, INDOCRYPT 2025, Bhubaneswar, India, 14 - 17 December 2025, vol.16372 LNCS, pp.216-238, (Full Text) identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 16372 LNCS
  • Doi Number: 10.1007/978-3-032-13301-4_10
  • City: Bhubaneswar
  • Country: India
  • Page Numbers: pp.216-238
  • Keywords: ECC, Group Communication, Identity-Based Signatures, Isogeny-based Cryptography, Key Revocation, Pairing-based
  • Middle East Technical University Affiliated: Yes

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 (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.