Further Application of Progressive Verification

Abstract

A digital signature is a fundamental cryptographic primitive that provides authenticity and integrity by allowing anyone with a public key to verify that a message was produced by a signer with a corresponding secret key. Such verifications typically produce a binary output only when the process is finished. In contrast, progressive verification (PV) performs verification in smaller incremental steps, gradually building confidence in the signature’s validity over the course of the process. Progressive verification offers several key advantages for post-quantum cryptographic (PQC) schemes on resource constrained devices as it allows for early rejection of invalid inputs and supports adjustable soundness (allowing for a trade-off between security and efficiency). Furthermore, PV can shrink the public key size which addresses a common challenge of PQC schemes. This thesis explores the design and applicability of PV on post-quantum secure digital signature schemes currently involved in the NIST PQC standardisation process. The approach utilises a compiler framework developed by Boschini et al [1] which transforms matrix-vector based (Mv-style) verifications into progressive ones. We explore whether this approach extends to further multivariate quadratic (MQ) schemes as well as to code based schemes. In addition, we investigate whether the compiler can be applied to zero-knowledge proofs, thereby addressing the broader applicability of progressive verification beyond digital signatures. By identifying the matrix-vector structure in the schemes and analysing how the compiler interacts with the verification steps, we assess correctness preservation, security aspects, and practical feasibility. Our findings show that the PV compiler applies cleanly to the MQ-based scheme Unbalanced Oil and Vinegar (UOV), enabling gradual verification without modifying the signing or key-generation algorithms. For code-based schemes, we demonstrate that PV is not applicable to the Codes and Restricted Objects Signature Scheme (CROSS), despite it containing a matrix-vector multiplication in the verification. Progressive verification was also shown to be partially applicable to the verification of a zero-knowledge proof. Overall, this thesis expands the set of post-quantum digital signature schemes known to support progressive verification and highlights design features that make a scheme compatible with PV. These insights can guide both future implementations of PV and the development of new PQC schemes intended for constrained environments.