Fast computation of large distributions and its cryptographic applications

Summary, in English

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.

• Författare: Alexander Maximov; Thomas Johansson
• Avdelning/ar: Institutionen för elektro- och informationsteknik
• Publiceringsår: 2005
• Språk: Engelska
• Sidor: 313-332
• Publikation/Tidskrift/Serie: Lecture Notes in Computer Science
• Volym: 3788
• Länkar: http://dx.doi.org/10.1007/11593447
• Dokumenttyp: Artikel i tidskrift
• Förlag: Springer
• Ämne: Electrical Engineering, Electronic Engineering, Information Engineering
• Nyckelord: large distributions; approximations; convolution; algorithms; cryptanalysis; complexity; pseudo-linear functions
• Status: Published
• ISBN/ISSN/Övrigt: ISSN: 1611-3349