Fast computation of large distributions and its cryptographic applications
(2005) In Lecture Notes in Computer Science 3788. p.313332 Abstract
 Let X1, X2, ... , Xk be independent n bit random variables. If they have arbitrary distributions, we show how to compute distributions like Pr{X1 circle plus X2 circle plus (...) circle plus Xk} and Pr{X1 boxed plus X2 boxed plus (...) boxed plus Xk} in complexity O(kn2(n)). Furthermore, if X1, X2, ... Xk are uniformly distributed we demonstrate a large class of functions F(X1, X2, ... Xk), 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 X1, X2, ... , Xk be independent n bit random variables. If they have arbitrary distributions, we show how to compute distributions like Pr{X1 circle plus X2 circle plus (...) circle plus Xk} and Pr{X1 boxed plus X2 boxed plus (...) boxed plus Xk} in complexity O(kn2(n)). Furthermore, if X1, X2, ... Xk are uniformly distributed we demonstrate a large class of functions F(X1, X2, ... Xk), 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:
http://lup.lub.lu.se/record/209505
 author
 Maximov, Alexander ^{LU} and Johansson, Thomas ^{LU}
 organization
 publishing date
 2005
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 large distributions, approximations, convolution, algorithms, cryptanalysis, complexity, pseudolinear functions
 in
 Lecture Notes in Computer Science
 volume
 3788
 pages
 313  332
 publisher
 Springer
 external identifiers

 wos:000234879200017
 scopus:33646803496
 ISSN
 16113349
 DOI
 10.1007/11593447
 language
 English
 LU publication?
 yes
 id
 c115a1e7f5314b429163cc5047553492 (old id 209505)
 date added to LUP
 20070813 13:51:47
 date last changed
 20170416 03:30:32
@article{c115a1e7f5314b429163cc5047553492, abstract = {Let X1, X2, ... , Xk be independent n bit random variables. If they have arbitrary distributions, we show how to compute distributions like Pr{X1 circle plus X2 circle plus (...) circle plus Xk} and Pr{X1 boxed plus X2 boxed plus (...) boxed plus Xk} in complexity O(kn2(n)). Furthermore, if X1, X2, ... Xk are uniformly distributed we demonstrate a large class of functions F(X1, X2, ... Xk), 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 = {16113349}, keyword = {large distributions,approximations,convolution,algorithms,cryptanalysis,complexity,pseudolinear functions}, language = {eng}, pages = {313332}, 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}, }