American Institute of Mathematical Sciences

Advanced
May  2019, 13(2): 343-371. doi: 10.3934/amc.2019023

Efficient public-key operation in multivariate schemes

Felipe Cabarcas 1,, , Daniel Cabarcas 2, and  John Baena 2,

1. 

Grupo SISTEMIC, Departamento de Ingeniería Electrónica, Universidad de Antioquia (UdeA), Calle 70 No. 52-21, Medellín, Colombia
2. 

Universidad Nacional de Colombia Sede Medellín, Calle 59 A N 63-20, Medellín, Colombia

* Corresponding author

Received  July 2018 Revised  January 2019 Published  February 2019

Fund Project: 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.

Keywords: Multivariate public-key cryptography, encryption schemes, signature schemes, ZHFE, UOV, Rainbow, algebraic attack, x86 architecture, SIMD, PCLMULQDQ.
Mathematics Subject Classification: Primary: 11T71, 94A60; Secondary: 14G50.
Citation: Felipe Cabarcas, Daniel Cabarcas, John Baena. Efficient public-key operation in multivariate schemes. Advances in Mathematics of Communications, 2019, 13 (2) : 343-371. doi: 10.3934/amc.2019023
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. Google Scholar

[2]

D. J. Bernstein, J. Buchmann and E. Dahmen, Post-Quantum Cryptography, Springer-Verlag, Berlin, 2009. doi: 10.1007/978-3-540-88702-7.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[17]

Intel®, Intel®64 and IA-32 Architectures Optimization Reference Manual, Technical report, Intel®, 2015. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

show all references

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. Google Scholar

[2]

D. J. Bernstein, J. Buchmann and E. Dahmen, Post-Quantum Cryptography, Springer-Verlag, Berlin, 2009. doi: 10.1007/978-3-540-88702-7.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[17]

Intel®, Intel®64 and IA-32 Architectures Optimization Reference Manual, Technical report, Intel®, 2015. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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 Options

Download full-size image

Download as PowerPoint slide

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 Options

Download full-size image

Download as PowerPoint slide

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 Options

Download full-size image

Download as PowerPoint slide

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 Options

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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 Options

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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 Options

Download as excel

$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 Options

Download as excel

$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 Options

Download as excel

$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 Options

Download as excel

$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 Options

Download as excel

$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 Options

Download as excel

$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
Table Options

Download as excel

$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]

Anton Stolbunov. Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Advances in Mathematics of Communications, 2010, 4 (2) : 215-235. doi: 10.3934/amc.2010.4.215
[2]

Gerhard Frey. Relations between arithmetic geometry and public key cryptography. Advances in Mathematics of Communications, 2010, 4 (2) : 281-305. doi: 10.3934/amc.2010.4.281
[3]

Gérard Maze, Chris Monico, Joachim Rosenthal. Public key cryptography based on semigroup actions. Advances in Mathematics of Communications, 2007, 1 (4) : 489-507. doi: 10.3934/amc.2007.1.489
[4]

Jintai Ding, Zheng Zhang, Joshua Deaton. The singularity attack to the multivariate signature scheme HIMQ-3. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020043
[5]

Yvo Desmedt, Niels Duif, Henk van Tilborg, Huaxiong Wang. Bounds and constructions for key distribution schemes. Advances in Mathematics of Communications, 2009, 3 (3) : 273-293. doi: 10.3934/amc.2009.3.273
[6]

Mohammad Sadeq Dousti, Rasool Jalili. FORSAKES: A forward-secure authenticated key exchange protocol based on symmetric key-evolving schemes. Advances in Mathematics of Communications, 2015, 9 (4) : 471-514. doi: 10.3934/amc.2015.9.471
[7]

Mohamed Baouch, Juan Antonio López-Ramos, Blas Torrecillas, Reto Schnyder. An active attack on a distributed Group Key Exchange system. Advances in Mathematics of Communications, 2017, 11 (4) : 715-717. doi: 10.3934/amc.2017052
[8]

Yang Lu, Quanling Zhang, Jiguo Li. An improved certificateless strong key-insulated signature scheme in the standard model. Advances in Mathematics of Communications, 2015, 9 (3) : 353-373. doi: 10.3934/amc.2015.9.353
[9]

Paolo Aluffi. Segre classes of monomial schemes. Electronic Research Announcements, 2013, 20: 55-70. doi: 10.3934/era.2013.20.55
[10]

Marx Chhay, Aziz Hamdouni. On the accuracy of invariant numerical schemes. Communications on Pure & Applied Analysis, 2011, 10 (2) : 761-783. doi: 10.3934/cpaa.2011.10.761
[11]

Benjamin Seibold, Rodolfo R. Rosales, Jean-Christophe Nave. Jet schemes for advection problems. Discrete & Continuous Dynamical Systems - B, 2012, 17 (4) : 1229-1259. doi: 10.3934/dcdsb.2012.17.1229
[12]

Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145.

[13]

Joan-Josep Climent, Juan Antonio López-Ramos. Public key protocols over the ring $E_{p}^{(m)}$. Advances in Mathematics of Communications, 2016, 10 (4) : 861-870. doi: 10.3934/amc.2016046
[14]

Yakov Pesin, Samuel Senti. Equilibrium measures for maps with inducing schemes. Journal of Modern Dynamics, 2008, 2 (3) : 397-430. doi: 10.3934/jmd.2008.2.397
[15]

Claire david@lmm.jussieu.fr David, Pierre Sagaut. Theoretical optimization of finite difference schemes. Conference Publications, 2007, 2007 (Special) : 286-293. doi: 10.3934/proc.2007.2007.286
[16]

Henk van Tilborg, Josef Pieprzyk, Ron Steinfeld, Huaxiong Wang. New constructions of anonymous membership broadcasting schemes. Advances in Mathematics of Communications, 2007, 1 (1) : 29-44. doi: 10.3934/amc.2007.1.29
[17]

Yaozhong Hu, Yanghui Liu, David Nualart. Taylor schemes for rough differential equations and fractional diffusions. Discrete & Continuous Dynamical Systems - B, 2016, 21 (9) : 3115-3162. doi: 10.3934/dcdsb.2016090
[18]

Gilberto Bini, Margarida Melo, Filippo Viviani. On GIT quotients of Hilbert and Chow schemes of curves. Electronic Research Announcements, 2012, 19: 33-40. doi: 10.3934/era.2012.19.33
[19]

Emma Hoarau, Claire david@lmm.jussieu.fr David, Pierre Sagaut, Thiên-Hiêp Lê. Lie group study of finite difference schemes. Conference Publications, 2007, 2007 (Special) : 495-505. doi: 10.3934/proc.2007.2007.495
[20]

P. Smoczynski, Mohamed Aly Tawhid. Two numerical schemes for general variational inequalities. Journal of Industrial & Management Optimization, 2008, 4 (2) : 393-406. doi: 10.3934/jimo.2008.4.393

2018 Impact Factor: 0.879

Tools

Metrics

  • PDF downloads (144)
  • HTML views (451)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences