You are looking at a specific version 20210918:081140 of this paper. See the latest version.

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)
PDF
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.