Palash Sarkar

Claude Carlet, Palash Sarkar

The nonlinear filter model is an old and well understood approach to the design of secure stream ciphers. Extensive research over several decades has shown how to attack stream ciphers based on this model and has identified the required security properties of the Boolean function used as the filtering function to resist such attacks. This led to the problem of constructing Boolean functions which provide adequate security \textit{and} at the same time are efficient to implement. Unfortunately, over the last two decades no fully satisfactory solutions to this problem appeared in the literature. The lack of good solutions has effectively led to the nonlinear filter model becoming more or less obsolete. This is a big loss to the cryptographic design toolkit, since the great advantages of the nonlinear filter model are its simplicity, well understood security and the potential to provide low cost solutions for hardware oriented stream ciphers. In this paper, we revive the nonlinear filter model by constructing appropriate Boolean functions which provide required security and are also efficient to implement. We put forward concrete suggestions of stream ciphers which are $κ$-bit secure against known types of attacks for $κ=80$, 128, 160, 192, 224 and 256. For the 80-bit and the 128-bit security levels, the gate count estimates of our proposals compare quite well to the famous ciphers Trivium and Grain-128a respectively, while for the 256-bit security level, we do not know of any other stream cipher design which has such a low gate count.

Aniruddha Biswas, Palash Sarkar

The influence of a variable is an important concept in the analysis of Boolean functions. The more general notion of influence of a set of variables on a Boolean function has four separate definitions in the literature. In the present work, we introduce a new definition of influence of a set of variables which is based on the auto-correlation function and develop its basic theory. Among the new results that we obtain are generalisations of the Poincaré inequality and the edge expansion property of the influence of a single variable. Further, we obtain new characterisations of resilient and bent functions using the notion of influence. We show that the previous definition of influence due to Fischer et. al. (2002) and Blais (2009) is half the value of the auto-correlation based influence that we introduce. Regarding the other prior notions of influence, we make a detailed study of these and show that each of these definitions do not satisfy one or more desirable properties that a notion of influence may be expected to satisfy.

Aniruddha Biswas, Palash Sarkar

We show (almost) separation between certain important classes of Boolean functions. The technique that we use is to show that the total influence of functions in one class is less than the total influence of functions in the other class. In particular, we show (almost) separation of several classes of Boolean functions which have been studied in the coding theory and cryptography from classes which have been studied in combinatorics and complexity theory.