Abstract
Advances in quantum computers pose great threats on the currently used public key cryptographic algorithms such as RSA and ECC. As a promising candidate secure against attackers equipped with quantum computational power, multivariate public key cryptosystems (MPKCs) have attracted increasing attention in recently years. Unfortunately, the existing MPKCs can only be used as a multivariate signature scheme, and it remains unknown how to construct an efficient MPKC enabling secure encryption. Furthermore, some multivariate signature schemes have been shown insecure in recent years, and it is also not trivial to build MPKC which can serve as a secure signature scheme. By employing the basic MQ-trapdoors, this paper proposes a novel MPKC and shows how it can be used as a multivariate signature scheme and a multivariate encryption scheme, respectively. The goal is achieved by incorporating our new hash authentication techniques and some modification methods such as the Shamir’s minus method. Thorough analysis shows that our schemes are secure and efficient. Our MPKC gives a positive response to the challenges in multivariate public key cryptography.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J Comput, 1997, 6: 1484–1509
Vandersypen L M K, Steffen M, Breyta G, et al. Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance. Nature, 2001, 414: 883–887
Guan H M. Progress in quantum computers abroad, information security challenges and countermeasures. Comput Secur, 2009, 4: 1–5
Fu X Q, Bao W S, Zhou C. Speeding up implementation for Shor’s factorization quantum. Chinese Sci Bull, 2010, 55: 322–327
Wu Q H, Mu Y, Susilo W, et al. Asymmetric group key agreement. In: Eurocrypt 2009, LNCS, Vol. 5479. Berlin: Springer-Verlag, 2009. 153–170
Wu Q H, Domingo-Ferrer J, González-Nicolás U. Balanced trustworthiness, safety and privacy in vehicle-to-vehicle communications. IEEE Trans Veh Technol, 2010, 2: 559–573
Li Y, Deng R, Wang X. The equivalence of McEliece’s and Niederreiter’s public-key cryptosystems. IEEE Trans Inf Theory, 1994, 44: 271–273
Garey M, Johnson D. Computers and Intractability, a Guide to the Theory of NP-Completeness. New York: Freeman, 1979. 128–130
Patarin J. Hidden field equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms. In: Proceedings of Eurocrypt 1996, LNCS, Vol. 1070. Berlin: Springer-Verlag, 1996. 33–48
Wolf C. Multivariate quadratic polynomials in public key cryptography. Katholieke Universiteit Leuven, 2005
Shamir A. Efficient signature schemes based on birational permutations. In: Proceedings of Crypto 1993, LNCS, Vol. 773. Berlin: Springer-Verlag, 1993. 1–12
Wang H Z, Zhang H G, Guan H M. Multivariate algebra theory and its application in cryptography. J Beijing Univ Technol, 2010, 5: 9–17
Coutrtois N T, Klimov A, Patarin J, et al. Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: Proceedings of Eurocrypt 2000, LNCS, Vol. 1807. Berlin: Springer-Verlag, 2000. 392–407
Faugere J C. A new efficient algorithm for computing Grobner bases without reduction to zero (F5). In: Proceedings of ISSAC 2002 LNCS, Vol. 2518. Berlin: Springer-Verlag, 2002. 75–83
Tang X J, Feng Y. Applying dixon resultants in cryptography. J Softw, 2007, 7: 1738–1745
Wang H Z, Zhang H G, et al. Design theory and method of multivariate hash function. Sci China Inf Sci, 2010, 53: 1977–1987
Merkle R C. A certified digital signature. In: Proceedings of CRYPTO1989. LNCS, Vol. 435. Berlin: Springer-Verlag, 1989. 218–238
Matsumoto T, Imai H. Public quadratic polynomial-tuples for efficient signature verification and message encryption. In: Proceedings of Eurocryp 1988, LNCS, Vol. 330. Berlin: Springer-Verlag, 1988. 419–453
Patarin J. Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt 1988. In: Proceedings of Crypto 1995, LNCS, Vol. 963. Berlin: Springer-Verlag, 1995. 248–261
Dubois V, Fouque P A, Shamir A, et al. Practical cryptanalysis of SFLASH. In: Proceedings of Crypto 2007, LNCS, Vol. 4622. Berlin: Springer-Verlag, 2007. 1–12
Wang H Z, Zhang H G, et al. A new perturbation algorithm and enhancing security of SFLASH signature scheme. Sci China Inf Sci, 2010, 53: 760–768
Akkar M, Courtois N. A fast and secure implementation of SFLASH. In: Proceedings of PKC 2003, LNCS, Vol. 2567. Berlin: Springer-Verlag, 2003. 267–278
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wang, H., Zhang, H., Wang, Z. et al. Extended multivariate public key cryptosystems with secure encryption function. Sci. China Inf. Sci. 54, 1161–1171 (2011). https://doi.org/10.1007/s11432-011-4262-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11432-011-4262-3