Abstract
Nonlinearity criteria for Boolean functions are classified in view of their suitability for cryptographic design. The classification is set up in terms of the largest transformation group leaving a criterion invariant. In this respect two criteria turn out to be of special interest, the distance to linear structures and the distance to affine functions, which are shown to be invariant under all affine transformations. With regard to these criteria an optimum class of functions is considered. These functions simultaneously have maximum distance to affine functions and maximum distance to linear structures, as well as minimum correlation to affine functions. The functions with these properties are proved to coincide with certain functions known in combinatorial theory, where they are called bent functions. They are shown to have practical applications for block ciphers as well as stream ciphers. In particular they give rise to a new solution of the correlation problem.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
D. Chaum, J.-H. Evertse, “Cryptanalysis of DES with a reduced number of rounds”, Proceedings of Crypto’85, pp. 192–211.
G.D. Cohen, M.G. Karpovsky, H.F. Mattson, J.R. Schatz, “Covering radius-Survey and recent results”, IEEE Trans. Inform. Theory, Vol. IT-31, pp. 328–343, 1985.
J.-H. Evertse, “Linear structures in block ciphers”, Proceedings of Eurocrypt’87, pp. 249–256.
R. Forré, “The strict avalanche criterion: Spectral properties of Boolean functions and an extended definition”, Proceedings of Crypto’88.
S. Lang, “Algebra”, Addison-Wesley Publishing Company, 1971.
O.S. Rothaus, “On bent functions”, Journal of Combinatorial Theory (A), Vol. 20, pp. 300–305, 1976.
R.A. Rueppel, “Analysis and design of stream ciphers”, Springer-Verlag, 1986.
C.E. Shannon, “Communications theory of secrecy systems”, Bell Sys. Tech. Journal, Vol. 28, pp. 656–715, 1949.
T. Slegenthaler, “Correlation-immunity of nonlinear combining functions for cryptographic applications”, IEEE Trans. Inform. Theory, Vol. IT-30, pp. 776–780, 1984.
T. Siegenthaler, “Cryptanalysts representation of nonlinearly filtered ML-sequences”, Proceedings of Eurocrypt’85, pp. 103–110.
A.F. Webster, S.E. Tavares, “On the design of S-boxes”, Proceedings of Crypto’85, pp. 523–534.
G.Z. Xiao, J.L. Massey, “A spectral characterization of correlation-immune combining functions”, IEEE Trans. Inform. Theory, Vol IT-34, pp. 569–571, 1988.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1990 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Meier, W., Staffelbach, O. (1990). Nonlinearity Criteria for Cryptographic Functions. In: Quisquater, JJ., Vandewalle, J. (eds) Advances in Cryptology — EUROCRYPT ’89. EUROCRYPT 1989. Lecture Notes in Computer Science, vol 434. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46885-4_53
Download citation
DOI: https://doi.org/10.1007/3-540-46885-4_53
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-53433-4
Online ISBN: 978-3-540-46885-1
eBook Packages: Springer Book Archive