Almost perfect nonlinear power functions on \(\mathrm{GF}(2^n)\): the Niho case.

*(English)*Zbl 1072.94513Summary: 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}\).

##### MSC:

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 |

PDF
BibTeX
XML
Cite

\textit{H. Dobbertin}, Inf. Comput. 151, No. 1--2, 57--72 (1999; Zbl 1072.94513)

Full Text:
DOI

##### References:

[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.