A Public Key Cryptosystem Using a Group of Permutation Polynomials

Singh, Rajesh P.; Sarma, Bhaba K.; Saikia, Anupam

doi:10.2478/tmmp-2020-0013

Abstract

In this paper we propose an efficient multivariate encryption scheme based on permutation polynomials over finite fields. We single out a commutative group ℒ(q, m) of permutation polynomials over the finite field F_qm. We construct a trapdoor function for the cryptosystem using polynomials in ℒ(2, m), where m =2^k for some k ≥ 0. The complexity of encryption in our public key cryptosystem is O(m³) multiplications which is equivalent to other multivariate public key cryptosystems. For decryption only left cyclic shifts, permutation of bits and xor operations are used. It uses at most 5m²+3m – 4 left cyclic shifts, 5m² +3m + 4 xor operations and 7 permutations on bits for decryption.

References

[1] LIDL, R.—NIEDERREITER, H.: Finite Fields. Addision-Wesley, 1983.
Search in Google Scholar Back to article
[2] LIDL, R.— MULLEN, G. L.: When does a polynomial over a finite field permute the elements of the field?, The American Math. Monthly, 95 (1988), no. 3, 243–246.
Search in Google Scholar Back to article
[3] MATSUMOTO, T.—IMAI, H.: Public quadratic polynomial-tuples for efficient signature-verification and message-encryption.In: Advances in cryptology-Eurocrypt ’88 (Davos, 1988), Lecture Notes in Comput. Sci., Vol. 330, Springer-Verlag, 1988, pp. 419–453.
Search in Google Scholar Back to article
[4] LIDL, R.— MULLEN, G. L.: When does a polynomial over a finite field permute the elements of the field? II, Amer. Math. Monthly, 100 (1993), no. 1, 71–74.
Search in Google Scholar Back to article
[5] PATARIN, J.: Cryptanalysis of Matsumoto and Imai public key scheme of Eurocrypt ’88. In: Advances in Cryptology- Crypto ’95, Lecture Notes in Comput. Sci., Vol. 963, Springer-Verlag, Berlin, 1995, pp. 248–261.10.1007/3-540-44750-4_20
Search in Google Scholar Back to article
[6] PATARIN, J.: Hidden Field equations (HFE) and isomorphism of polynomials (IP): two new families of asymmetric algorithms.In: Advances in cryptology- Eurocrypt ’96, Lecture Notes in Comput. Sci., Vol. 1070, Springer-Verlag, Berlin, 1996, pp. 33–48.
Search in Google Scholar Back to article
[7] PATARIN, J.: Asymmetric cryptography with a hidden monomial. In: Advances in Cryptology-Crypto ’96, Lecture Notes in Comput. Sci., Vol. 1109, Springer-Verlag, Berlin, pp. 45–60, 1996.
Search in Google Scholar Back to article
[8] COX, D.—LITTLE, J.—O’SHEA, D.: Ideals, Varieties, and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra (2nd edition). Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1997.
Search in Google Scholar Back to article
[9] KOBLITZ, N.: Algebraic Aspects of Cryptography. Springer-Verlag, Berlin, 1998.10.1007/978-3-662-03642-6
Search in Google Scholar Back to article
[10] MOH, T. T.: A public key system with signature and master key functions, Commun. Algebra, 27(1999), no. 5, 2207–2222.
Search in Google Scholar Back to article
[11] KIPNIS, A.—SHAMIR, A.: Cryptanalysis of the HFE public key cryptosystem by relinearization.In: Advances in cryptology—CRYPTO ’99, Santa Barbara, CA, Lecture Notes in Comput. Sci., Vol. 1666, Springer, Berlin, pp. 19–30, 1999.
Search in Google Scholar Back to article
[12] KIPNIS, A.—PATARIN, J.—GOUBIN, L.: Unbalanced oil and vinegar signature scheme. In: EUROCRYPT 1999, Lecture Notes in Comput. Sci., Vol. 1592, Springer-Verlag, Berlin, 1999, pp. 206–222.
Search in Google Scholar Back to article
[13] GOUBIN, L.—COURTOIS, N. T.: Cryptanalysis of the TTM cryptosystem. In: Adv. Cryptol. ASIACRYPT, 2000, Lecture Notes in Comput. Sci., Vol. 1976, Springer-Verlag, Berlin, 2000. pp. 44–57,
Search in Google Scholar Back to article
[14] COURTOIS, N. T.—KLIMOV, A.—PATARIN, J.—SHAMIR, A.: Efficient algorithm for solving overdefined system of multivariate polynomial equations,In: EUROCRYPT 2000. Lecture Notes in Comput. Sci., Vol. 1807, Springer-Verlag, Berlin, 2001, pp. 392–407.
Search in Google Scholar Back to article
[15] COURTOIS, N. T.: The security of hidden field equations (HFE).In : CT-RSA 2001, Lecture Notes in Comput. Sci., Vol. 2020, Springer-Verlag, Berlin, 2001, pp. 266–281.
Search in Google Scholar Back to article
[16] PATARIN, J.—COURTOIS, N. T.—GOUBIN, L.: QUARTZ, 128-bit long digital signatures.In: CTRSA 2001, Lecture Notes in Comput. Sci., Vol. 2020, Springer-Verlag, Berlin, 2001, pp. 282-297.
Search in Google Scholar Back to article
[17] PATARIN, J.—COURTOIS, N. T.—GOUBIN, L.: FLASH, a fast multivariate signature algorithm.In: CT-RSA01 2001, Lecture Notes in Comput. Sci., Vol. 2020, Springer-Verlag, Berlin, 2001, pp. 298–307.
Search in Google Scholar Back to article
[18] FAUGÈRE, J.-C.: A new efficient algorithm for computing Gröbner bases (F4), J. Pure Appl. Algebra, 139(2002), 61–88.10.1016/S0022-4049(99)00005-5
Search in Google Scholar Back to article
[19] FAUGÈRE, J.-C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In: International Symposium on Symbolic and Algebraic Computation– –ISSAC 2002, ACM Press, New York, pp. 75–83.10.1145/780506.780516
Search in Google Scholar Back to article
[20] COURTOIS, N. T.—DAUM, M.—FELKE, P.: On the security of HFE, HFEv- and quartz.In: PKC 2003, Lecture Notes in Comput. Sci., Vol. 2567, Springer-Verlag, Berlin, 2003, pp. 337–350.
Search in Google Scholar Back to article
[21] FAUGERE, J.-C.—JOUX, A.: Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner basis.In: CRYPTO 2003, Lecture Notes in Comput. Sci., Vol. 2729, Springer-Verlag, Berlin, 2003, pp. 44–60,
Search in Google Scholar Back to article
[22] DING, J.: A new variant of the Matsumoto-Imai cryptosystem through perturbation. In: PKC04, Lecture Notes in Comput. Sci., Vol. 2947, Springer-Verlag, Berlin, 2004, pp. 305–318.
Search in Google Scholar Back to article
[23] FOUQUE, P.-A.—GRANBOULAN, L.—STERM, J.: Differential cryptanalysis for multivariate schemes.In: in EUROCRYPT 2005, Lecture Notes in Comput. Sci., Vol. 3494, Springer-Verlag, Berlin, 2005, pp. 341–353.
Search in Google Scholar Back to article
[24] DING, J.—SCHMIDT, D. S.: Rainbow, a new multivariate polynomial signature scheme. In: ACNS 2005, Lecture Notes in Comput. Sci., Vol. 3531, Springer-Verlag, Berlin, 2005, pp. 164–175.
Search in Google Scholar Back to article
[25] DING, J.—GOWER, J. E.—SCHMIDT, D. S.: Multivariate Public Key Cryptosystems, Springer-Verlag, Berlin, 2006.10.1090/conm/419/07997
Search in Google Scholar Back to article
[26] WANG, L.-C.—YANG, B.-Y.—HU, Y.-H.—LAI, F.: A medium-field multivariate public key encryption scheme.In: CT-RSA 2006: The Cryptographers Track at the RSA Conference 2006, Lecture Notes in Comput. Sci., Vol. 3860, Springer-Verlag, Berlin, 2006. pp. 132–149.
Search in Google Scholar Back to article
[27] DING, J.—HU, L.—NIE, X.—LI, J.—WAGNER, J.: High order linearization equation (HOLE) attack on multivariate public key cryptosystems.In: PKC 2007, Lecture Notes in Comput. Sci., Vol. 4450, Springer-Verlag, Berlin, 2007. pp. 233–248,
Search in Google Scholar Back to article
[28] DUBOIS, V.—FOUQUE, P.-A.—SHAMIR, A.—STERN, J.: Practical cryptanalysis of SFLASH.In: Advances in Cryptology-Crypto 2007, Lecture Notes in Comput. Sci., Vol. 4622, Springer-Verlag, Berlin, 2007, pp. 1–12.
Search in Google Scholar Back to article
[29] SINGH, R. P.—SARMA, B. K.—SAIKIA, A.: Public key cryptography using permutation P-polynomials over finite fields, Cryptology eprint archive, 2009/208, https://eprint.iacr.org/2009/208
Search in Google Scholar Back to article
[30] SINGH, R. P.—SAIKIA, A.—SARMA, B. K.: Little Dragon Two: An efficient multivariate public key cryptosystem, Int. J. Network Security and Appl, 2 (2010), no. 2, 1–10.
Search in Google Scholar Back to article
[31] SINGH, R. P.—SAIKIA, A.—SARMA, B. K.: Poly-dragon: an efficient multivariate public key cryptosystem, Journal of Mathematical Cryptology, 4 (2011), no. 4, 349–364.
Search in Google Scholar Back to article
[32] TAO, C.—DIENE, A.—TANG, S.—DING, J.: Simple-matrix scheme for encryption. In: PQCrypto 2013, Lecture Notes in Comput. Sci., Vol. 7932, Springer-Verlag, Berlin, 2013, pp. 231–242.
Search in Google Scholar Back to article
[33] PORRAS, J.—BAENA, J.—DING, J.: ZHFE, a new multivariate public key encryption scheme.In: PQCrypto 2014, Lecture Notes in Comput. Sci., Vol. 8772, Springer-Verlag, Berlin, 2014, pp. 229–245.
Search in Google Scholar Back to article
[34] PETZOLDT, A.—CHEN, M.-S.—YANG, B.-Y.—TAO, C.—DING, J.: Design principles for HFEv- based signature schemes.In:ASIACRYPT 2015 (Part I), Lecture Notes in Comput. Sci., Vol. 9452, Springer-Verlag, Berlin, 2015, pp. 311–334.
Search in Google Scholar Back to article
[35] TAO, C.—XIANG, H.—PETZOLDT, A.—DING, J.: Simple Matrix - a multivariate public key cryptosystem (MPKC) for encryption, Finite Fields Appl. 35 (2015), 352–368.10.1016/j.ffa.2015.06.001
Search in Google Scholar Back to article
[36] YASUDA, T.—SAKURAI, K.: A multivariate encryption scheme with Rainbow. In: ICISC 2015, Lecture Notes in Comput. Sci., Vol. 9543, Springer-Verlag, Berlin, 2015, pp. 222–236.
Search in Google Scholar Back to article
[37] CHUNSHENG, G.: Cryptanalysis of simple matrix scheme for encryption, Cryptology eprint archive, 2016/1075, https://eprint.iacr.org/2016/1075
Search in Google Scholar Back to article
[38] MOODY, D.—PERLNER, R.—SMITH-TONE, D.: Key recovery attack on the cubic ABC simple matrix multivariate encryption scheme.In: Selected Areas in Cryptography– –SAC 2016, Lecture Notes in Comput. Sci., Vol. 10532, Springer-Verlag, Berlin, 2016, pp. 543–558.
Search in Google Scholar Back to article
[39] MOODY, D.—PETZOLDT, A.—SMITH-TONE, D.: Key recovery attack on the cubic ABC simple matrix multivariate encryption scheme.In: Selected Areas in Cryptography– –SAC 2017, Lecture Notes in Comput. Sci., Vol. 10719, Springer-Verlag, Berlin, 2017, pp. 355–373.
Search in Google Scholar Back to article
[40] CABARCAS, D.—SMITH-TONE, D.—VERBEL, J. A.: Key recovery attack for ZHFE. In: PQCrypto 2017, Lecture Notes in Comput. Sci., Vol. 10346, Springer-Verlag, Berlin, 2017, pp. 289–308.
Search in Google Scholar Back to article
[41] DING, J.—PETZOLDT, A.: Current state of multivariate cryptography, IEEE Security and Privacy, 15 (2017), 28–36. (DOI: 10.1109/MSP.2017.3151328)
Search in Google Scholar Back to article

A Public Key Cryptosystem Using a Group of Permutation Polynomials

Abstract

Paradigm

My account