Fast computation of large distributions and its cryptographic applications
(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:
https://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, 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
- 2016-04-01 11:55:05
- date last changed
- 2023-09-01 12:17:37
@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}}, keywords = {{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}}, doi = {{10.1007/11593447}}, volume = {{3788}}, year = {{2005}}, }