Abstract
In the theory of symmetric cipher design, criteria for the choice of Boolean functions with good behavior have been thoroughly studied. The character of these criteria is mainly statistiscal. We survey the often conflicting propoerties which are generally acknowledged, which shows the almost universal neglect of complexity-theoretic techniques. Of these, we propose the most prominent complexity measure concerning Boolean functions, to wit, boolean circuit complexity (BCC), as a means to assess Boolean function behavior in the context of symmetric algorithm design. The connection between BCC of the non-linear elements of a design and the pseudorandom stream generated with their help is shown by scrutiny of linear complexity profiles.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Siegenthaler, T.: Correlation-immunity of nonlinear combining functions for cryptographic applications. IEEE Transactions on Information Theory IT-30, 776–780 (1984)
Rueppel, R.A.: Analysis and Design of Stream Ciphers. Springer, Berlin (1986)
Rothaus, O.S.: On ”bent” functions. J. Comb. Theory, Ser. A 20, 300–305 (1976)
Meier, W., Staffelbach, O.: Nonlinearity criteria for cryptographic functions. In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol. 434, pp. 549–562. Springer, Heidelberg (1990)
Webster, A.F., Tavares, S.E.: On the design of S-boxes. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 523–534. Springer, Heidelberg (1986)
Preneel, B., Leekwijck, W.V., Linden, L.V., Govaerts, R., Vandewalle, J.: Propagation characteristics of Boolean functions. In: Damgård, I.B. (ed.) EUROCRYPT 1990. LNCS, vol. 473, pp. 161–173. Springer, Heidelberg (1991)
Zhang, K., Zheng, Y.: GAC—the criterion for global avalanche characteristics of cryptographic functions. The Journal of Universal Computer Science 1, 316 (1995)
Guo-Zhen, X., Massey, J.L.: A spectral characterization of correlation-immune combining functions. IEEE Transactions on Information Theory IT-34, 569–571 (1988)
Golomb, S.W.: On the classification of boolean functions. IEEE Transactions on Information Theory, 176–186 (1959)
Jansen, C.J.A., Boekee, D.E.: The shortest feedback shift register that can generate a given sequence. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 90–99. Springer, Heidelberg (1990)
Shannon, C.E.: Communication theory of secrecy systems. Bell System Technical Journal 28 (1949)
Lempel, A., Ziv, J.: On the complexity of finite sequences. IEEE Trans. Inf. Theory IT-22, 783–795 (1976)
Shannon, C.: The synthesis of two–terminal switching circuits. Bell System Technical Journal 28, 59–98 (1949)
Anderson, R., Biham, E., Knudsen, L.: Serpent: A proposal for the Advanced Encryption Standard. NIST AES proposal, National Institute for Standards and Technology, Gaithersburg, MD, USA (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cobas, J.D.G., Brugos, J.A.L. (2005). Complexity-Theoretical Approaches to the Design and Analysis of Cryptographical Boolean Functions. In: Moreno Díaz, R., Pichler, F., Quesada Arencibia, A. (eds) Computer Aided Systems Theory – EUROCAST 2005. EUROCAST 2005. Lecture Notes in Computer Science, vol 3643. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11556985_44
Download citation
DOI: https://doi.org/10.1007/11556985_44
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29002-5
Online ISBN: 978-3-540-31829-3
eBook Packages: Computer ScienceComputer Science (R0)