Advanced

Fast computation of large distributions and its cryptographic applications

Maximov, Alexander LU and Johansson, Thomas LU (2005) In Lecture Notes in Computer Science 3788. p.313-332
Abstract
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
large distributions, approximations, convolution, algorithms, cryptanalysis, complexity, pseudo-linear functions
in
Lecture Notes in Computer Science
volume
3788
pages
313 - 332
publisher
Springer
external identifiers
  • wos:000234879200017
  • scopus:33646803496
ISSN
1611-3349
DOI
10.1007/11593447
language
English
LU publication?
yes
id
c115a1e7-f531-4b42-9163-cc5047553492 (old id 209505)
date added to LUP
2007-08-13 13:51:47
date last changed
2017-04-16 03:30:32
@article{c115a1e7-f531-4b42-9163-cc5047553492,
  abstract     = {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.},
  author       = {Maximov, Alexander and Johansson, Thomas},
  issn         = {1611-3349},
  keyword      = {large distributions,approximations,convolution,algorithms,cryptanalysis,complexity,pseudo-linear functions},
  language     = {eng},
  pages        = {313--332},
  publisher    = {Springer},
  series       = {Lecture Notes in Computer Science},
  title        = {Fast computation of large distributions and its cryptographic applications},
  url          = {http://dx.doi.org/10.1007/11593447},
  volume       = {3788},
  year         = {2005},
}