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:
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}},
}