Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Improved Security Proofs in Lattice-Based Cryptography: Using the Rényi Divergence Rather Than the Statistical Distance Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Design Principles for HFEv- Based Multivariate Signature Schemes

verfasst von : Albrecht Petzoldt, Ming-Shing Chen, Bo-Yin Yang, Chengdong Tao, Jintai Ding

Erschienen in: Advances in Cryptology -- ASIACRYPT 2015

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

The Hidden Field Equations (HFE) Cryptosystem as proposed by Patarin is one of the best known and most studied multivariate schemes. While the security of the basic scheme appeared to be very weak, the HFEv- variant seems to be a good candidate for digital signature schemes on the basis of multivariate polynomials. However, the currently existing scheme of this type, the QUARTZ signature scheme, is hardly used in practice because of its poor efficiency. In this paper we analyze recent results from Ding and Yang about the degree of regularity of HFEv- systems and derive from them design principles for signature schemes of the HFEv- type. Based on these results we propose the new HFEv- based signature scheme Gui, which is more than 100 times faster than QUARTZ and therefore highly comparable with classical signature schemes such as RSA and ECDSA.

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 Type 2 Structure-Preserving Signature Schemes Revisited
Nächstes Kapitel Oblivious Network RAM and Leveraging Parallelism to Achieve Obliviousness
Fußnoten
1
We call our new scheme Gui, referring to earthenware pottery dating back to the 4000-year-old Longshan culture [31].
 
Literatur
1.
Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.): Post Quantum Cryptography. Springer, Heidelberg (2009)MATH
2.
Bernstein, D.J., Duif, N., Lange, T., Schwabe, P., Yang, B.-Y.: High-speed high-security signatures. J. Cryptographic Eng. 2(2), 77–89 (2012)CrossRefMATH
3.
4.
Bettale, L., Faugère, J.C., Perret, L.: Hybrid approach for solving multivariate systems over finite fields. J. Math. Cryptol. 3, 177–197 (2009)MathSciNetCrossRefMATH
5.
Bogdanov, A., Eisenbarth, T., Rupp, A., Wolf, C.: Time-area optimized public-key engines: \(\cal MQ\)-cryptosystems as replacement for elliptic curves? In: Oswald, E., Rohatgi, P. (eds.) CHES 2008. LNCS, vol. 5154, pp. 45–61. Springer, Heidelberg (2008)CrossRef
6.
Chen, A.I.-T., Chen, M.-S., Chen, T.-R., Cheng, C.-M., Ding, J., Kuo, E.L.-H., Lee, F.Y.-S., Yang, B.-Y.: SSE implementation of multivariate PKCs on modern x86 CPUs. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 33–48. Springer, Heidelberg (2009) CrossRef
7.
Courtois, N.T., Daum, M., Felke, P.: On the security of HFE, HFEv- and QUARTZ. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 337–350. Springer, Heidelberg (2003)CrossRef
8.
Ding, J., Gower, J.E., Schmidt, D.S.: Multivariate Public Key Cryptosystems. Springer, New York (2006)MATH
9.
Ding, J., Kleinjung, T.: Degree of regularity for HFE-. IACR eprint 2011/570
10.
Ding, J., Schmidt, D.: Rainbow, a new multivariable polynomial signature scheme. In: Ioannidis, J., Keromytis, A.D., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 164–175. Springer, Heidelberg (2005) CrossRef
11.
Ding, J., Yang, B.-Y.: Degree of regularity for HFEv and HFEv-. In: Gaborit, P. (ed.) PQCrypto 2013. LNCS, vol. 7932, pp. 52–66. Springer, Heidelberg (2013) CrossRef
12.
13.
Faugère, J.C., Safey el Din, M., Spaenlehauer, P.J.: On the complexity of the generalized MinRank problem. J. Symbolic Comput. 55, 30–58 (2013)MathSciNetCrossRefMATH
14.
15.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)MATH
16.
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of STOC, pp. 212–219. ACM (1996)
17.
18.
Jiang, X., Ding, J., Hu, L.: Kipnis-Shamir attack on HFE revisited. In: Pei, D., Yung, M., Lin, D., Wu, C. (eds.) Inscrypt 2007. LNCS, vol. 4990, pp. 399–411. Springer, Heidelberg (2008) CrossRef
19.
Kravitz, D.: Digital Signature Algorithm. US patent 5231668, July 1991
20.
Kipnis, A., Patarin, J., Goubin, L.: Unbalanced oil and vinegar signature schemes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 206–222. Springer, Heidelberg (1999) CrossRef
21.
Kipnis, A., Shamir, A.: Cryptanalysis of the HFE public key cryptosystem by relinearization. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 19–30. Springer, Heidelberg (1999) CrossRef
22.
Mohamed, M.S.E., Ding, J., Buchmann, J.: Towards algebraic cryptanalysis of HFE challenge 2. In: Kim, T., Adeli, H., Robles, R.J., Balitanas, M. (eds.) ISA 2011. CCIS, vol. 200, pp. 123–131. Springer, Heidelberg (2011) CrossRef
23.
Matsumoto, T., Imai, H.: Public quadratic polynomial-tuples for efficient signature-verification and message-encryption. In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 419–453. Springer, Heidelberg (1988) CrossRef
24.
Patarin, J., Courtois, N.T., Goubin, L.: QUARTZ, 128-bit long digital signatures. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 282–297. Springer, Heidelberg (2001) CrossRef
25.
Patarin, J., Courtois, N.T., Goubin, L.: FLASH, a fast multivariate signature algorithm. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 298–307. Springer, Heidelberg (2001) CrossRef
26.
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)
27.
Richards, C.: Algorithms for factoring square-free polynomials over finite fields. Master thesis, Simon Fraser University, Canada (2009)
28.
Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)MathSciNetCrossRefMATH
29.
Shor, P.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)MathSciNetCrossRefMATH
30.
Taverne, J., Faz-Hernández, A., Aranha, D.F., Rodríguez-Henríquez, F., Hankerson, D., López, J.: Software implementation of binary elliptic curves: impact of the carry-less multiplier on scalar multiplication. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 108–123. Springer, Heidelberg (2011) CrossRef
31.
Metadaten
Titel
Design Principles for HFEv- Based Multivariate Signature Schemes
verfasst von
Albrecht Petzoldt
Ming-Shing Chen
Bo-Yin Yang
Chengdong Tao
Jintai Ding
Copyright-Jahr
2015
Verlag
Springer Berlin Heidelberg
Buch
Advances in Cryptology -- ASIACRYPT 2015

Print ISBN: 978-3-662-48796-9

Electronic ISBN: 978-3-662-48797-6

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-662-48797-6_14

Premium Partner

    Bildnachweise