×

zbMATH — the first resource for mathematics

Nonlinearities of S-boxes. (English) Zbl 1122.94026
Authors’ abstract: We introduce an indicator of the non-balancedness of functions defined over Abelian groups, and deduce a new indicator, denoted by \(NB\), of the nonlinearity of such functions. We prove an inequality relating \(NB\) and the classical indicator \(NL\), introduced by Nyberg and studied by Chabaud and Vaudenay, of the nonlinearity of S-boxes. This inequality results in an upper bound on \(NL\) which unifies Sidelnikov-Chabaud-Vaudenay’s bound and the covering radius bound. We also deduce from bounds on linear codes three new bounds on \(NL\) that improve upon Sidelnikov-Chabaud-Vaudenay’s bound and the covering radius bound in many cases.

MSC:
94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
94B75 Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory
94B05 Linear codes, general
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Biham, E.; Shamir, A., Differential cryptanalysis of DES-like cryptosystems, J. cryptol., 4, 1, 3-72, (1991) · Zbl 0729.68017
[2] Carlet, C.; Charpin, P.; Zinoviev, V., Codes, bent functions and permutations suitable for DES-like cryptosystems, Designs codes cryptography, 15, 125-156, (1998) · Zbl 0938.94011
[3] Carlet, C.; Ding, C., Highly nonlinear mappings, J. complexity, 20, 205-244, (2004) · Zbl 1053.94011
[4] C. Carlet, S. Dubuc, On generalized bent and q-ary perfect nonlinear functions, in: D. Jungnickel, H. Niederreiter (Eds.), Finite Fields and Applications, Proceedings of Fq5, Springer, Berlin, 2000, pp. 81-94. · Zbl 1010.94549
[5] F. Chabaud, S. Vaudenay, Links between differential and linear cryptanalysis, in: Advances in Cryptology—EUROCRYPT’94, Lecture Notes in Computer Science, vol. 950, Springer, Berlin, 1995, pp. 356-365. · Zbl 0879.94023
[6] J.F. Dillon, Elementary Hadamard Difference sets, Ph.D. Thesis, University of Maryland, 1974. · Zbl 0346.05003
[7] Ling, S.; Xing, C., Coding theory, (2004), Cambridge University Press Cambridge
[8] MacWilliams, F.J.; Sloane, N.J., The theory of error-correcting codes, (1977), North Holland Amsterdam · Zbl 0369.94008
[9] M. Matsui, Linear cryptanalysis method for DES cipher, in: Advances in Cryptography—EUROCRYPT’93, Lecture Notes in Computer Science, vol. 765, Springer, Heidelberg, 1994, pp. 386-397. · Zbl 0951.94519
[10] K. Nyberg, Perfect non-linear S-boxes, in: Advances in Cryptology—EUROCRYPT’ 91, Lecture Notes in Computer Science, vol. 547, Springer, Heidelberg, 1992, pp. 378-386. · Zbl 0766.94012
[11] K. Nyberg, On the construction of highly nonlinear permutations, in: Advances in Cryptology—EUROCRYPT’ 92, Lecture Notes in Computer Science, vol. 658, Springer, Heidelberg, 1993, pp. 92-98. · Zbl 0794.94008
[12] K. Nyberg, Differentially uniform mappings for cryptography, in: Advances in Cryptography—EUROCRYPT’93, Lecture Notes in Computer Science, vol. 765, Springer, Heidelberg, 1994, pp. 55-64. · Zbl 0951.94510
[13] Patterson, N.J.; Wiedemann, D.H., The covering radius of the \([2^{15}, 16]\) reed – muller code is at least 16276, IEEE trans. inform. theory, IT-36, 2, 443, (1983) · Zbl 0505.94021
[14] Rothaus, O.S., On bent functions, J. combin. theory, 20A, 300-305, (1976) · Zbl 0336.12012
[15] Shannon, C.E., Communication theory of secrecy systems, Bell system tech. J., 28, 656-715, (1949) · Zbl 1200.94005
[16] Sidel’nikov, V.M., On the mutual correlation of sequences, Soviet math. dokl., 12, 197-201, (1971) · Zbl 0241.94008
[17] Wadayama, T.; Hada, T.; Wakasugi, K.; Kasahara, M., Upper and lower bounds on maximum nonlinearity of n-input m-output Boolean function, Designs, codes cryptography, 23, 23-33, (2001) · Zbl 1020.94016
[18] Welch, L., Lower bounds on the maximum cross correlation of signals, IEEE trans. inform. theory, IT-20, 3, 397-399, (1974) · Zbl 0298.94006
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.