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 onmultivariate 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, andcomputation time. We define an efficiency metric by using impersonation probability and computation time. Accordingto the comparison results, the proposed one has the same computation time as that of Monteiro et al. and reducesimpersonation probability compared to the work of Sakumoto et al. We also propose a new signature scheme constructedfrom the proposed identification scheme. In addition, we compare the signature scheme with the previous schemes inview of signature and key sizes. We improve the signature size compared to that given in previous work by Chen et al.