Du är här

Fast computation of large distributions and its cryptographic applications

Författare:
Publiceringsår: 2005
Språk: Engelska
Sidor: 313-332
Publikation/Tidskrift/Serie: ADVANCES IN CRYPTOLOGY ASIACRYPT 2005
Volym: 3788
Dokumenttyp: Artikel
Förlag: SPRINGER-VERLAG BERLIN

Sammanfattning

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.

Disputation

Nyckelord

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

Övriga

Published
Yes
  • ISSN: 0302-9743

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

 

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen