Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

15.10.2018

On the security of biquadratic C public-key cryptosystems and its generalizations

Zeitschrift:
Cryptography and Communications
Autor:
Patrick Felke
Wichtige Hinweise
This article is part of the Topical Collection on Special Issue: Mathematical Methods for Cryptography

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Abstract

Public key cryptosystems based on multivariate polynomials have been studied since the eighties. One of them, called C, was introduced in 1988 by Imai and Matsumoto, and broken in 1993 by Dobbertin in classified work he did for the German Federal Office for Information Security and later by Patarin (see Dobbertin et al. 2005, Patarin 1995). Since then, the construction of multivariate systems sharing a great deal of the C properties have become of particular interest. Dobbertin introduced in a series of classified papers and later in a challenge of the MysteryTwister-Competition hosted by the Horst-Görtz-Institute in 2005, (see Dobbertin et al. 2005) together with the author, a system where the central mapping is a power mapping of degree 4 and shares almost all the properties of C. It was therefore called biquadratic C. The challenge remained unbroken and the security of these systems an open problem. As its key size is rather large, the interest in such systems became low during the last years. Due to the initiative of the European Telecommunications Standards Institute and the National Institute for Standards and Technology in creating standards for post-quantum cryptography, systems with bigger key sizes have become of interest for practical applications. In this paper we will consider biquadratic C and more general systems based on hidden monomials of degree k called k-ary C. We will prove a lower bound for the running time of attacks based on Gröbner basis algorithms like F4 or F5. We will compute the first fall degree for k-ary C and give a counterexample to the first fall degree assumption. We will derive an estimate for the complexity of breaking the above mentioned cryptochallenge and give parameter sizes for secure systems by taking into account all known types of attacks. It will turn out that the security requirements yield systems with impractical key sizes even for applications in post-quantum cryptography. Although k-ary C is not of practical interest the results presented here give some insight in understanding the complexity of attacks on multivariate cryptosystems, especially based on Gröbner basis algorithms, and show that these systems are very promising objects for conducting further research in this direction.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Maschinenbau + Werkstoffe​​​​​​​​​​​​​​

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Premium Partner

    Bildnachweise