Paper 2021/832
On the Efficiency and Flexibility of Signature Verification
Cecilia Boschini and Dario Fiore and Elena Pagnin
Abstract
Digital signatures are a well-established mean to securely certify data integrity and authenticate sources. One core component of digital signature schemes is signature verification. Traditionally, verification is monolithic and returns a decision (accept/reject) only at the very end of the process. In this work, we pose two questions that dismantle this monolithic view on signature verification: (1) is it possible to extract meaningful information from a partial verification? (flexibility); and (2) is it possible to split the verification process into a computational heavy, one-time set-up, and a lightweight, reusable part, without undermining unforgeability? (efficiency). We answer both questions in a positive way for specific classes of schemes that include post-quantum secure signatures from lattices and from multivariate polynomials. 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, rather than requiring a re-design. For each framework, we exhibit generic transformations to realize efficient (and/or) flexible verification for signature schemes that involve a matrix-vector multiplication among the checks. Our transformations apply to the NIST finalist Rainbow; MP12 (EUROCRYPT); GVW15 (STOC); and Lyub12 (EUROCRYPT) when implemented with non-cryptographic hash functions as suggested by Chen et al. (CRYPTO21), among other schemes.
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,dario fiore @ imdea org,cecilia boschini @ usi ch
- 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