Quantum-Safe Identity-Based Signature Scheme in Multivariate Quadratic Setting

Abstract

Cryptographic techniques are essential for the security of communication in modern society. Today, nearly all public key cryptographic schemes used in practice are based on the two problems of factoring large integers and solving discrete logarithms. However, as the world grapples with the possibility of widespread quantum computing, these schemes are the ones most threatened. Multivariate Public Key Cryptography is one of the possible candidates for security in a post-quantum society, especially in the area of digital signature. This thesis uses the setting of multivariate cryptography to propose an identity-based signature scheme. Our proposal is based on the Rainbow signature scheme and the multivariate 3-pass identification scheme, both of which have been subjected to scrutiny by cryptographers all over the world and have emerged as strong post-quantum candidates. In our construction, we use the identity of users to generate their private key using Rainbow signature scheme. Thereafter, we use these user private keys to sign messages by applying Fiat-Shamir transform to the 3-pass identification scheme. We support the proposed scheme with suitable proof under appropriate computational assumptions, using the standard notions of security. We study the known attacks against multivariate schemes in general, and Rainbow and MQDSS in particular. We then use this analysis to propose concrete parameter sets for our construction. We implement our proposed scheme on an x86-64 PC platform and provide timing results. Our implementation shows that our construction is both practical and efficient. Thus our proposed scheme stands as a potential post-quantum multivariate signature candidate in the identity-based setting.