Prefix Puncturable Signatures with Smaller Signing Key from HIBS

Puncturable signatures, introduced by Bellare et al. at 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.

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^{\text{Punc}}$.

This paper addresses the key-size problem by presenting a gener

The main result is a generic construction of prefix puncturable signatures from HIBS with significantly reduced signing key size. Specifically, for prefix space $\{0,1{\}}^l$, the punctured signing key size is bounded by $O(l{Q}^{\text{Punc}})$, where $Q^{\text{Punc}}$ is the number of puncturing operations.

This improves upon prior constructions:

- The IBS-based construction (ESORICS 2022) requires a signing key of size $2^l$ IBS signing keys, which is exponential in the prefix length.
- The delegated constrained signature construction (IEEE Trans. Inf. Forensics Secure. 2024), when instantiated with a lattice-based scheme, yields a punctured signing key whose size grows quadratically with $Q^{\text{Punc}}$, i.e., $O((Q^{\text{Punc}}{)}^2)$.

In contrast, the proposed HIBS-based construction achieves linear growth in both $l$ and $Q^{\text{Punc}}$. When instantiated with HIBS${}^{\text{GPV}}$, the scheme remains secure under standard lattice assumptions and is post-quantum secure.

The paper provides a formal security proof showing that the constructed prefix puncturable signature scheme is existentially unforgeable under chosen-message attacks (EUF-CMA) if the underlying HIBS schem