Improving the algorithm 2 in multidimensional linear cryptanalysis

Phuong Ha Nguyen; Hongjun Wu; Huaxiong Wang

doi:10.1007/978-3-642-22497-3_5

Improving the algorithm 2 in multidimensional linear cryptanalysis

Phuong Ha Nguyen^*, Hongjun Wu, Huaxiong Wang

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

20 Citations (Scopus)

Abstract

In FSE'09 Hermelin et al. introduced the Algorithm 2 of multidimensional linear cryptanalysis. If this algorithm is m-dimensional and reveals l bits of the last round key with N plaintext-ciphertext pairs, then its time complexity is O(mN2^l). In this paper, we show that by applying the Fast Fourier Transform and Fast Walsh Hadamard Transform to the Algorithm 2 of multidimensional linear cryptanalysis, we can reduce the time complexity of the attack to O(N + λ2^m+l), where λ is 3(m + l) or 4m + 3l . The resulting attacks are the best known key recovery attacks on 11-round and 12-round Serpent. The data, time, and memory complexity of the previously best known attack on 12-round Serpent are reduced by factor of 2^7.5, 2^11.7, and 2^7.5, respectively. This paper also simulates the experiments of the improved Algorithm 2 in multidimensional linear cryptanalysis on 5-round Serpent.

Original language	English
Title of host publication	Information Security and Privacy
Subtitle of host publication	16th Australasian Conference, ACISP 2011, Melbourne, Australia, July 11-13, 2011. Proceedings
Editors	Udaya Parampalli, Philip Hawkes
Place of Publication	Heidelberg
Publisher	Springer, Springer Nature
Pages	61-74
Number of pages	14
ISBN (Electronic)	9783642224973
ISBN (Print)	9783642224966
DOIs	https://doi.org/10.1007/978-3-642-22497-3_5
Publication status	Published - 2011
Externally published	Yes
Event	16th Australasian Conference on Information Security and Privacy, ACISP 2011 - Melbourne, VIC, Australia Duration: 11 Jul 2011 → 13 Jul 2011

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Berlin Heidelberg
Volume	6812
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	16th Australasian Conference on Information Security and Privacy, ACISP 2011
Country/Territory	Australia
City	Melbourne, VIC
Period	11/07/11 → 13/07/11

Keywords

multidimensional linear cryptanalysis
linear cryptanalysis
serpent
Fast Fourier Transform
Fast Walsh Hadamard Transform

Access to Document

10.1007/978-3-642-22497-3_5

Cite this

Nguyen, P. H., Wu, H., & Wang, H. (2011). Improving the algorithm 2 in multidimensional linear cryptanalysis. In U. Parampalli, & P. Hawkes (Eds.), Information Security and Privacy: 16th Australasian Conference, ACISP 2011, Melbourne, Australia, July 11-13, 2011. Proceedings (pp. 61-74). (Lecture Notes in Computer Science; Vol. 6812). Springer, Springer Nature. https://doi.org/10.1007/978-3-642-22497-3_5

Nguyen, Phuong Ha ; Wu, Hongjun ; Wang, Huaxiong. / Improving the algorithm 2 in multidimensional linear cryptanalysis. Information Security and Privacy: 16th Australasian Conference, ACISP 2011, Melbourne, Australia, July 11-13, 2011. Proceedings. editor / Udaya Parampalli ; Philip Hawkes. Heidelberg : Springer, Springer Nature, 2011. pp. 61-74 (Lecture Notes in Computer Science).

@inproceedings{754149f7db924b23933fb0268087ee72,

title = "Improving the algorithm 2 in multidimensional linear cryptanalysis",

abstract = "In FSE'09 Hermelin et al. introduced the Algorithm 2 of multidimensional linear cryptanalysis. If this algorithm is m-dimensional and reveals l bits of the last round key with N plaintext-ciphertext pairs, then its time complexity is O(mN2l). In this paper, we show that by applying the Fast Fourier Transform and Fast Walsh Hadamard Transform to the Algorithm 2 of multidimensional linear cryptanalysis, we can reduce the time complexity of the attack to O(N + λ2m+l), where λ is 3(m + l) or 4m + 3l . The resulting attacks are the best known key recovery attacks on 11-round and 12-round Serpent. The data, time, and memory complexity of the previously best known attack on 12-round Serpent are reduced by factor of 27.5, 211.7, and 27.5, respectively. This paper also simulates the experiments of the improved Algorithm 2 in multidimensional linear cryptanalysis on 5-round Serpent.",

keywords = "multidimensional linear cryptanalysis, linear cryptanalysis, serpent, Fast Fourier Transform, Fast Walsh Hadamard Transform",

author = "Nguyen, {Phuong Ha} and Hongjun Wu and Huaxiong Wang",

year = "2011",

doi = "10.1007/978-3-642-22497-3_5",

language = "English",

isbn = "9783642224966",

series = "Lecture Notes in Computer Science",

publisher = "Springer, Springer Nature",

pages = "61--74",

editor = "Udaya Parampalli and Philip Hawkes",

booktitle = "Information Security and Privacy",

address = "United States",

note = "16th Australasian Conference on Information Security and Privacy, ACISP 2011 ; Conference date: 11-07-2011 Through 13-07-2011",

}

Nguyen, PH, Wu, H & Wang, H 2011, Improving the algorithm 2 in multidimensional linear cryptanalysis. in U Parampalli & P Hawkes (eds), Information Security and Privacy: 16th Australasian Conference, ACISP 2011, Melbourne, Australia, July 11-13, 2011. Proceedings. Lecture Notes in Computer Science, vol. 6812, Springer, Springer Nature, Heidelberg, pp. 61-74, 16th Australasian Conference on Information Security and Privacy, ACISP 2011, Melbourne, VIC, Australia, 11/07/11. https://doi.org/10.1007/978-3-642-22497-3_5

Improving the algorithm 2 in multidimensional linear cryptanalysis. / Nguyen, Phuong Ha; Wu, Hongjun; Wang, Huaxiong.
Information Security and Privacy: 16th Australasian Conference, ACISP 2011, Melbourne, Australia, July 11-13, 2011. Proceedings. ed. / Udaya Parampalli; Philip Hawkes. Heidelberg: Springer, Springer Nature, 2011. p. 61-74 (Lecture Notes in Computer Science; Vol. 6812).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Improving the algorithm 2 in multidimensional linear cryptanalysis

AU - Nguyen, Phuong Ha

AU - Wu, Hongjun

AU - Wang, Huaxiong

PY - 2011

Y1 - 2011

N2 - In FSE'09 Hermelin et al. introduced the Algorithm 2 of multidimensional linear cryptanalysis. If this algorithm is m-dimensional and reveals l bits of the last round key with N plaintext-ciphertext pairs, then its time complexity is O(mN2l). In this paper, we show that by applying the Fast Fourier Transform and Fast Walsh Hadamard Transform to the Algorithm 2 of multidimensional linear cryptanalysis, we can reduce the time complexity of the attack to O(N + λ2m+l), where λ is 3(m + l) or 4m + 3l . The resulting attacks are the best known key recovery attacks on 11-round and 12-round Serpent. The data, time, and memory complexity of the previously best known attack on 12-round Serpent are reduced by factor of 27.5, 211.7, and 27.5, respectively. This paper also simulates the experiments of the improved Algorithm 2 in multidimensional linear cryptanalysis on 5-round Serpent.

AB - In FSE'09 Hermelin et al. introduced the Algorithm 2 of multidimensional linear cryptanalysis. If this algorithm is m-dimensional and reveals l bits of the last round key with N plaintext-ciphertext pairs, then its time complexity is O(mN2l). In this paper, we show that by applying the Fast Fourier Transform and Fast Walsh Hadamard Transform to the Algorithm 2 of multidimensional linear cryptanalysis, we can reduce the time complexity of the attack to O(N + λ2m+l), where λ is 3(m + l) or 4m + 3l . The resulting attacks are the best known key recovery attacks on 11-round and 12-round Serpent. The data, time, and memory complexity of the previously best known attack on 12-round Serpent are reduced by factor of 27.5, 211.7, and 27.5, respectively. This paper also simulates the experiments of the improved Algorithm 2 in multidimensional linear cryptanalysis on 5-round Serpent.

KW - multidimensional linear cryptanalysis

KW - linear cryptanalysis

KW - serpent

KW - Fast Fourier Transform

KW - Fast Walsh Hadamard Transform

UR - http://www.scopus.com/inward/record.url?scp=79960242173&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-22497-3_5

DO - 10.1007/978-3-642-22497-3_5

M3 - Conference proceeding contribution

AN - SCOPUS:79960242173

SN - 9783642224966

T3 - Lecture Notes in Computer Science

SP - 61

EP - 74

BT - Information Security and Privacy

A2 - Parampalli, Udaya

A2 - Hawkes, Philip

PB - Springer, Springer Nature

CY - Heidelberg

T2 - 16th Australasian Conference on Information Security and Privacy, ACISP 2011

Y2 - 11 July 2011 through 13 July 2011

ER -

Nguyen PH, Wu H, Wang H. Improving the algorithm 2 in multidimensional linear cryptanalysis. In Parampalli U, Hawkes P, editors, Information Security and Privacy: 16th Australasian Conference, ACISP 2011, Melbourne, Australia, July 11-13, 2011. Proceedings. Heidelberg: Springer, Springer Nature. 2011. p. 61-74. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-22497-3_5

Improving the algorithm 2 in multidimensional linear cryptanalysis

Abstract

Publication series

Other

Keywords

Access to Document

Other files and links

Fingerprint

Cite this