Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Capacity and Data Complexity in Multidimensional Linear Attack
 
conference paper

Capacity and Data Complexity in Multidimensional Linear Attack

Huang, Jialin  
•
Vaudenay, Serge  
•
Lai, Xuejia
Show more
2015
Advances in Cryptology - {CRYPTO} 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part {I}
35th International Cryptology Conference

Multidimensional linear attacks are one of the most powerful variants of linear cryptanalytic techniques now. However, there is no knowledge on the key-dependent capacity and data complexity so far. Their values were assumed to be close to the average value for a vast majority of keys. This assumption is not accurate. In this paper, under a reasonable condition, we explicitly formulate the capacity as a Gamma distribution and the data complexity as an Inverse Gamma distribution, in terms of the average linear probability and the dimension. The capacity distribution is experimentally verified on the 5-round PRESENT. Regarding to complexity, we solve the problem of estimating the average data complexity, which was difficult to estimate because of the existence of zero correlations. We solve the problem of using the median complexity in multidimensional linear attacks, which is an open problem since proposed in Eurocrypt 2011. We also evaluate the difference among the median complexity, the average complexity and a lower bound of the average complexity -- the reciprocal of average capacity. In addition, we estimate more accurately the key equivalent hypothesis, and reveal the fact that the average complexity only provides an accurate estimate for less than half of the keys no matter how many linear approximations are involved. Finally, we revisit the so far best attack on PRESENT based on our theoretical result.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-662-47989-6_7
Web of Science ID

WOS:000364183000007

Author(s)
Huang, Jialin  
Vaudenay, Serge  
Lai, Xuejia
Nyberg, Kaisa
Date Issued

2015

Publisher

Springer

Publisher place

Berlin

Published in
Advances in Cryptology - {CRYPTO} 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part {I}
ISBN of the book

978-3-662-47989-6

978-3-662-47988-9

Total of pages

20

Series title/Series vol.

Lecture Notes in Computer Science

Volume

9215

Start page

141

Subjects

Multidimensional linear attack

•

Capacity

•

Data complexity

•

Linear hull effect

•

Linear probability

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LASEC  
Event nameEvent placeEvent date
35th International Cryptology Conference

Santa Barbara, CA, USA

August 16-20, 2015

Available on Infoscience
November 16, 2015
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/120605
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés