A novel 3-pass identification scheme and signature scheme based on multivariate quadratic polynomials

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.

PDF

___

[1] Abdalla M, An JH, Bellare M and Namprempre C. From identification to signatures via the Fiat-Shamir transform: minimizing assumptions for security and forward-security. Lect Notes Comp Sci 2002; 2332: 418-433.
[2] Bernstein DJ. Buchmann J, Dahmen E. Post-Quantum Cryptography. Berlin, Germany: Springer, 2009.
[3] Chen MS, Hülsing A, Rijneveld J, Samardjiska S, Schwabe P. From 5-pass MQ-based identification to MQ-based signatures. In: International Conference on the Theory and Application of Cryptology and Information Security - ASIACRYPT 2016; 4–8 December 2016; Hanoi, Vietnam. Berlin, Germany: Springer, 2016. pp. 135-165.
[4] Chen MS, Hülsing A, Rijneveld J, Samardjiska S, Schwabe, P. MQDSS specifications version 1.1. In: NIST’s First PQC Standardization Conference; 2018.
[5] Dagdelen O, Galindo D, Veron P, El Yousfi Alaoui SM, Cayrel PL. Extended security arguments for signature schemes. Design Code Cryptogr 2016; 78: 441-461.
[6] Feige U, Fiat A, Shamir A. Zero-knowledge proofs of identity. J Cryptol 1988; 1: 77–94.
[7] Fiat A, Shamir A. How to prove yourself: practical solutions to identification and signature problems. In: Advances in Cryptology — CRYPTO’86; 1987. pp. 186-194.
[8] Hornschuch M. Multivariate-based identification and signature schemes with additional properties. MSc, Technische Universitat Darmstadt, Germany, 2012.
[9] Monteiro FS, Goya DH, Terada R. Improved identification protocol based on the MQ problem. IEICE T Fund Electr 2015; E98-A: 1255-1265.
[10] Okamoto T. Provably secure and practical identification schemes and corresponding signature schemes. Lect Notes Comp Sci 1992; 740: 31-53.
[11] Sakumoto K. Public-key identification schemes based on multivariate cubic polynomials. Lect Notes Comp Sci 2012; 7293: 172-189.
[12] Sakumoto K, Shirai T, Hiwatari H. Public-key identification schemes based on multivariate quadratic polynomials. Lect Notes Comp Sci 2011; 6841: 706-723.
[13] Shor PW. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J Comput 1997; 26: 1484-1509.
[14] Simari GI. A Primer on Zero Knowledge Protocols. Technical Report. Buenos Aires, Argentina: Universidad Nacional del Sur, 2002.