Local verifiability in aggregate and multi-signature schemes: from pairing-based constructions to post-quantum lattice assumptions

Date

2026-8

Author

Yaman Gökce, Neslihan

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

107
views

0
downloads

Cite This

Digital signature schemes are indispensable cryptographic primitives for ensuring au- thenticity, integrity, and non-repudiation in modern communication systems. Aggre- gate signatures and multi-signatures improve the efficiency of digital signatures by reducing communication, storage, and verification costs in distributed environments such as blockchain, cloud computing, and the Internet of Things. However, exist- ing verification algorithms require processing all signed messages or all participating signers, which causes the verification cost to grow linearly with the size of the system. In order to overcome this limitation, the notion of local verifiability was introduced, enabling a verifier to efficiently verify the inclusion of a particular message in an ag- gregate signature through a compact auxiliary value without requiring access to the complete message set. Although this concept opened up a new research direction, it remained largely restricted to message-oriented verification and classical crypto- graphic constructions. This thesis investigates local verifiability in aggregate and multi-signature schemes and presents a series of constructions that progressively extend its applicability from pairing-based settings to post-quantum lattice-based cryptography. First, a locally verifiable aggregate signature construction is proposed that supports the simultane- ous verification of multiple selected messages, allowing a verifier to validate multiple messages using a single auxiliary opening while preserving compact aggregate signatures and provable security. Subsequently, the concept of local verifiability is transferred from the message domain to the signer domain through the design of lo- cally verifiable multi-signature schemes, enabling efficient verification of the partic- ipation of individual signers without requiring verification over the complete signer set. The proposed techniques are then extended to a locally verifiable aggregated multi-signature scheme supporting dynamic signer participation, allowing different subsets of signers to jointly authorize multiple messages while preserving efficient aggregation and local verification. All three pairing-based constructions are proven unforgeable in the random oracle model: the first under Diffie–Hellman inversion assumptions, and the two multi-signature constructions under the computational co- Diffie–Hellman assumption with respect to honestly generated openings. Motivated by the transition toward post-quantum cryptography, this thesis extends local verifi- ability to lattice-based assumptions and presents L-LVMS, the first locally verifiable multi-signature scheme built on standard lattice hardness. The construction augments the two-round lattice-based multi-signature scheme MS2 with a deterministic local opening mechanism that allows efficient verification of an individual signer’s par- ticipation. The original key generation algorithm, the signature algorithm, and the signature size remain unchanged. L-LVMS is proven existentially unforgeable under chosen-message attacks in the random oracle model, assuming honestly generated local openings, under the MSIS and MLWE assumptions together with the security of an underlying trapdoor homomorphic commitment scheme. The thesis further ex- amines the case of adversarially generated local openings and shows that this setting introduces fundamental limitations, motivating post-quantum succinct arguments as a direction for future work. Overall, this thesis presents a systematic progression of locally verifiable signature schemes. The concept is first developed for message-domain verification in clas- sical pairing-based constructions, then extended to signer-domain verification, and finally established under post-quantum lattice assumptions. The proposed construc- tions broaden the applicability of local verification, improve the efficiency and scala- bility of distributed signature systems. They also provide rigorous security guarantees under well-established cryptographic assumptions. In doing so, this thesis contributes to the development of practical and scalable locally verifiable signature schemes for both classical and post-quantum cryptographic settings.

Subject Keywords

Aggregate signatures, Multi-signatures, Local verification, Locally verifiable signatures, Lattice-based signature schemes

URI

https://hdl.handle.net/11511/120715

Collections

Graduate School of Applied Mathematics, Thesis