nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

Analysis of Multivariate Encryption Schemes: Application to Dob

verfasst von : Morten Øygarden, Patrick Felke, Håvard Raddum

Erschienen in: Public-Key Cryptography – PKC 2021

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, we study the effect of two modifications to multivariate public key encryption schemes: internal perturbation (ip), and \(Q_+\). Focusing on the Dob encryption scheme, a construction utilising these modifications, we accurately predict the number of degree fall polynomials produced in a Gröbner basis attack, up to and including degree five. The predictions remain accurate even when fixing variables. Based on this new theory we design a novel attack on the Dob encryption scheme, which breaks Dob using the parameters suggested by its designers.

While our work primarily focuses on the Dob encryption scheme, we also believe that the presented techniques will be of particular interest to the analysis of other big–field schemes.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Isogeny-Based Key Compression Without Pairings

Nächstes Kapitel On the Integer Polynomial Learning with Errors Problem

Here we follow the nomenclature used, for instance, in [18].

The authors of [20] named these two modifiers \(\oplus \) and \(``+"\). Note that in earlier literature (c.f. [31]), the \(``+"\) modification refers to a different modification than what is described in [20], and the \(\oplus \) modification has been called internal perturbation (ip). (To the best of our knowledge, the \(``+"\) modification from [20] has not been used in earlier work). To avoid any confusion, we have chosen to stick with the name (ip) and use \(Q_+\) for [20]’s “+".

Not all of these will be linearly independent in \(\mathcal {S}(\mathcal {F})\). For example, the d syzygies associated with \((X^{2^m} + X^2)G_1\) will correspond to syzygies in \(\mathcal {T}(\mathcal {F}^h)\). This does not really matter, as the expressions Eq. (18) and Eq. (19) corrects for this.

If \(p_R\) has degree \(\ge 3\), then the syzygy \(p_R^2 + p_R = 0\) will be of degree \(> \nu \). In this case \(p_R\) will not be among the generators of \(\mathcal {H}\). We shall see later, in Remark (1), that the effect of \(p_R\) can also be removed in the degree 2 case, but at an added cost to the run time.

We will see later that the gluing also requires some overlap between the variable sets, but this is not a problem for the parameters we are interested in.

Here we implicitly assume that k variables have been eliminated by the linear forms \(v_i^*\).

For nude Dob, the polynomial \(X^5F\) can be used to create linear polynomials (see Equation (35), Appendix D in [33]). The crucial difference is that in this case, the linear term X can be cancelled out at degree 3, whereas this is not possible for a general L(X).

Apon, D., Moody, D., Perlner, R., Smith-Tone, D., Verbel, J.: Combinatorial rank attacks against the rectangular simple matrix encryption scheme. In: Ding, J., Tillich, J.-P. (eds.) PQCrypto 2020. LNCS, vol. 12100, pp. 307–322. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-44223-1_17CrossRef

Bardet, M., Faugère, J.-C., Salvy, B.: Complexity of Gröbner basis computation for Semi-regular Overdetermined sequences over \(\mathbb{F}_2\) with solutions in \(\mathbb{F}_2\). (2003). [Research Report] RR-5049, INRIA, inria-00071534

Bettale, L., Faugère, J.-C., Perret, L.: Hybrid approach for solving multivariate systems over finite fields. J. Math. Cryptology 3(3), 177–197 (2009)MathSciNetCrossRef

Carlet. S.: Vectorial boolean functions for cryptography. In: Crama, Y., Hammer, P.L., (eds.), Boolean Models and Methods in Mathematics, Computer Science, and Engineering, pp. 398–469. Cambridge University Press (2010)

Cartor, R., Smith-Tone, D.: EFLASH: a new multivariate encryption scheme. In: Cid Jr., C., Jacobson, M. (eds.) Selected Areas in Cryptography - SAC 2018, vol. 11349, pp. 281–299. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-10970-7_13CrossRef

Cheng, Chen-Mou, Chou, Tung, Niederhagen, Ruben, Yang, Bo-Yin: Solving quadratic equations with XL on parallel architectures. In: Prouff, Emmanuel, Schaumont, Patrick (eds.) CHES 2012. LNCS, vol. 7428, pp. 356–373. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33027-8_21CrossRef

Cox, D.A., Little, J., O’shea, D.: Using Algebraic Geometry. Springer, Heidelberg (2006). https://doi.org/10.1007/b138611CrossRefMATH

Ding, J.: A new variant of the matsumoto-imai cryptosystem through perturbation. In: Bao, F., Deng, R., Zhou, J. (eds.) PKC 2004. LNCS, vol. 2947, pp. 305–318. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24632-9_22CrossRef

Ding, J., Gower, J.E.: Inoculating multivariate schemes against differential attacks. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006. LNCS, vol. 3958, pp. 290–301. Springer, Heidelberg (2006). https://doi.org/10.1007/11745853_19CrossRef

10.

Ding, J., Hodges, T.J.: Inverting HFE systems is quasi-polynomial for all fields. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 724–742. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_41CrossRef

11.

Ding, J., Perlner, R., Petzoldt, A., Smith-Tone, D.: Improved cryptanalysis of HFEv- via projection. In: Lange, T., Steinwandt, R. (eds.) PQCrypto 2018. LNCS, vol. 10786, pp. 375–395. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-79063-3_18CrossRef

12.

Ding, J., Schmidt, D.: Cryptanalysis of HFEv and internal perturbation of HFE. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 288–301. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30580-4_20CrossRef

13.

Dobbertin, H.: Almost perfect nonlinear power functions on GF (2/sup n/): the welch case. IEEE Trans. Inf. Theory 45(4), 1271–1275 (1999)MathSciNetCrossRef

14.

Dubois, V., Granboulan, L., Stern, J.: Cryptanalysis of HFE with internal perturbation. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 249–265. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-71677-8_17CrossRef

15.

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

16.

Faugère, J.-C., Joux, A.: Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 44–60. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_3CrossRef

17.

Fouque, P.-A., Granboulan, L., Stern, J.: Differential cryptanalysis for multivariate schemes. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 341–353. Springer, Heidelberg (2005). https://doi.org/10.1007/11426639_20CrossRef

18.

Hoffman, J.W., Jia, X., Wang, H.: Commutative Algebra: An Introduction. Stylus Publishing, LLC (2016)MATH

19.

https://github.com/Simula-UiB/Attack-On-The-Dob-Encryption-Scheme

20.

Macario-Rat, G., Patarin, J.: Two-face: new public key multivariate schemes. In: Joux, A., Nitaj, A., Rachidi, T. (eds.) AFRICACRYPT 2018. LNCS, vol. 10831, pp. 252–265. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-89339-6_14CrossRef

21.

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

22.

Ø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

23.

Patarin, J.: Cryptanalysis of the matsumoto and imai public key scheme of eurocrypt 1988. 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

24.

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

25.

Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124–134. IEEE (1994)

26.

Smith-Tone, D., Verbel, J.: A rank attack against extension field cancellation. In: Ding, J., Tillich, J.-P. (eds.) PQCrypto 2020. LNCS, vol. 12100, pp. 381–401. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-44223-1_21CrossRef

27.

Szepieniec, A., Ding, J., Preneel, B.: Extension field cancellation: a new central trapdoor for multivariate quadratic systems. In: Takagi, T. (ed.) PQCrypto 2016. LNCS, vol. 9606, pp. 182–196. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-29360-8_12CrossRef

28.

Tao, C., Xiang, H., Petzoldt, A., Ding, J.: Simple matrix-a multivariate public key cryptosystem (MPKC) for encryption. Finite Fields Appl. 35, 352–368 (2015)MathSciNetCrossRef

29.

Wang, Y., Ikematsu, Y., Duong, D.H., Takagi, T.: The secure parameters and efficient decryption algorithm for multivariate public key cryptosystem EFC. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 102(9), 1028–1036 (2019)CrossRef

30.

Wiedemann, D.: Solving sparse linear equations over finite fields. IEEE Trans. Inf. Theory 32(1), 54–62 (1986)MathSciNetCrossRef

31.

Wolf, C., Preneel, B.: Taxonomy of public key schemes based on the problem of multivariate quadratic equations. Cryptology ePrint Archive, Report 2005/077 (2005). https://eprint.iacr.org/2005/077

32.

Yasuda, T., Wang, Y., Takagi, T.: Multivariate encryption schemes based on polynomial equations over real numbers. In: Ding, J., Tillich, J.-P. (eds.) PQCrypto 2020. LNCS, vol. 12100, pp. 402–421. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-44223-1_22CrossRef

33.

Ø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 (Extended Version)

Titel: Analysis of Multivariate Encryption Schemes: Application to Dob
verfasst von: Morten Øygarden
Patrick Felke
Håvard Raddum
Verlag: Springer International Publishing
Buch: Public-Key Cryptography – PKC 2021
Print ISBN: 978-3-030-75244-6

Electronic ISBN: 978-3-030-75245-3

Copyright-Jahr: 2021
DOI: https://doi.org/10.1007/978-3-030-75245-3_7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"