Article Contents
Article Contents

# Efficient public-key operation in multivariate schemes

• * Corresponding author

This work was partially supported by "Fondo Nacional de Financiamiento para la Ciencia, la Tecnología y la Innovación Francisco José de Caldas", Colciencias (Colombia), Project No. 111865842333 and Contract No. 049-2015

• 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.

Mathematics Subject Classification: Primary: 11T71, 94A60; Secondary: 14G50.

 Citation:

• Figure 1.  Public-key-operation throughput for different number of variables for $m = n$. The register type used in the program to hold the message is fixed for each finite field and shown in brackets. For GF(2) it was a vector each of 4 (64-bit-unsigned int); for the GF(3) it was 16-bit-unsigned integers; for 13 and 73, it was 32-bit-unsigned integers; for 919 and 117659 it was 64-bit-unsigned integers. Finally, for the $2^{64}$ and $2^{128}$ it was used 128-bit registers (coded with assembler intrinsics.)

Figure 2.  Public-key-operation throughput for different number of variables for $m = 2n$. The register type used in the program to hold the message is fixed for each finite field and shown in brackets. See Figure 1 for details

Figure 3.  Public-key-operation throughput for different number of variables in the case $n = 3m$. The register type used in the program to hold the message is fixed for each finite field and shown in brackets. See Figure 1 for details

Figure 4.  Public-key-operation throughput for different number of variables in the case $m = n-r$ with $r = 16$. The register type used in the program to hold the message is fixed for each finite field and shown in brackets. See Figure 1 for details

Figure 5.  Fraction of the peak performance of the processor for the $m = 2n$ case

Figure 6.  Optimal fraction of variable to guess in hybrid attack with field equations

Figure 7.  Time to attack for different values of $n$ and selected fields, in the case $m = n$ equations in $n$ variables

Figure 8.  Time to attack for different values of $n$ and selected fields, in the case $m = 2n$ equations in $n$ variables.

Figure 9.  Time to attack $n = 16$ and $n = 17$, for different prime fields, in the case $m = 2n$ equations in $n$ variables

Figure 10.  Time to attack $n = 16$, for different GF(2) extensions, in the case $m = 2n$ equations in $n$ variables

Figure 11.  Degree of regularity of semiregular sequences of $2n$ quadratic equations in $n$ variables, for any $q$ and without field equations

Figure 12.  Time to attack for different values of $n$ and selected fields, in the case $m$ equations in $n = 3m$ variables

Figure 13.  Time to attack for different values of $n$ and selected fields, in the case $n-r$ equations in $n$ variables, for $r = 16$

Figure 14.  Public-key-operation throughput for different security levels in the case $m = n$ equations in $n$ variables

Figure 15.  Public-key-operation throughput for different security levels in the case $m = 2n$ equations in $n$ variables

Figure 16.  Public-key-operation throughput for different security levels in the case $m$ equations in $3m$ variables

Figure 17.  Public-key-operation throughput for different security levels in the case $m = n-r$ equations in $n$ variables with $r = 16$

Table 1.  Optimal fraction of variable to guess in hybrid attack

 $q$ 2 2(wfe) 3 3(wfe) 13 $\beta_0$ 0.23 0.12 0.05 0.02 $\beta_0$ 0.76 0.55 0.61 0.50 0.27 $q$ 13(wfe) 73 919 117659

Table 2.  Trend line parameters, in the case $m = n$ equations in $n$ variables

 $q$ $c$ $b$ $2$ $1.43*10^{-4}$ $0.61$ $2$ wfe $1.58*10^{-5}$ $0.58$ $3$ $8.62*10^{-6}$ $0.95$ $3$ wfe $2.55*10^{-6}$ $0.98$ $13$ $2.32*10^{-6}$ $1.53$ $13$ wfe $3.16*10^{-5}$ $1.35$ $73$ $1.30*10^{-6}$ $1.76$ $919$ $2.73*10^{-5}$ $1.63$ $117659$ $2.50*10^{-3}$ $1.66$ $2^{64}$ $3.97*10^{-7}$ $2.27$ $2^{128}$ $1.20*10^{-6}$ $2.18$

Table 3.  Trend line parameters, in the case $m = 2n$ equations in $n$ variables

 $q$ $c$ $b$ $2$ $1.43*10^{-4}$ $0.61$ $2$ wfe $1.58*10^{-5}$ $0.58$ $3$ $8.62*10^{-6}$ $0.95$ $3$ wfe $2.55*10^{-6}$ $0.98$ $13$ $2.32*10^{-6}$ $1.53$ $13$ wfe $3.16*10^{-5}$ $1.35$ $73$ $1.30*10^{-6}$ $1.76$ $919$ $2.73*10^{-5}$ $1.63$ $117659$ $2.50*10^{-3}$ $1.66$ $2^{64}$ $3.97*10^{-7}$ $2.27$ $2^{128}$ $1.20*10^{-6}$ $2.18$

Table 4.  $n$ needed for different bit security levels, when $m = n$. For $q = 13, 2^{64}, 2^{128}$ the best attack is the plain algebraic attack, and for the rest is the hybrid approach

 $q$ bit sec. level $2$ $3$ $13$ $73$ $919$ $117659$ $2^{64}$ $2^{128}$ 80 88 54 38 31 32 28 25 25 100 112 68 48 39 40 36 31 31 112 126 77 54 43 45 41 34 35 128 145 88 62 50 52 48 39 40 192 222 133 95 75 79 75 59 61

Table 5.  $n$ needed for different bit security levels, when $m = 2n$

 $q$ bit sec. level $2$ $3$ $13$ $73$ $919$ $117659$ $2^{64}$ $2^{128}$ 80 97 61 55 55 55 54 51 49 100 123 77 69 69 69 68 65 63 112 138 86 77 77 77 76 73 71 128 158 99 88 88 88 87 84 81 192 240 150 133 132 132 130 127 124

Table 6.  $n$ needed for different bit security levels, when $n = 3m$. For $q = 2, 3, 13$ the best attack is a collision attack on the underlying hash function, for $q = 73, 919, 117659$ is the hybrid approach, and for the rest is the plain algebraic attack

 $q$ bit sec.level $2$ $3$ $13$ $73$ $919$ $117659$ $2^{64}$ $2^{128}$ 80 480 315 135 98 100 89 81 82 100 600 394 169 121 125 114 100 102 112 672 441 189 135 141 129 111 113 128 768 504 216 154 161 149 126 129 192 1152 756 324 230 243 229 187 192

Table 7.  $n$ needed for different bit security levels, when $m = n-r$, for $r = 16$. For $q = 2, 3, 13$ the best attack is a collision attack on the underlying hash function, for $q = 73, 919, 117659$ is the hybrid approach, and for the rest is the plain algebraic attack

 $q$ bit sec.level $2$ $3$ $13$ $73$ $919$ $117659$ $2^{64}$ $2^{128}$ 80 176 121 61 47 48 44 41 42 100 216 147 72 55 56 52 48 48 112 240 163 79 59 61 57 51 52 128 272 184 88 66 68 64 56 57 192 400 268 124 91 95 91 77 78
•  [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. [2] D. J. Bernstein, J. Buchmann and E. Dahmen, Post-Quantum Cryptography, Springer-Verlag, Berlin, 2009. doi: 10.1007/978-3-540-88702-7. [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. doi: 10.1007/978-3-540-68164-9_10. [4] L. Bettale, J.-C. Faugere and L. Perret, Hybrid approach for solving multivariate systems over finite fields, Journal of Mathematical Cryptology, 3 (2009), 177-197.  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. doi: 10.1145/2442829.2442843. [6] L. Bettale, J.-C. Faugère and L. Perret, Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic, Designs, Codes and Cryptography, 69 (2013), 1-52.  doi: 10.1007/s10623-012-9617-2. [7] W. Bosma, J. Cannon and C. Playoust, The Magma algebra system. Ⅰ. The user language, J. Symbolic Comput., 24 (1997), 235-265.  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 $\mathbb{F}_2$, in Cryptographic Hardware and Embedded Systems, CHES 2010 (eds. S. Mangard and F.-X. Standaert), Springer Berlin Heidelberg, Berlin, Heidelberg, 2010, 203–218. [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. doi: 10.1007/978-3-642-04138-9_3. [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. [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. doi: 10.1007/11496137_12. [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. doi: 10.1007/978-3-540-85886-7_15. [13] V. Dubois, P.-A. Fouque, A. Shamir and J. Stern, Practical cryptanalysis of Sflash, CRYPTO, 4622 (2007), 1-12.  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. doi: 10.1007/978-3-540-45146-4_3. [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. [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. doi: 10.1007/978-3-540-74143-5_9. [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. doi: 10.1007/3-540-48910-X_15. [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. doi: 10.1007/3-540-48405-1_2. [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. doi: 10.1007/3-540-45961-8_39. [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. [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. doi: 10.1007/3-540-45353-9_22. [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. doi: 10.1007/3-540-45353-9_21. [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. doi: 10.1007/3-540-49649-1_4. [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. doi: 10.1007/978-3-319-11659-4_14. [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. doi: 10.1007/978-3-642-22792-9_40. [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. [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. doi: 10.1007/978-3-642-30057-8_10. [30] R. C. Whaley and A. Petitet, Minimizing development and maintenance costs in supporting persistently optimized BLAS, Software: Practice and Experience, 35 (2005), 101-121.  doi: 10.1002/spe.626.

Figures(17)

Tables(7)