Abstract
We present an in-depth algorithmic study of the linear approximations of addition modulo 2n. Our results are based on a fairly simple classification of the linear approximations of the carry function. Using this classification, we derive an Θ(logn)-time algorithm for computing the correlation of linear approximation of addition modulo 2n, an optimal algorithm for generating all linear approximations with a given non-zero correlation coefficient, and determine the distribution of the correlation coefficients. In the generation algorithms, one or two of the selection vectors can optionally be fixed. The algorithms are practical and easy to implement.
Chapter PDF
Similar content being viewed by others
References
Aoki, K., Kobayashi, K., Moriai, S.: Best differential characteristic search for FEAL. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 41–53. Springer, Heidelberg (1997)
Biham, E., Shamir, A.: Differential Cryptanalysis of the Data Encryption Standard. Springer, Heidelberg (1993)
Chabaud, F., Vaudenay, S.: Links between differential and linear cryptanalysis. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 356–365. Springer, Heidelberg (1995)
Daemen, J.: Cipher and Hash Function Design: Methods Based on Linear and Differential Cryptanalysis. PhD thesis, Katholieke Universiteit Leuven (March 1995)
Lawler, E.L., Wood, D.E.: Branch-and-bound methods: a survey. Operations Research 14(4), 699–719 (1966)
Lipmaa, H.: On differential properties of Pseudo-Hadamard transform and related mappings. In: Menezes, A., Sarkar, P. (eds.) INDOCRYPT 2002. LNCS, vol. 2551, pp. 48–61. Springer, Heidelberg (2002)
Lipmaa, H., Moriai, S.: Efficient algorithms for computing differential properties of addition. In: Matsui, M. (ed.) FSE 2001. LNCS, vol. 2355, pp. 336–350. Springer, Heidelberg (2002)
Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994)
Matsui, M.: On correlation between the order of S-boxes and the strength of DES. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 366–375. Springer, Heidelberg (1995)
Matsui, M.: New structure of block ciphers with provable security against differential and linear cryptanalysis. In: Gollmann, D. (ed.) FSE 1996. LNCS, vol. 1039, pp. 205–218. Springer, Heidelberg (1996)
Miyano, H.: Addend dependency of differential/linear probability of addition. IEICE Trans. Fundamentals E81-A(1), 106–109 (1998)
Nyberg, K.: Linear approximations of block ciphers. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 439–444. Springer, Heidelberg (1995)
Vaudenay, S.: Provable security for block ciphers by decorrelation. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol. 1373, pp. 249–275. Springer, Heidelberg (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wallén, J. (2003). Linear Approximations of Addition Modulo 2n . In: Johansson, T. (eds) Fast Software Encryption. FSE 2003. Lecture Notes in Computer Science, vol 2887. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-39887-5_20
Download citation
DOI: https://doi.org/10.1007/978-3-540-39887-5_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20449-7
Online ISBN: 978-3-540-39887-5
eBook Packages: Springer Book Archive