LMQSAS - post-quantum aggregate signature scheme with lazy verification

Abstract

Aggregated signatures are a type of digital signatures that allow individual signatures obtained by different signers for different messages to be combined into a single signature that provides authenticity, integrity, and non-repudiation for all signed messages. In this case, the length of the resulting aggregated signature is much less than the sum of the lengths of the individual signatures. Sequential aggregated signatures are a subtype of aggregated signatures and allow individual signatures to be combined only during the signing procedure. Signatures of this type can be used in a variety of applications, including secure routing protocols, secure logging, sensor networks, public key infrastructure, blockchain. In this paper we present a new post-quantum aggregated signature scheme with lazy verification that eliminates the need for checking the current sequential aggregated signature during the signature process, which expands its possible application as compared to existing sequential post-quantum signature schemes. The proposed signature scheme is based on post-quantum HFEv- one-way trapdoor permutation, which is known to be resistant to quantum attacks; and Unified Framework of Gentry, O'Neill and Reyzin for obtaining lazy verification using an ideal cipher that can be implemented using the Feistel network and a block cipher. For the presented scheme we provide formal proofs of its security using Bellare-Rogaway game model: the security of the scheme was reduced to the security of a HFEv- one-way trapdoor permutation. We also present a set of parameters for the proposed scheme to meet 80 and 120-bit security levels.

Keywords

• digital signature, post-quantum cryptography, aggregated signatures, sequential aggregated signatures, lazy verification, multivariate cryptography.