A Novel 3-Pass Identification Scheme and Signature Scheme Based on Multivariate Quadratic Polynomials

Abstract

Identification schemes are used to verify identities of parties and signatures. Recently, systems based on multivariate polynomials have been preferred in identification schemes due to their resistance against quantum attacks. In this paper, we propose a quantum secure 3-pass identification scheme based on multivariate quadratic polynomials. We compare the proposed scheme with the previous ones in view of memory requirements, communication length, and computation time. We define an efficiency metric by using impersonation probability and computation time. According to the comparison results, the proposed one has the same computation time as that of Monteiro et al. and reduces impersonation probability compared to the work of Sakumoto et al. We also propose a new signature scheme constructed from the proposed identification scheme. In addition, we compare the signature scheme with the previous schemes in view of signature and key sizes. We improve the signature size compared to that given in previous work by Chen et al. © TÜBI˙TAK.