Paper 2025/715

Updatable Signature with Public Tokens

Abstract

The Updatable Signature (US) allows valid signatures to be updated by an update token without accessing the newly generated signing key. Cini et al. (PKC'21) formally defined this signature and gave several constructions. However, their security model requires the secrecy of the update token, which is only applicable in some specific scenarios, such as software verification in the trusted App Store. In Web3, information is usually shared via a public blockchain, and decentralized private computation is expensive. In addition, one can use the same token to update both the signing key and signatures and all signatures can be updated with a single token. The adversarial signature generated by an adversary might also be updated. Therefore, this work explores the (im)possibility of constructing an Updatable Signature with public tokens (USpt), the tokens of which are signature-dependent. Specifically, we define the updatable signature with public tokens and present its security model. Then, we present a concrete USpt scheme based on the Boneh–Lynn–Shacham signature. This variant introduces a limitation for the signer who must maintain a dataset about its signed messages or hashes of them, which is applicable in our applications.