Improving linear cryptanalysis of LOKI91 by probabilistic counting method

Kouichi Sakurai, Souichi Furuya

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Citations (Scopus)


We improve linear cryptanalysis by introducing a technique of probabilistic counting into the maximum likelihood stage. In the original linear cryptanalysis based on maximum likelihood method with deterministic counting, the number of effective key and text bits is a multiple of the number of bit involved in the input to some S-box. Then, when larger S-boxes are used, 2R-method and even the 1R-methods can become impractical just because the number of effective text and key bits become excessive. Though 2R-method is practical for attacking DES, existing examples of ciphers where 2R-method is impractical include LOKI91. We overcome this problem by selecting a part of the effective key bits and investigating the probabilistic behavior of the remained effective key bits. The previous attacks discusses deterministic evaluation of the given approximated formula only when all values of the effective text/key bits are known, while we compute the probability that the approximated formula with unknown inputs equals to zero. This extension of linear cryptanalysis make useful for 2R-attack on LOKI91, then improves the performance of previous attacks. Furthermore, we implemented some experiments of attacks on 4-round LOKI91, and confirmed the effectiveness of our method.

Original languageEnglish
Title of host publicationFast Software Encryption - 4th International Workshop, FSE 1997, Proceedings
EditorsEli Biham
PublisherSpringer Verlag
Number of pages20
ISBN (Print)3540632476, 9783540632474
Publication statusPublished - 1997
Event4th International Workshop on Fast Software Encryption, FSE 1997 - Haifa, Israel
Duration: Jan 20 1997Jan 22 1997

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other4th International Workshop on Fast Software Encryption, FSE 1997

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Improving linear cryptanalysis of LOKI91 by probabilistic counting method'. Together they form a unique fingerprint.

Cite this