Prefix Puncturable Signatures with Smaller Signing Key from HIBS

Abstract

Puncturable signatures, proposed by Bellare et al. (EUROCRYPT 2016), allow a signing key to be punctured (updated) so that it loses the ability to sign particular messages while retaining the ability to sign all others. Halevi et al. (ASIACRYPT 2017) introduced prefix puncturable signatures, in which the signing key can be punctured with respect to a target prefix so that it cannot sign messages whose prefixes match the target prefix. So far, several generic constructions of prefix puncturable signature schemes have been proposed, including constructions based on identity-based signatures (IBS) (ESORICS 2022) and delegated constrained signatures (IEEE Trans. Inf. Forensics Secure. 2024). However, these constructions suffer from drawbacks in terms of key size. When the prefix space is the set of all l-bit strings, the former construction requires a signing key consisting of 2^{l} IBS signing keys. The latter construction, when instantiated with a lattice-based delegated constrained signature scheme, yields a punctured signing key whose size grows quadratically with the number of puncturing operations Q^{Punc}. In this paper, we present a generic construction of prefix puncturable signatures from hierarchical identity-based signature (HIBS) schemes. When the prefix space is {0,1}^{l} and our construction is instantiated with the lattice-based HIBS scheme HIBS^{GPV} by Ruckert (PQC 2010), our construction achieves a punctured signing key size bounded by O(lQ^{Punc}).