Cryptology ePrint Archive: Report 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.

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

Date: received 18 Jun 2021, last revised 18 Sep 2021

Contact author: elena pagnin at eit lth se, dario fiore at imdea org, cecilia boschini at usi ch

Available format(s): PDF | BibTeX Citation

Version: 20210918:081140 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]