MQ-based signature scheme

Abstract

One approach to constructing a signature scheme is to begin by designing a zero-knowledge identification scheme, which can then be transformed into a non-interactive signature scheme using methods such as the Fiat-Shamir transformation. Beullens [Beu19] introduced a sigma protocol for knowledge of solutions to MQ-problems, achieving a soundness error is significantly smaller compared to existing proofs. Beullens further claimed that his sigma protocol can be converted into a signature scheme by applying the generic Fiat-Shamir transformation, and he proved its unforgeability in the Quantum Random Oracle Model by a result of [DFMS19]. He also briefly discussed employing binary trees to minimize signature size and the application of the parallel repetition technique from [KKW18] to further mitigate the soundness error. However, the paper does not provide a detailed construction of a signature scheme, with or without these optimizations. In this paper, we present a concrete construction of a basic signature scheme based on Beullens’ sigma protocol. We also offer a detailed explanation of the construction and integration of seed trees and hash Merkle trees into the scheme. Additionally, we clearly explain the use of the beating parallel repetition technique in the optimized version of the basic signature scheme.