Quantum secure digital signature scheme based on multivariate quadratic quasigroups (MQQ)

Satish Kumar; Indivar Gupta; Ashok Ji Gupta

doi:10.3934/amc.2024057

Article Contents

2025, Volume 19, Issue 5: 1336-1359. Doi: 10.3934/amc.2024057

This issue Previous Article Three MacWilliams type identities and quantum error-correcting $ G $-codes Next Article A new path to code-based signatures via identification schemes with restricted errors

Quantum secure digital signature scheme based on multivariate quadratic quasigroups (MQQ)

1.
Department of Mathematical Sciences, Indian Institute of Technology (BHU), Varanasi-221005, India
2.
Scientific Analysis Group, Defence Research & Development Organisation, New Delhi-110054, India

^*Corresponding author: Indivar Gupta
^*Corresponding author: Indivar Gupta

Received: April 2024

Revised: August 2024

Early access: December 25, 2024

Published online: December 25, 2024

Abstract / Introduction Full Text(HTML) Figure(2) / Table(4) Related Papers Cited by

Abstract

In this paper, we propose a digital signature scheme, the MQQ-Sigv scheme, that relies on the difficulty of solving the multivariate quadratic (MQ) problem. The central map of the proposed scheme will be designed using the multivariate quadratic quasigroup (MQQ). We will prove that the MQQ-Sigv scheme is secure against various attacks including existential unforgeability under chosen message attack (EUF-CMA), Min-Rank attack, High-Rank attack, Direct attack, and Differential attack. Furthermore, we will prove that finding an equivalent good key for the MQQ-Sigv scheme is infeasible in polynomial time, and analyze the operating characteristics of the scheme.

Keywords:

Non-associative group,
quasigroups,
public-key cryptography,
Multivariate public-key cryptosystem,
multivariate quadratic quasigroup (MQQ).

Mathematics Subject Classification: 20N05, 14G50, 12E20, 94A62.

Citation:

Full Text(HTML)

Figure 1. Pictorial representation of the signature scheme and its verification

Download: Full-size image PowerPoint slide

Figure 2. Pictorial representation of the transformed MQQ-Sigv scheme

Download: Full-size image PowerPoint slide

Table 1. Least number of variables required to resist min-rank and high-rank attack over the finite field $ \mathbb{F}_{2^8} $

Security level $ l(y) $ (in bits)	Number of removed equations ($ r_1 $)	Number of variables to resist min-rank attack	Number of varibles to resist high-rank attack
80	8	264	5
	9	59	5
	10	20	5
96	9	265	6
	10	50	6
	11	17	6
112	10	1635	7
	11	267	7
	12	52	7
128	11	10332	8
	12	1637	8
	15	21	8

| Show Table

DownLoad: CSV

Table 2. Minimal number of equations needed to achieve a given security level

Security level $ l(y) $ (in bits)	Number of equations
Security level $ l(y) $ (in bits)	$ \mathbb{F}_{2^4} $	$ \mathbb{F}_{31} $	$ \mathbb{F}_{2^8} $
80	30	28	26
100	39	36	33
128	51	48	43
192	80	75	68
256	110	103	93

| Show Table

DownLoad: CSV

Table 3. For 128-bit security, the size of the public and private key

Finite field	Security level $ l(y) $ (in bits)	Number of variables (n)	Number of removed equations (r)	Number of vinegar variables (v)	Public key size (in bytes)	Private key size (in bytes) for fixed $ u_1=u_2=10 $
128	128	25	15	8	5206	618
128	128	35	15	10	18917	866
256	128	45	20	15	47275	1147
256	128	45	20	20	102410	1147

| Show Table

DownLoad: CSV

Table 4. Comparative analysis of the MQQ-SIG, Rainbow, and MQQ-Sigv schemes in terms of key size and signature size

Security level $ l(y) $ (in bits)	Algorithm	Number of variables (n)	Number of vinegar variables (v)	Public key size (in bytes)	Private key size (in bytes)	Signature size (in bytes)
80	MQQ-SIG	50	20	137408	401	40
	Rainbow	50	20	30240	23408	42
	MQQ-Sigv	50	20	12780	1156	100
96	MQQ-SIG	70	20	222360	465	48
96	MQQ-Sigv	70	20	32441	1618	140
112	MQQ-SIG	90	30	352828	529	56
112	MQQ-Sigv	90	30	73810	2081	180
128	MQQ-SIG	100	40	526368	593	64
128	MQQ-Sigv	100	40	100110	2312	200

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	C.-O. Chen, M.-S. Chen, J. Ding, F. Werner and B.-Y. Yang, Odd-char multivariate hidden field equations, Cryptology ePrint Archive, 2008.
[2]	M.-S. Chen, A. Hülsing, J. Rijneveld, S. Samardjiska and P. Schwabe, From 5-pass-based identification to-based signatures, Application of Cryptology and Information Security, Springer, 10032 (2016) 135-165.
[3]	W. Chen and Y. Shaoquan, Algorithm for modultion classification of mpsk signals based on cyclic cumulant invariants, Journal of Electronics and Information, 25 (2003), 320-325.
[4]	J. Ding and D. Schmidt, Rainbow, a new multivariable polynomial signature scheme, Applied Cryptography and Network Security, (2005), 164-175. doi: 10.1007/11496137_12.
[5]	J. Ding, D. Schmidt and Z. Yin, Cryptanalysis of the new TTS scheme in CHES 2004, International Journal of Information Security, Springer, 5 (2006), 231–240. doi: 10.1007/s10207-006-0003-9.
[6]	J. Ding and B.-Y. Yang, Multivariate public key cryptography, Post-Quantum Cryptography, Springer Berlin Heidelberg, (2009) 193-241.
[7]	V. Dubois, P. A. Fouque, A. Shamir and J. Stern, Practical cryptanalysis of SFLASH, Advances in Cryptology - CRYPTO 2007, 4622 (2007), 1-12. doi: 10.1007/978-3-540-74143-5_1.
[8]	L. Euler, Commentationes arithmeticae collectae, Typis ac impensis Academiae Imperialis Scientiarum, 2 (1849).
[9]	J.-C. Faugére, D. Gligoroski, L. Perret, S. Samardjiska and E. Thomae, A polynomial-time key-recovery attack on MQQ cryptosystems, IACR International Workshop on Public Key Cryptography, Springer Berlin Heidelberg, 9020 (2015), 150-174. doi: 10.1007/978-3-662-46447-2_7.
[10]	J.-C. Faugére, R. S. Ødegård, L. Perret and D. Gligoroski, Analysis of the MQQ public key cryptosystem, Cryptology and Network Security: 9th International Conference, CANS 2010, Kuala Lumpur, Malaysia, Springer, (2010), 169-183.
[11]	A. Ferozpuri and K. Gaj, High-speed FPGA implementation of the NIST round 1 rainbow signature scheme, 2018 International Conference on ReConFigurable Computing and FPGAs (ReConFig), IEEE, (2018), 1-8.
[12]	A. Fiat and A. Shamir, How to prove yourself: Practical solutions to identification and signature problems, Lecture Notes in Comput. Sci., 263 (1986), 186-194.
[13]	P.-A. Fouque, L. Granboulan and S. Jacques., Differential cryptanalysis for multivariate schemes, Advances in Cryptology—EUROCRYPT, 3494 (2005), 341-353. doi: 10.1007/11426639_20.
[14]	D. Gligoroski, S. Markovski and S. J. Knapskog, Multivariate quadratic trapdoor functions based on multivariate quadratic quasigroups, Proceedings of the American Conference on Applied Mathematics, (2008), 44-49.
[15]	D. Gligoroski, S. Markovski and S. J. Knapskog, A public key block cipher based on multivariate quadratic quasigroups, preprint, arXiv: 0808.0247, 2008.
[16]	D. Gligoroski, R. S. Ødegård, R. E. Jensen, L. Perret, J. C. Faugére, S. J. Knapskog and S. Markovski, MQQ-SIG: An ultra-fast and provably CMA resistant digital signature scheme, International Conference on Trusted Systems, Springer, (2011), 184-203.
[17]	D. Gligoroski and S. Samardjiska, The multivariate probabilistic encryption scheme MQQ-ENC, IACR Cryptology ePrint Archive, 2012.
[18]	S. Goldwasser, S. Micali and R. L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, 17 (1988), 281-308.
[19]	L. Goubin and N. T. Courtois, Cryptanalysis of the TTM cryptosystem, Advances in Cryptology—ASIACRYPT 2000, 1976 (2000), 44-57.
[20]	Y. Hashimoto, On the security of HMFEv, Cryptology ePrint Archive, 2017.
[21]	A. D. Keedwell and J. Dénes, Latin Squares and Their Applications, 2$^{nd}$ edition, Elsevier, 2015.
[22]	A. Kipnis, J. Patarin and L. Goubin, Unbalanced oil and vinegar signature schemes, Advances in Cryptology—EUROCRYPT '99, Springer, 1592 (1999), 206-222. doi: 10.1007/3-540-48910-X_15.
[23]	A. Kipnis and A. Shamir, Cryptanalysis of the oil and vinegar signature scheme, Advances in Cryptology—CRYPTO '98, Springer, 1462 (1998), 257-266. doi: 10.1007/BFb0055733.
[24]	A. Kipnis and A. Shamir, Cryptanalysis of the HFE public key cryptosystem by relinearization, Annual International Cryptology Conference, Springer, 1666 (1999), 19-30. doi: 10.1007/3-540-48405-1_2.
[25]	S. Kumar, I. Gupta and A. J. Gupta, A study of public key cryptosystems based on quasigroups, Cryptologia, 47 (2023), 511-540. doi: 10.1080/01611194.2022.2081824.
[26]	S. Kumar, H. Singh, I. Gupta and A. J. Gupta, MDS codes based on orthogonality of quasigroups, Applicable Algebra in Engineering, Communication and Computing, (2023), 1-22.
[27]	T. Matsumoto and H. Imai, Public quadratic polynomial-tuples for efficient signature-verification and message-encryption, Advances in Cryptology—EUROCRYPT'88, 330 (1988), 419-453.
[28]	S. E. Mohamed, J. Ding and J. Buchmann, Algebraic Cryptanalysis of MQQ Public Key Cryptosystem by MutantXL, IACR Cryptology ePrint Archive, 2008.
[29]	R. A. Mollin and S. Charles, On permutation polynomials over finite fields, International Journal of Mathematics and Mathematical Sciences, Hindawi 10 (1987), 535-543. doi: 10.1155/S0161171287000644.
[30]	R. Moufang, Zur struktur von alternativkörpern, Mathematische Annalen, Springer, 110 (1935), 416-430. doi: 10.1007/BF01448037.
[31]	R. Ødegård, L. Perret, J. C. Faugére and D. Gligoroski, Analysis of the MQQ public key cryptosystem, Conference on Symbolic Computation and Cryptography, 2010.
[32]	J. Patarin, Cryptanalysis of the matsumoto and imai public key scheme of eurocrypt'98, Designs, Codes and Cryptography, 20 (2000), 175-209. doi: 10.1023/A:1008341625464.
[33]	J. Patarin, Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt'88, Advances in Cryptology—CRYPT0'95, 963 (1995), 248-261.
[34]	J. Patarin, The Oil and Vinegar Signature Scheme, Presented at the Dagstuhl Workshop on Cryptography September, 1997.
[35]	J. Patarin, Hidden fields equations (HFE) and isomorphisms of polynomials (IP): Two new families of asymmetric algorithms, International Conference on the Theory and Applications of Cryptographic Techniques, Springer, (1996) 33-48.
[36]	J. Patarin, N. Courtois and L. Goubin, Flash, a fast multivariate signature algorithm, Topics in Cryptology — CT-RSA 2001: The Cryptographers' Track at RSA Conference 2001 San Francisco, C A, 2020 (2001), 298-307.
[37]	J. Patarin, N. Courtois and L. Goubin, QUARTZ, 128-bit long digital signatures,, Topics in Cryptology-CT-RSA 2001, Springer, (2001), 282-297. doi: 10.1007/3-540-45353-9_21.
[38]	A. Petzoldt, Selecting and reducing key sizes for multivariate cryptography, PhD Thesis, Darmstadt Tuprints, 2013.
[39]	A. Petzoldt, S. Bulygin and J. Buchmann, CyclicRainbow – a multivariate signature scheme with a partially cyclic public key, Progress in Cryptology-INDOCRYPT 2010, 6498 (2010), 33-48.
[40]	A. Petzoldt, M.-S. Chen, J. Ding and B.-Y. Yang, HMFEv - an efficient multivariate signature scheme, Post-Quantum Cryptography, 10346 (2017), 205-223.
[41]	A. Petzoldt, M. S. Chen, B. Y. Yang, C. Tao and J. Ding, Design principles for HFEv-based multivariate signature schemes, Advances in Cryptology-ASIACRYPT 2015 Springer, 9452 (2015), 311-334.
[42]	K. Sakumoto, T. Shirai and H. Hiwatari, Public-key identification schemes based on multivariate quadratic polynomials, Advances in Cryptology-CRYPTO 2011, Springer, 6841 (2011), 706-723.
[43]	S. Samardjiska, Y. Chen and D. Gligoroski, Algorithms for construction of Multivariate Quadratic Quasigroups (MQQs) and their parastrophe operations in arbitrary Galois fields, Journal of Information Assurance and Security, 7 (2012).
[44]	S. Samardjiska, S. Markovski and D. Gligoroski, Multivariate quasigroups defined by t-functions, Conference on Symbolic Computation and Cryptography, (2010), 117.
[45]	V. Shcherbacov, Elements of Quasigroup Theory and Applications, CRC Press, Boca Raton, FL, 2017.
[46]	P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Review, 41 (1999), 303-332.
[47]	E. Thomae, About the security of multivariate quadratic public key schemes, PhD Thesis, Ruhr-Universit$\ddot{a}$t Bochum, Universit$\ddot{a}$tsbibliothek, 2013.
[48]	E. Thomae and C. Wolf, Cryptanalysis of enhanced TTS, STS and all its variants, or: Why cross-terms are important, Progress in Cryptology-AFRICACRYPT 2012, Springer, 7374 (2012), 188-202.
[49]	X. Wang and B. Yang, An improved signature model of multivariate polynomial public key cryptosystem against key recovery attack, Mathematical Biosciences and Engineering, 16 (2019), 7734-7750.
[50]	C. Wolf and B. Preneel, Taxonomy of Public Key Schemes Based on the Problem of Multivariate Quadratic Equations, IACR Cryptology ePrint Archive, 2005.
[51]	B.-Y. Yang and J.-M. Chen, Building secure tame-like multivariate public-key cryptosystems: The new TTS, Australasian Conference on Information Security and Privacy, Springer, (2005), 518-531.