View all Seminars  |  Download ICal for this event

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

Series: M.Tech (Research) Colloquium - ON-LINE

Speaker: Ms. Aalo Majumdar M.Tech (Research) student Dept. of CSA

Date/Time: Sep 16 16:00:00

Location: Microsoft teams - ONLINE

Faculty Advisor: Prof. Sanjit Chatterjee

Current ubiquitous cryptosystems face an imminent threat from quantum algorithms like Shors and Grovers, leading us to a future of 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. The construction of this 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 version of 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 an improved security argument of MBSS in the UOMF security model using the PR-mSTI assumption. 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. With the high cost of forking, a significant degradation factor appears 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 argument in the UOMF and OMF models.

Microsoft Teams link:

Speaker Bio:

Host Faculty: