Security of Post-Quantum Multivariate Blind Signature Scheme: Revisited and Improved

Abstract

Current cryptosystems face an imminent threat from quantum algorithms like Shor's and Grover's, leading us to post-quantum cryptography. Multivariate signatures are prominent in post-quantum cryptography due to their fast, low-cost implementations and shorter signatures. Blind signatures are a special category of digital signatures with two security notions: blindness and one-more unforgeability (OMF). Our work primarily focuses on the multivariate blind signature scheme (MBSS) proposed by Petzoldt et al. We construct a formal proof along the lines of the heuristic sketch given by the authors of MBSS based on the proposed universal one-more unforgeability (UOMF) model, a weaker variant of OMF. Proper reconstruction of their proof led us to identify the various issues in the security argument - mainly the difficulty in simulating the response to the blind signature queries without knowing the secret key of the underlying Rainbow scheme used. Since our investigation revealed the difficulty in reducing the UOMF security to the hardness assumption used by the authors, therefore we design a new class of hardness assumptions: (1) Single Target Inversion Problem, PR-STI (2) Modified Single Target Inversion Problem, PR-mSTI (3) Chosen Target Inversion Problem, PR-CTI. Armed with the new class of computational problems, we reduce the UOMF and OMF security of MBSS to these problems. We begin by giving a security argument of MBSS in the UOMF security model using the PR-mSTI assumption, which is assumed to be quantum-safe. We employ the general forking algorithm in this security reduction. However, we cannot apply the forking algorithm directly owing to the wrapper algorithm being split and the presence of the blind signature oracle. We thus suitably modify the algorithm and then derive the corresponding forking probability. To argue the security of MBSS in the standard security model, i.e., in the OMF model, we try using the PR-CTI assumption. The PR-CTI problem demands computing the solution for more than one target. Computing the solution for more than one target entails using the forking process more than once. Since forking causes a high degradation in the success probability, this leads to a significant degradation factor in the success probability. So, instead, we reduce the OMF security of MBSS to the PR-mSTI assumption (in a restricted setting) and give a comparative analysis between the security arguments in the UOMF and OMF models.