The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Fast computation of large distributions and its cryptographic applications

På svenska

Author

Summary, in English

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.

Publishing year

2005

Language

English

Pages

313-332

Publication/Series

Lecture Notes in Computer Science

Volume

3788

Document type

Journal article

Publisher

Springer

Topic

  • Electrical Engineering, Electronic Engineering, Information Engineering

Keywords

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

Status

Published

ISBN/ISSN/Other

  • ISSN: 1611-3349