Approximation of a combining function by functions of fewer variables

Stream ciphers which combine several independent devices, such as combination generators or the recent Achterbahn proposal, are vulnerable to divide-and-conquer attacks. These attacks usually exploit an approximation of the combining function by a function of fewer variables. The accuracy of such an approximation is therefore an important parameter in the complexity of these attacks. In this context, we evaluate the correlations between a Boolean combining function and the functions depending on a small subset of its input variables. We notably show that the corresponding bias is upper-bounded by a quantity which depends on the nonlinearity of the function.

time info: arrival on Sunday, leave on Friday morning.

(C) 2007 University of Luxembourg

Original Version
VeryQuickWiki - HTML Export - Printable Version
Version: 2.7.1 (UniLux: 1.15.0 2006-01-19)
Modified: 2008-01-08 11:12:18
Exported: 2010-01-06 02:36:55