Cryptology ePrint Archive: Report 2021/832

On the Efficiency and Flexibility of Signature Verification

Cecilia Boschini and Dario Fiore and Elena Pagnin

Abstract: For decades signature verification has been regarded as a unique, monolithic process. Here, we want to look at it with fresh eyes and pose two fundamental questions: (1) is it possible to extract meaningful information from a partial signature verification? (flexibility); and (2) is it possible to speed up the verification process without impacting unforgeability? (efficiency). We answer both questions in a positive way for specific classes of post-quantum secure schemes.

In detail, we develop formal frameworks for signatures with efficient verification, flexible verification and combinations of the two. Crucially, we regard these as features that may enhance existing constructions. Flexibility is of particular interest as standard verification cannot provide any meaningful information about the validity of a given signature if interrupted in media res. We exhibit generic transformations to realize efficient (and) flexible verification for schemes that involve matrix-vector multiplications among the verification checks. In addition, we present concrete instantiations of efficient (and) flexible verification for Rainbow [ACNS05] (as representative of schemes based on multivariate quadratic equations), MP [EC12] and GVW [STOC15] (as representative of lattice-based constructions). Interestingly, we are able to efficiently verify Rainbow signatures using 50% of the original computational cost, and as little as 0.4% for GVW homomorphic signatures, provided a one-time preprocessing and with only negligible impact on security.

Category / Keywords: public-key cryptography / digital signatures, amortized efficiency, flexible verification, post quantum signaturess

Date: received 18 Jun 2021

Contact author: elena pagnin at eit lth se

Available format(s): PDF | BibTeX Citation

Version: 20210621:075304 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]