Top

Published in:

2021 | OriginalPaper | Chapter

On the Effect of Projection on Rank Attacks in Multivariate Cryptography

Authors : Morten Øygarden, Daniel Smith-Tone, Javier Verbel

Published in: Post-Quantum Cryptography

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The multivariate scheme HFEv- used to be considered a promising candidate for a post-quantum signature system. First suggested in the early 2000s, a version of the scheme made it to the third round of the ongoing NIST post-quantum standardization process. In late 2020, the system suffered from an efficient rank attack due to Tao, Petzoldt, and Ding. In this paper, we inspect how this recent rank attack is affected by the projection modification. This modification was introduced to secure the signature scheme PFLASH against its predecessor’s attacks. We prove upper bounds for the rank of projected HFEv- (pHFEv-) and PFLASH under the new attack, which are tight for the experiments we have performed. We conclude that projection could be a useful tool in protecting against this recent cryptanalysis.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter New Practical Multivariate Signatures from a Nonlinear Modifier

next chapter Quantum Key Search for Ternary LWE

Available only for authorised users

This is a slight abuse of notation from the S defined in Sect. 2, which had \(\mathbb {F}_q^{n - p}\) as its domain. This is easily remedied by composing with a projection along the \(n -p\) first coordinates.

Following our slight abuse of notation when compared with Sect. 2: \(U'\) will now be an invertible linear map \(\mathbb {F}_q^{n + v}\rightarrow \mathbb {F}_q^{n + v}\).

Any mention of commercial products does not indicate endorsement by NIST.

Berlekamp, E.R.: Factoring polynomials over large finite fields. Math. Comput. 24(111), 713–735 (1970)MathSciNetCrossRef

Bettale, L., Faugère, J.-C., Perret, L.: Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic. Des. Codes Cryptogr. 69(1), 1–52 (2013)MathSciNetCrossRef

Beullens, W.: Improved Cryptanalysis of UOV and Rainbow. Cryptology ePrint Archive, Report 2020/1343 (2020). https://eprint.iacr.org/2020/1343

Bosma, W., Cannon, J., Playoust, C.: The magma algebra system i: the user language. J. Symb. Comput. 24(3–4), 235–265 (1997)MathSciNetCrossRef

Cantor, D., Kaltofen, E.: On fast multiplication of polynomials over arbitrary algebras. Acta Informatica 28, 693–701 (1991)MathSciNetCrossRef

Cartor, R., Smith-Tone, D.: An updated security analysis of PFLASH. In: Lange, T., Takagi, T. (eds.) PQCrypto 2017. LNCS, vol. 10346, pp. 241–254. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59879-6_14CrossRef

Cartor, R., Smith-Tone, D.: EFLASH: a new multivariate encryption scheme. In: Cid, C., Jacobson, M.J., Jr. (eds.) SAC 2018. LNCS, vol. 11349, pp. 281–299. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-10970-7_13

Casanova, A., Faugère, J.-C., Macario-Rat, G., Patarin, J., Perret, L., Ryckeghem, J.: GeMSS: a great multivariate short signature (Round 3 submission). Technical report, National Institute of Standards and Technology (2020). https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions

Chen, M.-S., Yang, B.-Y., Smith-Tone, D.: PFLASH-secure asymmetric signatures on smart cards. In: Lightweight Cryptography Workshop (2015)

10.

Daniels, T., Smith-Tone, D.: Differential properties of the HFE cryptosystem. In: Mosca, M. (ed.) PQCrypto 2014. LNCS, vol. 8772, pp. 59–75. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-11659-4_4CrossRef

11.

Ding, J., Chen, M.-S., Petzoldt, A., Schmidt, D., Yang, B.-Y.: GUI. Technical report, National Institute of Standards and Technology (2017). https://csrc.nist.gov/Projects/post-quantum-cryptography/Round-1-Submissions

12.

Ding, J., et al.: Rainbow (round 3 submission). Technical report, National Institute of Standards and Technology (2020). https://csrc.nist.gov/Projects/post-quantum-cryptography/round-3-submissions

13.

Ding, J., Dubois, V., Yang, B.-Y., Chen, O.C.-H., Cheng, C.-M.: Could SFLASH be Repaired? In: Aceto, L., et al. (eds.) ICALP 2008. LNCS, vol. 5126, pp. 691–701. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-70583-3_56CrossRef

14.

Dubois, V., Fouque, P.-A., Shamir, A., Stern, J.: Practical cryptanalysis of SFLASH. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 1–12. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74143-5_1CrossRef

15.

Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases (F4). J. Pure and Appl. Algebra 139(1–3), 61–88 (1999)MathSciNetCrossRef

16.

Le Gall, F.: Powers of tensors and fast matrix multiplication. In: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pp. 296–303 (2014)

17.

Faugère, J.-C., Levy-dit-Vehel, F., Perret, L.: Cryptanalysis of MinRank. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 280–296. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_16CrossRef

18.

Matsumoto, T., Imai, H.: Public quadratic polynomial-tuples for efficient signature-verification and message-encryption. In: Barstow, D., et al. (eds.) EUROCRYPT 1988. LNCS, vol. 330, pp. 419–453. Springer, Heidelberg (1988). https://doi.org/10.1007/3-540-45961-8_39CrossRef

19.

Øygarden, M., Felke, P., Raddum, H., Cid, C.: Cryptanalysis of the multivariate encryption scheme EFLASH. In: Jarecki, S. (ed.) CT-RSA 2020. LNCS, vol. 12006, pp. 85–105. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-40186-3_5CrossRef

20.

Patarin, J.: Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt’88. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 248–261. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-44750-4_20CrossRef

21.

Patarin, J.: Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of asymmetric algorithms. In: Maurer, U. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 33–48. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68339-9_4CrossRef

22.

Smith-Tone, D.: Properties of the discrete differential with cryptographic applications. In: Sendrier, N. (ed.) PQCrypto 2010. LNCS, vol. 6061, pp. 1–12. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-12929-2_1CrossRef

23.

Strassen, V.: Gaussian elimination is not optimal. Numerische mathematik 13(4), 354–356 (1969)MathSciNetCrossRef

24.

Tao, C., Petzoldt, A., Ding, J.: Improved Key Recovery of the HFEv- Signature Scheme. Cryptology ePrint Archive, Report 2020/1424 (2020). https://eprint.iacr.org/2020/1424

25.

Vates, J., Smith-Tone, D.: Key recovery attack for all parameters of HFE-. In: Lange, T., Takagi, T. (eds.) PQCrypto 2017. LNCS, vol. 10346, pp. 272–288. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59879-6_16CrossRef

26.

Øygarden, M., Felke, P., Raddum, H.: Analysis of Multivariate Encryption Schemes: Application to Dob. Cryptology ePrint Archive, Report 2020/1442 (2020). https://eprint.iacr.org/2020/1442

Title: On the Effect of Projection on Rank Attacks in Multivariate Cryptography
Authors: Morten Øygarden
Daniel Smith-Tone
Javier Verbel
Publisher: Springer International Publishing
Book: Post-Quantum Cryptography
Print ISBN: 978-3-030-81292-8

Electronic ISBN: 978-3-030-81293-5

Copyright Year: 2021
DOI: https://doi.org/10.1007/978-3-030-81293-5_6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner