Fast computation of large distributions and its cryptographic applications

Alexander Maximov, Thomas Johansson

Research output: Contribution to journalArticlepeer-review

21 Citations (SciVal)


Let X-1, X-2, ... , X-k be independent n bit random variables. If they have arbitrary distributions, we show how to compute distributions like Pr{X-1 circle plus X-2 circle plus (...) circle plus X-k} and Pr{X-1 boxed plus X-2 boxed plus (...) boxed plus X-k} in complexity O(kn2(n)). Furthermore, if X-1, X-2, ... X-k are uniformly distributed we demonstrate a large class of functions F(X-1, X-2, ... X-k), for which we can compute their distributions efficiently. These results have applications in linear cryptanalysis of stream ciphers as well as block ciphers. A typical example is the approximation obtained when additions modulo 2(n) are replaced by bitwise addition. The efficiency of such an approach is given by the bias of a distribution of the above kind. As an example, we give a new improved distinguishing attack on the stream cipher SNOW 2.0.
Original languageEnglish
Pages (from-to)313-332
JournalLecture Notes in Computer Science
Publication statusPublished - 2005

Subject classification (UKÄ)

  • Electrical Engineering, Electronic Engineering, Information Engineering


  • large distributions
  • approximations
  • convolution
  • algorithms
  • cryptanalysis
  • complexity
  • pseudo-linear functions


Dive into the research topics of 'Fast computation of large distributions and its cryptographic applications'. Together they form a unique fingerprint.

Cite this