Welcome to the resource topic for 2025/2014
Title:
Multi-Splitting Forking Based Modular Security of Signatures in Multivariate Quadratic Setting
Authors: Sanjit Chatterjee, Tapas Pandit, Subhabrata Samajder
Abstract:This paper proposes modular security proofs for some identification scheme (IDS)-based signature schemes in the multivariate quadratic (MQ) setting. More precisely, our contributions include concrete security reduction for both 3-pass and 5-pass MQDSS signature schemes in the random oracle model. Although no formal security argument for the former was available in the literature, the one for the latter provides only a qualitative treatment. Our concrete analysis shows that the 3-pass scheme enjoys a comparatively tighter reduction. This result, considered in conjunction with a reported attack on the 5-pass MQDSS from the NIST PQC competition, thus indicates that contrary to the initial suggestion, the 3-pass MQDSS could be a better choice at a concrete security level. Our next focus is on the only blind signature scheme available in the MQ-setting, proposed by Petzoldt et al. While the security of the original scheme was discussed in a non-standard and significantly weak model; we propose a concrete security reduction for a slightly modified scheme in the standard one-more unforgeability (OMF) model.
Central to all our modular proofs are new forking algorithms. The forking algorithm/lemma has been widely used in the formal security reduction of numerous cryptographic schemes, mainly in the discrete logarithm and RSA setting. The abstractions proposed here allow multiple forkings at the same index while satisfying certain additional conditions for the underlying IDS in the MQ-setting. Thus, the forking algorithms capture the nuances of the MQ-setting while being agnostic of the underlying structure.
ePrint: https://eprint.iacr.org/2025/2014
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .