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.
canteaut.pdf