nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Multivariate Encryption Schemes Based on the Constrained MQ Problem

verfasst von : Takanori Yasuda

Erschienen in: Provable Security

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

The MQ problem is mathematical in nature and is related to the security of Multivariate Public Key Cryptography (MPKC). In this paper, we introduce the constrained MQ problem, which is a new mathematical problem derived from the MQ problem. We also propose an encryption scheme construction method in MPKC, the pq-method, whose security is mainly based on the difficulty of solving the constrained MQ problem. We analyze the difficulty level of solving the constrained MQ problem, including different approach from the usual for solving the MQ problem. Furthermore, based on the analysis of the constrained MQ problem, we present secure parameters for the pq-method, and implement the practical 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 A CCA-Secure Collusion-Resistant Identity-Based Proxy Re-Encryption Scheme

Nächstes Kapitel Token-Based Multi-input Functional Encryption

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

Bertsekas, D.P.: Nonlinear Programming, 3rd edn. Athena Scientific, Belmont (2016)MATH

Billet, O., Macario-Rat, G.: Cryptanalysis of the square cryptosystems. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 451–468. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10366-7_27CrossRef

Yang, B.-Y., Chen, J.-M.: All in the XL family: theory and practice. In: Park, C., Chee, S. (eds.) ICISC 2004. LNCS, vol. 3506, pp. 67–86. Springer, Heidelberg (2005). https://doi.org/10.1007/11496618_7CrossRef

Clough, C., Baena, J., Ding, J., Yang, B.-Y., Chen, M.: Square, a new multivariate encryption scheme. In: Fischlin, M. (ed.) CT-RSA 2009. LNCS, vol. 5473, pp. 252–264. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00862-7_17CrossRef

Coppersmith, D., Stern, J., Vaudenay, S.: The security of the birational permutation signature schemes. J. Cryptogr. 10(3), 207–221 (1997)MathSciNetCrossRef

Ding, J., Gower, J.E., Schmidt, D.S.: Multivariate Public Key Cryptosystems. Advances in Information Security, vol. 25. Springer, Heidelberg (2006). https://doi.org/10.1007/978-0-387-36946-4CrossRefMATH

Ding, J., Schmidt, D.: The new implementation schemes of the TTM cryptosystem are not secure. Progress Comput. Sci. Appl. Log. 23, 113–127 (2004)MathSciNetMATH

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

10.

Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In: Proceedings of ISSAC 2002, pp. 75–83. ACM Press (2002)

11.

Fell, H.J., Diffie, W.: Analysis of a public key approach based on polynomial substitution. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 340–349. Springer, Heidelberg (1986). https://doi.org/10.1007/3-540-39799-X_24CrossRef

12.

Fröberg, R.: An inequality for Hilbert series of graded algebras. Mathematica Scandinavica 56, 117–144 (1985)MathSciNetCrossRef

13.

Goubin, L., Courtois, N.T.: Cryptanalysis of the TTM cryptosystem. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 44–57. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44448-3_4CrossRef

14.

Hassegawa, S., Kaneko, T.: An attacking method for a public key cryptosystem based on the difficulty of solving a system of non-linear equations. In: Proceedings of 10th SITA, JA5-3 (1987). (in Japanese)

15.

Ikematsu, Y., Perlner, R., Smith-Tone, D., Takagi, T., Vates, J.: HFERP - a new multivariate encryption scheme. In: Lange, T., Steinwandt, R. (eds.) PQCrypto 2018. LNCS, vol. 10786, pp. 396–416. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-79063-3_19CrossRef

16.

Kanzowa, C., Yamashita, N., Fukushima, M.: Levenberg-Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints. J. Comput. Appl. Math. 172(2), 375–397 (2004)MathSciNetCrossRef

17.

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). https://doi.org/10.1007/3-540-48405-1_2CrossRef

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.

Moh, T.-T.: A fast public key system with signature and master key functions. Commun. Algebra 27(5), 2207–2222 (1999)MathSciNetCrossRef

20.

Moh, T.-T.: A fast public key system with signature and master Key functions. In: Proceedings of CrypTEC 1999, pp. 63–69 (1999)

21.

Moh, T.-T., Chen, J.-M.: On the Goubin-Courtois attack on TTM. Cryptology ePrint Archive (2001). http://eprint.iacr.org/2001/072

22.

Nguyen, P.Q.: Hermite’s constant and lattice algorithms. In: Nguyen, P., Vallée, B. (eds.) The LLL Algorithm. ISC, pp. 19–69. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02295-1_2CrossRef

23.

Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, Heidelberg (2006). https://doi.org/10.1007/978-0-387-40065-5CrossRefMATH

24.

Okamoto, E., Nakamura, K.: Evaluation of public key cryptosystems proposed recently. In: Proceedings of 1986’s Symposium of Cryptography and Information Security, vol. D1 (1986). (in Japanese)

25.

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

26.

Shamir, A.: Efficient signature schemes based on birational permutations. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 1–12. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48329-2_1CrossRef

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., Diene, A., Tang, S., Ding, J.: Simple matrix scheme for encryption. In: Gaborit, P. (ed.) PQCrypto 2013. LNCS, vol. 7932, pp. 231–242. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38616-9_16CrossRef

29.

Tsujii, S., Itoh, T., Fujioka, A., Kurosawa, K., Matsumoto, T.: Public-key cryptosystem based on the difficulty of solving a system of nonlinear equations. IEEE Xplore Electron. Lett. 23(11), 558–560 (1987)CrossRef

Titel: Multivariate Encryption Schemes Based on the Constrained MQ Problem
verfasst von: Takanori Yasuda
Verlag: Springer International Publishing
Buch: Provable Security
Print ISBN: 978-3-030-01445-2

Electronic ISBN: 978-3-030-01446-9

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-030-01446-9_8

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"