On the Nonlinearity of Discrete Logarithm in F_(2~n)

摘要

In this paper, we derive a lower bound to the nonlinearity of the discrete logarithm function in F_(2~n) extended to a bijection in F_2~n. This function is closely related to a family of S-boxes from F_2~n to F_2~m proposed recently by Feng, Liao, and Yang, for which a lower bound on the nonlinearity was given by Carlet and Feng. This bound decreases exponentially with m and is therefore meaningful and proves good nonlinearity only for S-boxes with output dimension m logarithmic to n. By extending the methods of Brandstatter, Lange, and Winterhof we derive a bound that is of the same magnitude. We computed the true nonlinearities of the discrete logarithm function up to dimension n = 11 to see that, in reality, the reduction seems to be essentially smaller. We suggest that the closing of this gap is an important problem and discuss prospects for its solution.