Puncturable Signature: A Generic Construction and Instantiations

Publication Name

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)


Puncturable signature (PS), proposed by Bellare, Stepanovs and Waters at EUROCRYPT 2016, is a special kind of digital signature that supports a fine-grained revocation of signing capacity by updating the secret key with selective messages. Puncturable signature has many usages like asynchronous transaction data signing services and proof-of-stake blockchain protocols. Meanwhile, it is an essential building block in constructing disappearing signatures in the bounded storage model. In this paper, we propose the first generic construction of puncturable signature from identity-based signature by treating identities as prefixes. With the help of our generic framework, we present different puncturable signature instantiations over lattices, bilinear maps, and multivariate public key cryptography (MPKC). Specifically, the lattice-based instantiation is based on the short integer solution (SIS) assumption and is proven secure in the random oracle model. Besides, the pairing-based instantiation is based on the computational Diffie-Hellman (CDH) assumption and is proven secure in the standard model. In addition, we show that the instantiation over MPKC is secure under current attacks.

Open Access Status

This publication is not available as open access


13555 LNCS

First Page


Last Page


Funding Number


Funding Sponsor

Australian Research Council



Link to publisher version (DOI)