×

Efficient public-key operation in multivariate schemes. (English) Zbl 1412.94158

Summary: The public-key operation in multivariate encryption and signature schemes evaluates \(m\) quadratic polynomials in \(n\) variables. In this paper we analyze how fast this simple operation can be made. We optimize it for different finite fields on modern architectures. We provide an objective and inherent efficiency measure of our implementations, by comparing their performance with the peak performance of the CPU. In order to provide a fair comparison for different parameter sets, we also analyze the expected security based on the algebraic attack taking into consideration the hybrid approach. We compare the attack’s efficiency for different finite fields and establish trends. We detail the role that the field equations play in the attack. We then provide a broad picture of efficiency of MQ-public-key operation against security.

MSC:

94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)

Software:

Magma; ZHFE; FLASH
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] C. Berbain, O. Billet and H. Gilbert, Efficient implementations of multivariate quadratic systems, in Selected Areas in Cryptography (eds. E. Biham and A. Youssef), vol. 4356 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2007,174-187. · Zbl 1161.94385
[2] D. J. Bernstein, J. Buchmann and E. Dahmen, Post-Quantum Cryptography, Springer-Verlag, Berlin, 2009. · Zbl 1155.81007
[3] L. Bettale, J.-C. Faugère and L. Perret, Cryptanalysis of the TRMS Signature Scheme of PKC’05, Progress in cryptology - AFRICACRYPT 2008, Springer Berlin Heidelberg, Berlin, Heidelberg, 2008,143-155. · Zbl 1142.94333
[4] L. Bettale; J.-C. Faugere; L. Perret, Hybrid approach for solving multivariate systems over finite fields, Journal of Mathematical Cryptology, 3, 177-197 (2009) · Zbl 1183.94021 · doi:10.1515/JMC.2009.009
[5] L. Bettale, J.-C. Faugère and L. Perret, Solving polynomial systems over finite fields: Improved analysis of the hybrid approach, in ISSAC 2012 - 37th International Symposium on Symbolic and Algebraic Computation, ACM, Grenoble, France, 2012, 67-74. · Zbl 1323.68583
[6] L. Bettale; J.-C. Faugère; L. Perret, Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic, Designs, Codes and Cryptography, 69, 1-52 (2013) · Zbl 1307.13031 · doi:10.1007/s10623-012-9617-2
[7] W. Bosma; J. Cannon; C. Playoust, The Magma algebra system. Ⅰ. The user language, J. Symbolic Comput., 24, 235-265 (1997) · Zbl 0898.68039 · doi:10.1006/jsco.1996.0125
[8] C. Bouillaguet, H.-C. Chen, C.-M. Cheng, T. Chou, R. Niederhagen, A. Shamir and B.-Y. Yang, Fast exhaustive search for polynomial systems in \(\begin{document}\mathbb{F}_2\end{document} \), in Cryptographic Hardware and Embedded Systems, CHES 2010 (eds. S. Mangard and F.-X. Standaert), Springer Berlin Heidelberg, Berlin, Heidelberg, 2010, 203-218. · Zbl 1297.94055
[9] A.-T. Chen, M.-S. Chen, T.-R. Chen, C.-M. Cheng, J. Ding, E.-H. Kuo, F.-S. Lee and B.-Y. Yang, Sse implementation of multivariate pkcs on modern x86 cpus, in Cryptographic Hardware and Embedded Systems - CHES 2009 (eds. C. Clavier and K. Gaj), vol. 5747 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2009, 33-48. · Zbl 1290.94055
[10] J. Ding, A. Petzoldt and L.-c. Wang, The cubic simple matrix encryption scheme, in Post-Quantum Cryptography: 6th International Workshop, PQCrypto 2014, Waterloo, ON, Canada, October 1-3, 2014. Proceedings (ed. M. Mosca), Springer International Publishing, Cham, 2014, 76-87. · Zbl 1306.94045
[11] J. Ding and D. Schmidt, Rainbow, a new multivariable polynomial signature scheme, in Applied Cryptography and Network Security (eds. J. Ioannidis, A. Keromytis and M. Yung), vol. 3531 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2005,164-175. · Zbl 1126.68393
[12] J. Ding, D. Schmidt and F. Werner, Algebraic attack on HFE revisited, in Information Security, 11th International Conference, ISC 2008, Taipei, Taiwan, September 15-18, 2008. Proceedings (eds. T.-C. Wu, C.-L. Lei, V. Rijmen and D.-T. Lee), vol. 5222 of Lecture Notes in Computer Science, Springer, 2008,215-227. · Zbl 1181.94092
[13] V. Dubois; P.-A. Fouque; A. Shamir; J. Stern, Practical cryptanalysis of Sflash, CRYPTO, 4622, 1-12 (2007) · Zbl 1215.94043 · doi:10.1007/978-3-540-74143-5_1
[14] J.-C. Faugère and A. Joux, Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases, in Advances in cryptology-CRYPTO 2003, vol. 2729 of Lecture Notes in Comput. Sci., Springer, Berlin, 2003, 44-60. · Zbl 1122.94371
[15] S. Gueron and M. E. Kounavis, White Paper: Intel Carry-Less Multiplication Instruction and its Usage for Computing the GCM Mode, Technical report, Intel, 2010. · Zbl 1234.94044
[16] N. Howgrave-Graham, A hybrid lattice-reduction and meet-in-the-middle attack against ntru, in Advances in Cryptology - CRYPTO 2007 (ed. A. Menezes), vol. 4622 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2007,150-169. · Zbl 1215.94053
[17] Intel®, Intel®64 and IA-32 Architectures Optimization Reference Manual, Technical report, Intel®, 2015.
[18] A. Kipnis, J. Patarin and L. Goubin, Unbalanced oil and vinegar signature schemes, in Advances in cryptology-EUROCRYPT ’99 (Prague), vol. 1592 of Lecture Notes in Comput. Sci., Springer, Berlin, 1999,206-222. · Zbl 0933.94031
[19] A. Kipnis and A. Shamir, Cryptanalysis of the HFE public key cryptosystem by relinearization, in Advances in cryptology-CRYPTO ’99 (Santa Barbara, CA), vol. 1666 of Lecture Notes in Comput. Sci., Springer, Berlin, 1999, 19-30. · Zbl 0940.94012
[20] T. Matsumoto and H. Imai, Public quadratic polynomial-tuples for efficient signature-verification and message-encryption, in Advances in cryptology-EUROCRYPT ’88 (Davos, 1988), vol. 330 of Lecture Notes in Comput. Sci., Springer, Berlin, 1988,419-453. · Zbl 0655.94013
[21] NIST, Proposed submission requirements and evaluation criteria for the post-quantum cryptography standardization process, http://csrc.nist.gov/groups/ST/post-quantum-crypto/call-for-proposals-2016.html, 2016, Accessed: 08/26/2016.
[22] J. Patarin, Hidden Field Equations (HFE) and Isomorphisms of Polynomials (IP): Two new families of asymmetric algorithms, in Advances in Cryptology—EUROCRYPT 96 (ed. U. Maurer), vol. 1070 of Lecture Notes in Computer Science, Springer-Verlag, 1996, 33-48. · Zbl 1301.94125
[23] J. Patarin, N. Courtois and L. Goubin, FLASH, a fast multivariate signature algorithm, in Topics in Cryptology-CT-RSA 2001 (San Francisco, CA), vol. 2020 of Lecture Notes in Comput. Sci., Springer, Berlin, 2001,298-307. · Zbl 0972.68075
[24] J. Patarin, N. Courtois and L. Goubin, QUARTZ, 128-bit long digital signatures, in Topics in cryptology-CT-RSA 2001 (San Francisco, CA), vol. 2020 of Lecture Notes in Comput. Sci., Springer, Berlin, 2001,282-297. · Zbl 0972.68074
[25] J. Patarin, L. Goubin and N. Courtois, C*-+ and HM: Variations around two schemes of T. Matsumoto and H. Imai, in ASIACRYPT ’98: Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security, Springer-Verlag, London, UK, 1998, 35-50. · Zbl 1036.94534
[26] J. Porras, J. Baena and J. Ding, ZHFE, a new multivariate public key encryption scheme, in Post-Quantum Cryptography (ed. M. Mosca), vol. 8772 of Lecture Notes in Computer Science, Springer International Publishing, 2014,229-245. · Zbl 1385.94065
[27] K. Sakumoto, T. Shirai and H. Hiwatari, Public-key identification schemes based on multivariate quadratic polynomials, in Advances in Cryptology - CRYPTO 2011 (ed. P. Rogaway), vol. 6841 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2011,706-723. · Zbl 1283.94104
[28] C. Tao, A. Diene, S. Tang and J. Ding, Simple matrix scheme for encryption, in Post-Quantum Cryptography: 5th International Workshop, PQCrypto 2013, Limoges, France, June 4-7, 2013. Proceedings (ed. P. Gaborit), Springer Berlin Heidelberg, Berlin, Heidelberg, 6841 (2013), 231-242. · Zbl 1306.94094
[29] E. Thomae and C. Wolf, Solving underdetermined systems of multivariate quadratic equations revisited, in Public Key Cryptography - PKC 2012 (eds. M. Fischlin, J. Buchmann and M. Manulis), 7293 (2012), 156-171. · Zbl 1290.94134
[30] R. C. Whaley; A. Petitet, Minimizing development and maintenance costs in supporting persistently optimized BLAS, Software: Practice and Experience, 35, 101-121 (2005) · doi:10.1002/spe.626
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.