article

Multivariate public key cryptosystems from diophantine equations

Authors:

Raymond HeindlAuthors Info & Claims

Designs, Codes and Cryptography, Volume 67, Issue 1

Pages 1 - 18

https://doi.org/10.1007/s10623-011-9582-1

Published: 01 April 2013 Publication History

Abstract

Wang et al. introduced in (A medium-field multivariate public-key encryption scheme. Topics in Cryptology--CTRSA 2006: The Cryptographers' Track at the RSA Conference, 2006) a multivariate public key cryptosystem, called MFE cryptosystem, and it is appealing as it is based on a simple polynomial identity. Their system, however, was subsequently broken by Ding et al. in (High order linearization equation (hole) attack on multivariate public key cryptosystems. Public key cryptography--PKC 2007: 10th international conference on practice and theory in public-key cryptography, 2007a, -Invertible cycles for multivariate quadratic public key cryptography. Public key cryptography--PKC 2007: 10th international conference on practice and theory in public-key cryptography, 2007b). Inspired by their work, we present a more general framework for multivariate public key cryptosystems, which combines ideas from both triangular and oil-vinegar schemes. Within this framework, we propose a new public key cryptosystem based on a solution of a Diophantine equation over polynomial rings.

References

[1]

Barget M., Faugére J., Salvy B., Yang B.: Asymptotic expansion of the degree of regularity for semiregular systems of equations. Proceedings of MEGA'05: 8th International Symposium on Effective Methods in Algebraic Geometry (2005).

[2]

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

Digital Library

[3]

Courtois N., Kilmov A., Patarin J., Shamir A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. Advances in Cryptology--EUROCRYPT 2000: International Conference on the Theory and Application of Cryptographic Techniques. LNCS, vol. 1807, pp. 392-407. Springer, Heidelberg (2000).

[4]

Ding J., Schmidt D.: The new TTM implementation is not secure. Proceedings of International Workshop on Coding, Cryptography, and Combinatorics (CCC 2003), pp. 106-121 (2003).

[5]

Ding J., Schmidt D.: Rainbow, a new multivariate polynomial signature scheme. Applied Cryptography and Network Security: Third International Conference (ANCS 2005). LNCS, vol. 3531, pp. 164-175. Springer, Heidelberg (2005).

[6]

Ding J., Hu L., Nie X., Li J., Wagner J.: High order linearization equation (hole) attack on multivariate public key cryptosystems. Public Key Cryptography--PKC 2007: 10th International Conference on Practice and Theory in Public-Key Cryptography. LNCS, vol. 4450, pp. 233-248. Springer, Heidelberg (2007a).

[7]

Ding J., Wolf C., Yang B.: l -Invertible cycles for multivariate quadratic public key cryptography. Public Key Cryptography--PKC 2007: 10th International Conference on Practice and Theory in Public-Key Cryptography. LNCS, vol. 4450, pp. 266-281. Springer, Heidelberg (2007b).

[8]

Faugére J.: A new efficient algorithm for computing Gröbner bases ( F ₄). J. Pure Appl. Algebra 139 , 61-68 (1999).

[9]

Faugére J.: A new efficient algorithm for computing Gröbner bases without reduction to zero ( F ₅). ISSAC '02: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, pp. 75-83. ACM, New York (2002).

Digital Library

[10]

Gao S., Volny IV, F., Wang M.: A new algorithm for computing Grobner bases, preprint 2010. Available at http://www.math.clemson.edu/faculty/Gao/papers/gvw.pdf or http://eprint.iacr.org/2010/641.

[11]

Goubin L., Courtois N.: Cryptanalysis of the TTM cryptosystem. Advances in Cryptology--ASIACRYPT 2000: 6th International Conference on the Theory and Application of Cryptology and Information Security. LNCS, vol. 1976, pp. 44-57. Springer (2000).

[12]

Joux A., Kunz-Jacques S., Muller F., Ricordel P.: Cryptanalysis of the Tractable Rational Map Cryptosystem. Public Key Cryptography--PKC 2005: 8th International Workshop on Theory and Practice in Public Key Cryptography. LNCS, vol. 3386, 258-274. Springer, Heidelberg (2005).

[13]

Kipnis A., Shamir A.: Cryptanalysis of the oil and vinegar signature scheme. Advances in Cryptology-- CRYPTO '98: 18th Annual International Cryptology Conference. LNCS, vol. 1462, pp. 257-266. Springer, Heidelberg (1998).

[14]

Kipnis A., Patarin J., Goubin L.: Unbalanced oil and vinegar signature schemes. Advances in Cryptology-- EUROCRYPT '99: International Conference on the Theory and Application of Cryptographic Techniques. LNCS, vol. 1592, pp. 206-222. Springer, Heidelberg (1999).

[15]

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

[16]

Moh T.: Two new examples of TTM. Cryptology ePrint Archive, Report 2007/144. http://eprint.iacr.org (2007).

[17]

Moh T., Chen J., Yang B.: Building instances of TTM immune to the Goubin-Courtois attack and the Ding-Schmidt attack. Cryptology ePrint Archive, Report 2004/168. http://eprint.iacr.org (2004).

[18]

Nie X., Jiang X., Hu L., Ding J.: Cryptanalysis of two new instances of TTM Cryptosystem. Cryptology ePrint Archive, Report 2007/381. http://eprint.iacr.org (2007).

[19]

Patarin J.: Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt '88. Advances in Cryptology--CRYPTO '95: 15th Annual International Cryptology Conference. LNCS, vol. 963, pp. 248-261. Springer, Heidelberg (1995).

[20]

Patarin J.: The oil and vinegar signature scheme. Presented at the Dagstuhl Workshop on Cryptography (1997).

[21]

Shor P.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26 (5), 1484-1509 (1997).

Digital Library

[22]

Wang L., Chang F.: Revision of tractable rational map cryptosystem. Cryptology ePrint Archive, Report 2004/046. http://eprint.iacr.org (2004).

[23]

Wang L., Yang B., Hu Y., Lai F.: A medium-field multivariate public-key encryption scheme. Topics in Cryptology--CT-RSA 2006: The Cryptographers' Track at the RSA Conference 2006. LNCS, vol. 3860, pp. 132-149. Springer, Heidelberg (2006).

[24]

Yang B., Chen J.: TTS: Rank attacks in tame-like multivariate PKCs. Cryptology ePrint Archive, Report 2004/061. http://eprint.iacr.org (2004).

[25]

Yang B., Chen J.: Building secure tame-like multivariate public-key cryptosystems: the new TTS. Information Security and Privacy: 10th Australasian Conference (ACISP 2005). LNCS, vol. 3574, pp. 518-531. Springer, Heidelberg (2005).

Cited By

Osipyan VLitvinov KBurnap PElçi ARana OReinecke PMoradpoor NTheodorakopoulos GKarabina K(2018)A mathematical model of the cryptosystem based on the linear Diophantine equationProceedings of the 11th International Conference on Security of Information and Networks10.1145/3264437.3264464(1-4)Online publication date: 10-Sep-2018
https://dl.acm.org/doi/10.1145/3264437.3264464
Yi H(2018)Towards Wearability in Cryptographic SystemsWireless Personal Communications: An International Journal10.1007/s11277-017-5206-z102:2(1471-1484)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s11277-017-5206-z

Multivariate public key cryptosystems from diophantine equations

Recommendations

Chosen ciphertext secure keyed-homomorphic public-key cryptosystems

In homomorphic encryption schemes, anyone can perform homomorphic operations, and therefore, it is difficult to manage when, where and by whom they are performed. In addition, the property that anyone can "freely" perform the operation inevitably means ...
Securely combining public-key cryptosystems
CCS '01: Proceedings of the 8th ACM conference on Computer and Communications Security

It is a maxim of sound computer-security practice that a cryptographic key should have only a single use. For example, an RSA key pair should be used only for public-key encryption or only for digital signatures, and not for both.In this paper we show ...
Lattice-based completely non-malleable public-key encryption in the standard model

An encryption scheme is non-malleable if giving an encryption of a message to an adversary does not increase its chances of producing an encryption of a related message (under a given public key). Fischlin introduced a stronger notion, known as complete ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Designs, Codes and Cryptography

Designs, Codes and Cryptography Volume 67, Issue 1

April 2013

152 pages

ISSN:0925-1022

Issue’s Table of Contents

Copyright © Copyright © 2013 Springer Science+Business Media New York.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 April 2013

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Osipyan VLitvinov KBurnap PElçi ARana OReinecke PMoradpoor NTheodorakopoulos GKarabina K(2018)A mathematical model of the cryptosystem based on the linear Diophantine equationProceedings of the 11th International Conference on Security of Information and Networks10.1145/3264437.3264464(1-4)Online publication date: 10-Sep-2018
https://dl.acm.org/doi/10.1145/3264437.3264464
Yi H(2018)Towards Wearability in Cryptographic SystemsWireless Personal Communications: An International Journal10.1007/s11277-017-5206-z102:2(1471-1484)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s11277-017-5206-z

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents