zbMATH — the first resource for mathematics

Almost perfect nonlinear power functions on \(\mathrm{GF}(2^n)\): the Niho case. (English) Zbl 1072.94513
Summary: Almost perfect nonlinear (APN) mappings are of interest for applications in cryptography. We prove for odd \(n\) and the exponent \(d=2^{2r}+2^r-1\), where \(4r+1\equiv 0 \bmod n\), that the power functions \(x^d\) on \(\mathrm{GF}(2^n)\) is APN. The given proof is based on a new class of permutation polynomials which might be of independent interest. Our result supports a conjecture of Niho stating that the power function \(x^d\) is even maximally nonlinear or, in other terms, that the crosscorrelation function between a binary maximum-length linear shift register sequences of degree \(n\) and a decimation of that sequence by \(d\) takes on precisely the three values \(-1, -1\pm 2^{(n+1)/2}\).

94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
11T06 Polynomials over finite fields
94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
Full Text: DOI
[1] Beth, T.; Ding, C., On almost perfect nonlinear permutations, (), 65-76 · Zbl 0951.94524
[2] Chabaud, F.; Vaudenay, S., Links between differential and linear cryptanalysis, (), 356-365 · Zbl 0879.94023
[3] Cusick, T.; Dobbertin, H., Some new 3-valued crosscorrelation functions of binary m-sequences, IEEE trans. inf. theory, 42, 1238-1240, (1996) · Zbl 0855.94012
[4] Dobbertin, H., One-to-one highly nonlinear power functions on GF(2^n), Appl. algebra eng. commun. comput., 9, 139-152, (1998) · Zbl 0924.94026
[5] Dobbertin, H, Almost perfect nonlinear power functions on GF(2^n): The Welch case, IEEE Trans. Inf. Theory, to appear. · Zbl 0957.94021
[6] Dobbertin, H, Another proof for Kasami’s theorem, Design Codes Cryptogr, to appear. · Zbl 0941.94013
[7] Gold, R., Maximal recursive sequences with 3-valued recursive crosscorrelation functions, IEEE trans. inf. theory, 14, 154-156, (1968) · Zbl 0228.62040
[8] Helleseth, T.; Sandberg, D., Some power mappings with low differential uniformity, Appl. algebra eng. commun. comput., 8, 363-370, (1997) · Zbl 0886.11067
[9] Helleseth, T.,, Rong, C., and Sandberg, D., New families of almost perfect nonlinear power mappings, IEEE Trans. Inf. Theory, to appear. · Zbl 0960.11051
[10] Janwa, H.; Wilson, R.M., Hyperplane sections of Fermat varieties in P3 in characteristic 2 and some applications to cyclic codes, (), 180-194 · Zbl 0798.94012
[11] Kasami, T., The weight enumerators for several classes of subcodes of the second order binary Reed-muller codes, Information and control, 18, 369-394, (1971) · Zbl 0217.58802
[12] Lachaud, G.; Wolfmann, J., The weights of the orthogonals of the extended quadratic binary Goppa codes, IEEE trans. inf. theory, 36, 686-692, (1971) · Zbl 0703.94011
[13] Niho, Y., Multi-valued cross-correlation functions between two maximal linear recursive sequences, Dept. elec. eng., (1972), Univ. Southern California
[14] Nyberg, K., Differentially uniform mappings for cryptography, (), 55-64 · Zbl 0951.94510
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.