On multidimensional linear cryptanalysis
Matsui’s Algorithms 1 and 2 with multiple approximations have been studied over 16 years. In CRYPTO’04, Biryukov et al. proposed a formal framework based on m statistically independent approximations. Started by Hermelin et al. in ACISP’08, a different approach was taken by studying m-dimensional co...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2012
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/94603 http://hdl.handle.net/10220/7711 |
| _version_ | 1826128681738698752 |
|---|---|
| author | Nguyen, Phuong Ha Wei, Lei Wang, Huaxiong Ling, San |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Nguyen, Phuong Ha Wei, Lei Wang, Huaxiong Ling, San |
| author_sort | Nguyen, Phuong Ha |
| collection | NTU |
| description | Matsui’s Algorithms 1 and 2 with multiple approximations have been studied over 16 years. In CRYPTO’04, Biryukov et al. proposed a formal framework based on m statistically independent approximations. Started by Hermelin et al. in ACISP’08, a different approach was taken by studying m-dimensional combined approximations from m base approximations. Known as multidimensional linear cryptanalysis, the requirement for statistical independence is relaxed. In this paper we study the multidimensional Alg. 1 of Hermelin et al.. We derive the formula for N, the number of samples required for the attack and we improve the algorithm by reducing time complexity of the distillation phase from 2m N to 2m2m + mN, and that of the analysis phase from 22m to 3m2m . We apply the results on 4- and 9-round Serpent and show that Hermelin et al. actually provided a formal model for the hypothesis of Biryukov et al. in practice, and this model is now much more practical with our improvements. |
| first_indexed | 2024-10-01T07:28:55Z |
| format | Journal Article |
| id | ntu-10356/94603 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T07:28:55Z |
| publishDate | 2012 |
| record_format | dspace |
| spelling | ntu-10356/946032023-02-28T19:31:09Z On multidimensional linear cryptanalysis Nguyen, Phuong Ha Wei, Lei Wang, Huaxiong Ling, San School of Physical and Mathematical Sciences DRNTU::Science::Mathematics Matsui’s Algorithms 1 and 2 with multiple approximations have been studied over 16 years. In CRYPTO’04, Biryukov et al. proposed a formal framework based on m statistically independent approximations. Started by Hermelin et al. in ACISP’08, a different approach was taken by studying m-dimensional combined approximations from m base approximations. Known as multidimensional linear cryptanalysis, the requirement for statistical independence is relaxed. In this paper we study the multidimensional Alg. 1 of Hermelin et al.. We derive the formula for N, the number of samples required for the attack and we improve the algorithm by reducing time complexity of the distillation phase from 2m N to 2m2m + mN, and that of the analysis phase from 22m to 3m2m . We apply the results on 4- and 9-round Serpent and show that Hermelin et al. actually provided a formal model for the hypothesis of Biryukov et al. in practice, and this model is now much more practical with our improvements. Accepted version 2012-04-11T01:11:58Z 2019-12-06T18:59:04Z 2012-04-11T01:11:58Z 2019-12-06T18:59:04Z 2010 2010 Journal Article Nguyen, P. H., Wei, L., Wang, H., & Ling, S. (2010). On multidimensional linear cryptanalysis. Lecture Notes in Computer Science, 6168, 37-52. https://hdl.handle.net/10356/94603 http://hdl.handle.net/10220/7711 10.1007/978-3-642-14081-5_3 en Lecture notes in computer science © 2010 Springer-Verlag Berlin Heidelberg. This is the author created version of a work that has been peer reviewed and accepted for publication by Lecture Notes in Computer Science, Springer-Verlag Berlin Heidelberg. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: http://dx.doi.org/10.1007/978-3-642-14081-5_3 16 p. application/pdf |
| spellingShingle | DRNTU::Science::Mathematics Nguyen, Phuong Ha Wei, Lei Wang, Huaxiong Ling, San On multidimensional linear cryptanalysis |
| title | On multidimensional linear cryptanalysis |
| title_full | On multidimensional linear cryptanalysis |
| title_fullStr | On multidimensional linear cryptanalysis |
| title_full_unstemmed | On multidimensional linear cryptanalysis |
| title_short | On multidimensional linear cryptanalysis |
| title_sort | on multidimensional linear cryptanalysis |
| topic | DRNTU::Science::Mathematics |
| url | https://hdl.handle.net/10356/94603 http://hdl.handle.net/10220/7711 |
| work_keys_str_mv | AT nguyenphuongha onmultidimensionallinearcryptanalysis AT weilei onmultidimensionallinearcryptanalysis AT wanghuaxiong onmultidimensionallinearcryptanalysis AT lingsan onmultidimensionallinearcryptanalysis |