Puncturable Signature: A Generic Construction and Instantiations

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.