Linear attack using multiple linear approximations

Jun Choi, Deukjo Hong, Seokhie Hong, Sangjin Lee

Research output: Contribution to journalArticlepeer-review


One of Kaliski and Robshaw's algorithms, which is used for the linear attack on block ciphers with multiple linear approximations and introduced as Algorithm 2M in this paper, looks efficient but lacks any theoretical and mathematical description. It means there exists no way to estimate the data complexity required for the attack by the algorithm except experiments of the reduced variants. In this paper we propose a new algorithm using multiple linear approximation. We achieve the theoretical and mathematical analysis of its success probability. The new algorithm needs about 240.6 plaintexts to find 12 bits of secret key of 16-round DES with a success probability of about 86%.

Original languageEnglish
Pages (from-to)2-8
Number of pages7
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number1
Publication statusPublished - 2005 Jan


  • Block cipher
  • Linear cryptanalysis
  • Multiple linear cryptanalsis

ASJC Scopus subject areas

  • Signal Processing
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering
  • Applied Mathematics


Dive into the research topics of 'Linear attack using multiple linear approximations'. Together they form a unique fingerprint.

Cite this