Highly nonlinear s-boxes with reduced bound on maximum correlation (extended abstract)
Khoongming Khoo, Guang Gong · 2003
In this paper, we consider S-boxes with n (odd) input bits and m ≥ 2 output bits as combiners in stream cipher systems. We construct two classes of balanced S-boxes with nonlinearity 2 n−1 − 2 (n−1)/2 for protection against correlation and linear approximation attacks. However, having a high nonlinearity may not be sufficient for security. Zhang and Chan [3] considered a more general correlation attack by using a nonlinear function of output bits. In this case, we will require the maximum correlation coefficients to be low in order to protect against their attack. They proved an upper bound for maximum correlation that is low for functions with high nonlinearity. We improve their result for our S-boxes by reducing their upper bound by a factor of √ 2. Thus, our S-boxes are more secure against general correlation attacks. Besides