×

On the constructions of \(n\)-cycle permutations. (English) Zbl 1468.11234

Summary: Any permutation polynomial is an \(n\)-cycle permutation. When \(n\) is a specific small positive integer, one can obtain efficient permutations, such as involutions, triple-cycle permutations and quadruple-cycle permutations. These permutations have important applications in cryptography and coding theory. Inspired by the AGW Criterion, we propose criteria for \(n\)-cycle permutations, which mainly are of the form \(x^rh(x^s)\). We then propose unified constructing methods including recursive ways and a cyclotomic way for \(n\)-cycle permutations of such form. We demonstrate our approaches by constructing three classes of explicit triple-cycle permutations with high index and two classes of \(n\)-cycle permutations with low index, many of which are new both at levels of permutation property and cycle property.

MSC:

11T06 Polynomials over finite fields
05A05 Permutations, words, matrices

Software:

PRINCE
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Mullen, G. L.; Wang, Q., Permutation polynomials of one variable, (Handbook of Finite Fields (2014), CRC), 215-230
[2] Hou, X. D., Permutation polynomials over finite fields—a survey of recent advances, Finite Fields Appl., 32, 82-119 (2015) · Zbl 1325.11128
[3] Li, N.; Zeng, X., A survey on the applications of Niho exponents, Cryptogr. Commun., 11, 3, 1-40 (2018)
[4] Wang, Q., Polynomials over finite fields: an index approach, (Combinatorics and Finite Fields. Difference Sets, Polynomials, Pseudorandomness and Applications (2019), Degruyter), 319-348 · Zbl 1464.11130
[5] Akbary, A.; Ghioca, D.; Wang, Q., On constructing permutations of finite fields, Finite Fields Appl., 17, 1, 51-67 (2011) · Zbl 1281.11102
[6] Ding, C.; Qu, L.; Wang, Q.; Yuan, J.; Yuan, P., Permutation trinomials over finite fields with even characteristic, SIAM J. Discrete Math., 29, 1, 79-92 (2015) · Zbl 1352.11102
[7] Li, K.; Qu, L.; Chen, X., New classes of permutation binomials and permutation trinomials over finite fields, Finite Fields Appl., 43, 69-85 (2017) · Zbl 1351.11078
[8] Gupta, R.; Sharma, R., Some new classes of permutation trinomials over finite fields with even characteristic, Finite Fields Appl., 41, 89-96 (2016) · Zbl 1372.11108
[9] Li, N.; Helleseth, T., Several classes of permutation trinomials from Niho exponents, Cryptogr. Commun., 9, 6, 693-705 (2017) · Zbl 1369.11089
[10] Zha, Z.; Hu, L.; Fan, S., Further results on permutation trinomials over finite fields with even characteristic, Finite Fields Appl., 45, 43-52 (2017) · Zbl 1362.05006
[11] Cepak, N.; Charpin, P.; Pasalic, E., Permutations via linear translators, Finite Fields Appl., 45, 19-42 (2017) · Zbl 1376.12003
[12] Li, K.; Qu, L.; Li, C.; Fu, S., New permutation trinomials constructed from fractional polynomials, Acta Arith., 10, 6, 1023-1036 (2018) · Zbl 1419.11126
[13] Wu, D.; Yuan, P.; Ding, C.; Ma, Y., Permutation trinomials over \(\mathbb{F}_{2^m} \), Finite Fields Appl., 46, 38-56 (2017) · Zbl 1431.11131
[14] Xu, G.; Cao, X.; Ping, J., Some permutation pentanomials over finite fields with even characteristic, Finite Fields Appl., 49, 212-226 (2018) · Zbl 1392.11094
[15] Tu, Z.; Zeng, X., Two classes of permutation trinomials with Niho exponents, Finite Fields Appl., 53, 99-112 (2018) · Zbl 1392.05005
[16] Li, N., On two conjectures about permutation trinomials over \(\mathbb{F}_{3^{2 k}} \), Finite Fields Appl., 47, 1-10 (2017) · Zbl 1369.05007
[17] Li, K.; Qu, L.; Sun, B.; Li, C., New results about the boomerang uniformity of permutation polynomials, IEEE Trans. Inf. Theory, 65, 11, 7542-7553 (2019) · Zbl 1433.94088
[18] Niu, T.; Li, K.; Qu, L.; Wang, Q., A general method for finding the compositional inverses of permutations from the AGW criterion (2020), arXiv preprint
[19] Wu, B., The compositional inverse of a class of linearized permutation polynomials over \(\mathbb{F}_{2^n} \), n odd, Finite Fields Appl., 29, 34-48 (2014) · Zbl 1309.11085
[20] Wu, B.; Liu, Z., The compositional inverse of a class of bilinear permutation polynomials over finite fields of characteristic 2, Finite Fields Appl., 24, 136-147 (2013) · Zbl 1286.05005
[21] Tuxanidy, A.; Wang, Q., On the inverses of some classes of permutations of finite fields, Finite Fields Appl., 28, 244-281 (2014) · Zbl 1360.11134
[22] Li, K.; Qu, L.; Wang, Q., Compositional inverses of permutation polynomials of the form \(x^r h( x^s)\) over finite fields, Cryptogr. Commun., 11, 2, 279-298 (2019) · Zbl 1409.11125
[23] Niu, T.; Li, K.; Qu, L.; Wang, Q., New constructions of involutions over finite fields, Cryptogr. Commun., 12, 165-185 (2020) · Zbl 1459.11223
[24] Zheng, Y.; Wang, F.; Wang, L.; Wei, W., On inverses of some permutation polynomials over finite fields of characteristic three, Finite Fields Appl., 66, Article 101670 pp. (2020) · Zbl 1478.11148
[25] Daemen, J.; Rijmen, V., The Design of Rijndael: AES-the Advanced Encryption Standard (2013), Springer Science & Business Media · Zbl 1065.94005
[26] Barreto, P.; Rijmen, V., The Khazad legacy-level block cipher, NESSIE, 97 (2000), Primitive submitted to
[27] P. Barreto, V. Rijmen, The anubis block cipher, 2000, submission to the NESSIE project.
[28] Borghoff, J.; Canteaut, A.; Güneysu, T.; Kavun, E. B.; Knezevic, M.; Knudsen, L. R.; Leander, G.; Nikov, V.; Paar, C.; Rechberger, C.; Rombouts, P.; Thomsen, S. S.; Yalçin, T., PRINCE - a low-latency block cipher for pervasive computing applications - extended abstract, (Advances in Cryptology - ASIACRYPT 2012 - 18th International Conference on the Theory and Application of Cryptology and Information Security. Advances in Cryptology - ASIACRYPT 2012 - 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, December 2-6, 2012. Advances in Cryptology - ASIACRYPT 2012 - 18th International Conference on the Theory and Application of Cryptology and Information Security. Advances in Cryptology - ASIACRYPT 2012 - 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, December 2-6, 2012, Lecture Notes in Computer Science, vol. 7658 (2012), Springer), 208-225 · Zbl 1292.94035
[29] Mesnager, S., On constructions of bent functions from involutions, (2016 IEEE International Symposium on Information Theory (ISIT) (2016), IEEE), 110-114
[30] Coulter, R. S.; Mesnager, S., Bent functions from involutions over \(\mathbb{F}_{2^n} \), IEEE Trans. Inf. Theory, 64, 4, 2979-2986 (2018) · Zbl 1392.94966
[31] Gallager, R., Low-density parity-check codes, IRE Trans. Inf. Theory, 8, 1, 21-28 (1962) · Zbl 0107.11802
[32] Canteaut, A.; Roué, J., On the behaviors of affine equivalent S-boxes regarding differential and linear attacks, (Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015. Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Lecture Notes in Computer Science, Part I, vol. 9056 (2015), Springer), 45-74 · Zbl 1365.94411
[33] Charpin, P.; Mesnager, S.; Sarkar, S., Involutions over the Galois field \(\mathbb{F}_{2^n} \), IEEE Trans. Inf. Theory, 62, 4, 2266-2276 (2016) · Zbl 1359.94789
[34] Zheng, D.; Yuan, M.; Li, N.; Hu, L.; Zeng, X., Constructions of involutions over finite fields, IEEE Trans. Inf. Theory, 65, 12, 7876-7883 (2019) · Zbl 1433.11136
[35] Liu, X.; Chen, Y.; Xu, Y.; Sun, Z., Triple-cycle permutations over finite fields of characteristic two, Int. J. Found. Comput. Sci., 30, 2, 275-292 (2019) · Zbl 1415.05005
[36] Wu, M.; Li, C.; Wang, Z., Characterizations and constructions of triple-cycle permutations of the form \(x^r h( x^s)\), Des. Codes Cryptogr., 88, 10, 2119-2132 (2020) · Zbl 1465.11231
[37] Niederreiter, H.; Winterhof, A., Cyclotomic R-orthomorphisms of finite fields, Discrete Math., 295, 1-3, 161-171 (2005) · Zbl 1078.11068
[38] Akbary, A.; Ghioca, D.; Wang, Q., On permutation polynomials of prescribed shape, Finite Fields Appl., 15, 2, 195-206 (2009) · Zbl 1220.11145
[39] Wang, Q., Cyclotomic mapping permutation polynomials over finite fields, (Sequences, Subsequences, and Consequences, International Workshop. Sequences, Subsequences, and Consequences, International Workshop, SSC 2007, Los Angeles, CA, USA, May 31 - June 2, 2007. Sequences, Subsequences, and Consequences, International Workshop. Sequences, Subsequences, and Consequences, International Workshop, SSC 2007, Los Angeles, CA, USA, May 31 - June 2, 2007, Lecture Notes in Computer Science, vol. 4893 (2007), Springer: Springer Los Angeles, CA, USA), 119-128 · Zbl 1154.11342
[40] Cao, X.; Hu, L.; Zha, Z., Constructing permutation polynomials from piecewise permutations, Finite Fields Appl., 26, 162-174 (2014) · Zbl 1288.11109
[41] Park, Y. H.; Lee, J. B., Permutation polynomials and group permutation polynomials, Bull. Aust. Math. Soc., 63, 1, 67-74 (2001) · Zbl 0981.11039
[42] Zieve, M. E., On some permutation polynomials over \(\mathbb{F}_q\) of the form \(x^r h( x^{( q - 1 ) / d})\), Proc. Am. Math. Soc., 137, 7, 2209-2216 (2009) · Zbl 1228.11177
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.