Paper 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.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- digital signaturesamortized efficiencyflexible verificationpost quantum signaturess
- Contact author(s)
- elena pagnin @ eit lth se
- History
- 2022-04-20: last of 5 revisions
- 2021-06-21: received
- See all versions
- Short URL
- https://ia.cr/2021/832
- License
-
CC BY