**On the Maximum Nonlinearity of De Bruijn Sequence Feedback Function**

*Congwei Zhou and Bin Hu and Jie Guan*

**Abstract: **The nonlinearity of Boolean function is an important cryptographic criteria in the Best Affine Attack approach. In this paper, based on the definition of nonlinearity, we propose a new design index of nonlinear feedback shift registers. Using the index and the correlative necessary conditions of de Bruijn sequence feedback function, we prove that when $n \ge 9$, the maximum nonlinearity $Nl{(f)_{\max }}$ of arbitrary $n - $order de Bruijn sequence feedback function $f$ satisfies $3 \cdot {2^{n - 3}} - ({Z_n} + 1) < Nl{(f)_{\max }} \le {2^{n - 1}} - {2^{\frac{{n - 1}}{2}}}$ and the nonlinearity of de Bruijn sequence feedback function, based on the spanning tree of adjacency graph of affine shift registers, has a fixed value. At the same time, this paper gives the correlation analysis and practical application of the index.

**Category / Keywords: **foundations / Nonlinear feedback shift register, Nonlinearity, De Bruijn sequence, Feedback function, Adjacency graph

**Date: **received 7 Jul 2020

**Contact author: **zhoucongwei at qq com

**Available format(s): **PDF | BibTeX Citation

**Version: **20200712:122720 (All versions of this report)

**Short URL: **ia.cr/2020/835

[ Cryptology ePrint archive ]