The Experts below are selected from a list of 53613 Experts worldwide ranked by ideXlab platform
Subhamoy Maitra - One of the best experts on this subject based on the ideXlab platform.
-
Balancedness and Correlation immunity of symmetric Boolean functions
Discrete Mathematics, 2007Co-Authors: Palash Sarkar, Subhamoy MaitraAbstract:AbstractNew subsets of symmetric balanced and symmetric Correlation Immune functions are identified. The method involves interesting relations on binomial coefficients and highlights the combinatorial richness of these classes. As a consequence of our constructive techniques, we improve upon the existing lower bounds on the cardinality of the above sets. We consider higher order Correlation Immune functions and show how to construct n-variable, third order Correlation Immune function for each perfect square n⩾9
-
results on rotation symmetric bent and Correlation Immune boolean functions
Fast Software Encryption, 2004Co-Authors: Pantelimon Stănică, Subhamoy Maitra, John A ClarkAbstract:Recent research shows that the class of Rotation Symmetric Boolean Functions (RSBFs), i.e., the class of Boolean functions that are invariant under circular translation of indices, is potentially rich in functions of cryptographic significance. Here we present new results regarding the Rotation Symmetric (rots) Correlation Immune (CI) and bent functions. We present important data structures for efficient search strategy of rots bent and CI functions. Further, we prove the nonexistence of homogeneous rots bent functions of degree ≥ 3o n a single cycle.
-
On Nonlinearity and AutoCorrelation Properties of Correlation Immune Boolean Functions
Journal of Information Science and Engineering, 2004Co-Authors: Subhamoy MaitraAbstract:In this paper we discuss the nonlinearity and autoCorrelation properties of Correlation Immune Boolean functions. First we provide a construction method for unbalanced, first order Correlation Immune Boolean functions on even an number of variables n ≥ 6. These functions achieve the currently best known nonlinearity of 22 2 1 2 22 n nn -+ . Then we provide a simple modification of these functions to get unbalanced Correlation Immune Boolean functions on an even number of variables n, with a nonlinearity of 2 n−1 -+ nn and a maximum possible algebraic degree of n − 1. Moreover, we present a detailed study on the Walsh spectra of these functions. Next we study the autoCorrelation values of Correlation Immune and resilient Boolean functions. We provide new lower bounds and related results on the absolute indicator and sum of square indicator of autoCorrelation values for low orders of Correlation immunity. Recently it has been show that the nonlinearity and algebraic degree of Correlation Immune and resilient functions can be optimized simultaneously. Our analysis shows that under such a scenario, the sum of square indicator also attains its minimum value. We also point out the weakness of two recursive construction techniques for resilient functions in terms of autoCorrelation values.
-
INDOCRYPT - AutoCorrelation Properties of Correlation Immune Boolean Functions
Lecture Notes in Computer Science, 2001Co-Authors: Subhamoy MaitraAbstract:In this paper we study the autoCorrelation values of Correlation Immune and resilient Boolean functions. We provide new lower bounds and related results on absolute indicator and sum of square indicator of autoCorrelation values for low orders of Correlation immunity. Recently it has been identified that the nonlinearity and algebraic degree ofthe Correlation Immune and resilient functions are optimized simultaneously. Our analysis shows that in such a scenario the sum of square indicator attains its minimum value too. We also point out the weakness of two recursive construction techniques for resilient functions in terms of autoCorrelation values.
-
new constructions of resilient and Correlation Immune boolean functions achieving upper bound on nonlinearity
Electronic Notes in Discrete Mathematics, 2001Co-Authors: Emir Pasalic, Subhamoy Maitra, Thomas Johansson, Palash SarkarAbstract:Abstract Recently, weight divisibility results on resilient and Correlation Immune Boolean functions have received a lot of attention. These results have direct consequences towards the upper bound on nonlinearity of resilient and Correlation Immune Boolean functions of certain order. Now the clear requirement in the design of resilient Boolean functions (which optimizes Siegenthaler's inequality) is to provide results which attain the upper bound on nonlinearity. Here we construct a 7-variable, 2-resilient Boolean function with nonlinearity 56. This solves the maximum nonlinearity issue for 7-variable functions with any order of resiliency. Using this 7-variable function, we also construct a 10-variable, 4-resilient Boolean function with nonlinearity 480. Construction of these two functions was posed as important open questions in Crypto 2000. Also, we provide methods to generate an infinite sequence of Boolean functions on n = 7 + 3i variables (i ≥ 0) with order of resiliency m = 2 + 2i, algebraic degree 4 + i and nonlinearity 2n-1 - 2m+1, which were not known earlier. We conclude with constructions of some unbalanced Correlation Immune functions of 5 and 6 variables which attain the upper bound on nonlinearity.
Palash Sarkar - One of the best experts on this subject based on the ideXlab platform.
-
Balancedness and Correlation immunity of symmetric Boolean functions
Discrete Mathematics, 2007Co-Authors: Palash Sarkar, Subhamoy MaitraAbstract:AbstractNew subsets of symmetric balanced and symmetric Correlation Immune functions are identified. The method involves interesting relations on binomial coefficients and highlights the combinatorial richness of these classes. As a consequence of our constructive techniques, we improve upon the existing lower bounds on the cardinality of the above sets. We consider higher order Correlation Immune functions and show how to construct n-variable, third order Correlation Immune function for each perfect square n⩾9
-
Spectral Domain Analysis of Correlation Immune and Resilient Boolean Functions
Finite Fields and Their Applications, 2002Co-Authors: Claude Carlet, Palash SarkarAbstract:We use a general property of Fourier transform to obtain direct proofs of recent divisibility results on the Walsh transform of Correlation Immune and resilient functions. Improved upper bounds on the nonlinearity of these functions are obtained from the divisibility results. We deduce further information on Correlation Immune and resilient functions. In particular, we obtain a necessary condition on the algebraic normal form of Correlation Immune functions attaining the maximum possible nonlinearity.
-
new constructions of resilient and Correlation Immune boolean functions achieving upper bound on nonlinearity
Electronic Notes in Discrete Mathematics, 2001Co-Authors: Emir Pasalic, Subhamoy Maitra, Thomas Johansson, Palash SarkarAbstract:Abstract Recently, weight divisibility results on resilient and Correlation Immune Boolean functions have received a lot of attention. These results have direct consequences towards the upper bound on nonlinearity of resilient and Correlation Immune Boolean functions of certain order. Now the clear requirement in the design of resilient Boolean functions (which optimizes Siegenthaler's inequality) is to provide results which attain the upper bound on nonlinearity. Here we construct a 7-variable, 2-resilient Boolean function with nonlinearity 56. This solves the maximum nonlinearity issue for 7-variable functions with any order of resiliency. Using this 7-variable function, we also construct a 10-variable, 4-resilient Boolean function with nonlinearity 480. Construction of these two functions was posed as important open questions in Crypto 2000. Also, we provide methods to generate an infinite sequence of Boolean functions on n = 7 + 3i variables (i ≥ 0) with order of resiliency m = 2 + 2i, algebraic degree 4 + i and nonlinearity 2n-1 - 2m+1, which were not known earlier. We conclude with constructions of some unbalanced Correlation Immune functions of 5 and 6 variables which attain the upper bound on nonlinearity.
-
A note on the spectral characterization of Correlation Immune Boolean functions
Information Processing Letters, 2000Co-Authors: Palash SarkarAbstract:We present a new proof of the Walsh transform characterization of Correlation Immune Boolean functions. Also we provide a simpler proof of the fundamental relation between order of Correlation immunity and algebraic degree of a Boolean function.
-
ACISP - Enumeration of Correlation Immune Boolean Functions
Information Security and Privacy, 1999Co-Authors: Subhamoy Maitra, Palash SarkarAbstract:We introduce new ideas to tackle the enumeration problem for Correlation Immune functions and provide the best known lower and upper bounds. The lower bound is obtained from sufficient conditions, which are essentially construction procedures for Correlation Immune functions. We obtain improved necessary conditions and use these to derive better upper bounds. Further, bounds are obtained for the set of functions which satisfy the four conditions of Correlation immunity, balancedness, nondegeneracy and nonaffinity. Our work clearly highlights the difficulty of exactly enumerating the set of Correlation Immune functions.
Claude Carlet - One of the best experts on this subject based on the ideXlab platform.
-
constructing low weight d th order Correlation Immune boolean functions through the fourier hadamard transform
IEEE Transactions on Information Theory, 2018Co-Authors: Claude Carlet, Xi ChenAbstract:The Correlation immunity of Boolean functions is a property related to cryptography, to error correcting codes, to orthogonal arrays (in combinatorics), and in a slightly looser way to sequences. Correlation-Immune Boolean functions (in short, CI functions) have the property of keeping the same output distribution when some input variables are fixed. They have been widely used as combiners in stream ciphers to allow resistance to the Siegenthaler Correlation attack. Very recently, a new use of CI functions has appeared in the framework of side channel attacks (SCA). To reduce the cost overhead of counter-measures to SCA, CI functions need to have low Hamming weights. This actually poses new challenges since the known constructions which are based on properties of the Walsh–Hadamard transform, do not allow to build unbalanced CI functions. In this paper, we propose constructions of low-weight $d$ th-order CI functions based on the Fourier–Hadamard transform, while the known constructions of resilient functions are based on the Walsh–Hadamard transform. These two transforms are closely related but the resulting constructions are very different. We first prove a simple but powerful result, which makes that one only need to consider the case where $d$ is odd in further research. Then, we investigate how constructing low Hamming weight CI functions through the Fourier–Hadamard transform (which behaves well with respect to the multiplication of Boolean functions). We use the characterization of CI functions by the Fourier–Hadamard transform and introduce a related general construction of CI functions by multiplication. By using the Kronecker product of vectors, we obtain more constructions of low-weight $d$ -CI Boolean functions. Furthermore, we present a method to construct low-weight d-CI Boolean functions by making additional restrictions on the supports built from the Kronecker product.
-
evolutionary approach for finding Correlation Immune boolean functions of order t with minimal hamming weight
TPNC 2015 Proceedings of the Fourth International Conference on Theory and Practice of Natural Computing - Volume 9477, 2015Co-Authors: Stjepan Picek, Sylvain Guilley, Claude Carlet, Domagoj Jakobovic, Julian F MillerAbstract:The role of Boolean functions is prominent in several areas like cryptography, sequences and coding theory. Therefore, various methods to construct Boolean functions with desired properties are of direct interest. When concentrating on Boolean functions and their role in cryptography, we observe that new motivations and hence new properties have emerged during the years. It is important to note that there are still many design criteria left unexplored and this is where Evolutionary Computation can play a distinct role. One combination of design criteria that has appeared recently is finding Boolean functions that have various orders of Correlation immunity and minimal Hamming weight. Surprisingly, most of the more traditionally used methods for Boolean function generation are inadequate in this domain. In this paper, we concentrate on a detailed exploration of several evolutionary algorithms and their applicability for this problem. Our results show that such algorithms are a viable choice when evolving Boolean functions with minimal Hamming weight and certain order of Correlation immunity. This approach is also successful in obtaining Boolean functions with several values that were known previously to be theoretically optimal, but no one succeeded in finding actual Boolean functions with such values.
-
GECCO - Correlation Immunity of Boolean Functions: An Evolutionary Algorithms Perspective
Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, 2015Co-Authors: Stjepan Picek, Claude Carlet, Domagoj Jakobovic, Julian F Miller, Lejla BatinaAbstract:Boolean functions are essential in many stream ciphers. When used in combiner generators, they need to have sufficiently high values of Correlation immunity, alongside other properties. In addition, Correlation Immune functions with small Hamming weight reduce the cost of masking countermeasures against side-channel attacks. Various papers have examined the applicability of evolutionary algorithms for evolving cryptographic Boolean functions. However, even when authors considered Correlation immunity, it was not given the highest priority. Here, we examine the effectiveness of three different EAs, namely, Genetic Algorithms, Genetic Programming (GP) and Cartesian GP for evolving Correlation Immune Boolean functions. Besides the properties of balancedness and Correlation immunity, we consider several other relevant cryptographic properties while maintaining the optimal trade-offs among them. We show that evolving Correlation Immune Boolean functions is an even harder objective than maximizing nonlinearity.
-
Spectral Domain Analysis of Correlation Immune and Resilient Boolean Functions
Finite Fields and Their Applications, 2002Co-Authors: Claude Carlet, Palash SarkarAbstract:We use a general property of Fourier transform to obtain direct proofs of recent divisibility results on the Walsh transform of Correlation Immune and resilient functions. Improved upper bounds on the nonlinearity of these functions are obtained from the divisibility results. We deduce further information on Correlation Immune and resilient functions. In particular, we obtain a necessary condition on the algebraic normal form of Correlation Immune functions attaining the maximum possible nonlinearity.
-
on the coset weight divisibility and nonlinearity of resilient and Correlation Immune functions
SETA, 2002Co-Authors: Claude CarletAbstract:Sarkar and Maitra have recently shown that, given any m-resilient function f on F 2 n , the Hamming distance between f and any affine function on F 2 n is divisible by 2m+1. We show that their result is a simple consequence of a recent characterization of resilient functions by means of their numerical normal forms. This characterization allows us to obtain a better divisibility bound, involving n, m and the algebraic degree d of the function. Smaller is d and/or m, stronger is our improvement. We show that our divisibility bound is tight for every positive n, every non-negative m ≤ n − 2 and every positive d ≤ n − m − 1. We deduce a bound on the nonlinearity of resilient functions involving n, m and d. This bound improves upon those given recently and independently by Sarkar and Maitra and by Tarannikov. We finally show that the same bound stands in the more general framework of m-th order Correlation-Immune functions, for sufficiently large m.
Alfredo Viola - One of the best experts on this subject based on the ideXlab platform.
-
Enumerative encoding of Correlation- Immune Boolean functions
2011Co-Authors: Nicolas Carrasco, Jean-marie Le Bars, Alfredo ViolaAbstract:Le Bars and Viola have recently proposed an innovative recursive decomposition of the first-order Correlation-Immune Boolean functions. Based on their work this paper presents the design of an enumerative encoding of these Boolean functions. This is the first enumerative encoding of a class of Boolean functions defined by a cryptographic property. In this paper we study three major milestones to do this encoding: the conceptual computational tree, the use of normal classes and signed permutations, and a dynamic selection of the decomposition. Our enumerative encoding algorithm is practicable up to 8 variables which is the best result we may expect due to the combinatorial explosion of the numbers of classes.
-
ITW - Enumerative encoding of Correlation Immune Boolean functions
2011 IEEE Information Theory Workshop, 2011Co-Authors: Nicolas Carrasco, Jean-marie Le Bars, Alfredo ViolaAbstract:Boolean functions are very important cryptographic primitives in stream or block ciphers. In order to be useful for cryptographic applications, these functions should satisfy some properties like high algebraic degree, high non linearity or being Correlation Immune. Since for most of the cryptographic criteria presented in the literature there is no complete characterization of the set of functions that optimally satisfy any of them, the possibility of finding an enumerative encoding of any such class of functions is extremely hard. In a recent paper Le Bars and Viola have presented an innovative recursive decomposition of the first order Correlation Immune Boolean functions. It is not a trivial task, however, to derive from this characterization an enumerative encoding. This paper presents an enumerative encoding for first order Correlation Immune functions. It provides the first enumerative encoding of a class of Boolean functions with cryptographic applications. The encoding naturally leads to efficient random generation algorithms. For example, we may construct, with uniform probability, any 1-resilient function (balanced first order Correlation Immune function) with 8 variables in less than 30 seconds, from a universe of around 1068 functions
-
equivalence classes of boolean functions for first order Correlation
IEEE Transactions on Information Theory, 2010Co-Authors: J Le M Bars, Alfredo ViolaAbstract:This paper presents a complete characterization of the first order Correlation Immune Boolean functions that includes the functions that are 1-resilient. The approach consists in defining an equivalence relation on the full set of Boolean functions with a fixed number of variables. An equivalence class in this relation, called a first-order Correlation class, provides a measure of the distance between the Boolean functions it contains and the Correlation-Immune Boolean functions. The key idea consists on manipulating only the equivalence classes instead of the set of Boolean functions. To achieve this goal, a class operator is introduced to construct a class with n variables from two classes of n - 1 variables. In particular, the class of 1-resilient functions on n variables is considered. An original and efficient method to enumerate all the Boolean functions in this class is proposed by performing a recursive decomposition of classes with less variables. A bottom up algorithm provides the exact number of 1-resilient Boolean functions with seven variables which is 23478015754788854439497622689296. A tight estimation of the number of 1-resilient functions with eight variables is obtained by performing a partial enumeration. It is conjectured that the exact complete enumeration for general n is intractable.
-
Equivalence Classes of Boolean Functions for
2010Co-Authors: Jean-marie Le Bars, Alfredo ViolaAbstract:This paper presents a complete characterization of the first order Correlation Immune Boolean functions that includes the functions that are -resilient. The approach consists in defining an equivalence relation on the full set of Boolean functions with a fixed number of variables. An equivalence class in this relation, called a first-order Correlation class, provides a measure of the distance between the Boolean functions it contains and the Correlation-Immune Boolean functions. The key idea consists on manipulating only the equivalence classes instead of the set of Boolean functions. To achieve this goal, a class operator is introduced to construct a class with variables from two classes of variables. In particular, the class of -resilient functions on variables is considered. An original and efficient method to enumerate all the Boolean functions in this class is proposed by performing a recursive decomposition of classes with less variables. A bottom up algorithm provides the exact number of -resilient Boolean functions with seven variables which is 23478015754788854439497622689296. A tight estimation of the number of -resilient functions with eight variables is obtained by performing a partial enumeration. It is conjectured that the exact complete enumeration for general is intractable.
Xian-mo Zhang - One of the best experts on this subject based on the ideXlab platform.
-
ICISC - New Results on Correlation Immunity
Lecture Notes in Computer Science, 2001Co-Authors: Yuliang Zheng, Xian-mo ZhangAbstract:The absolute indicator for GAC forecasts the overall avalanche characteristics of a cryptographic Boolean function. From a security point of view, it is desirable that the absolute indicator of a function takes as small a value as possible. The first contribution of this paper is to prove a tight lower bound on the absolute indicator of an mth-order Correlation Immune function with n variables, and to show that a function achieves the lower bound if and only if it is affine. The absolute indicator for GAC achieves the upper bound when the underlying function has a non-zero linear structure. Our second contribution is about a relationship between Correlation immunity and non-zero linear structures. The third contribution of this paper is to address an open problem related to the upper bound on the nonlinearity of a Correlation Immune function. More specifically, we prove that given any odd mth-order Correlation Immune function f with n variables, the nonlinearity of f, denoted by Nf, must satisfy Nf ? 2n-1 - 2m+1 for 1/2n - 1 ? m < 0.6n - 0.4 or f has a non-zero linear structure. This extends a known result that is stated for 0.6n - 0.4 ? m ? n - 2.
-
improved upper bound on the nonlinearity of high order Correlation Immune functions
Selected Areas in Cryptography, 2000Co-Authors: Yuliang Zheng, Xian-mo ZhangAbstract:It has recently been shown that when m > 1/2n - 1, the nonlinearity Nf of an mth-order Correlation Immune function f with n variables satisfies the condition of Nf ≤ 2n-1 - 2m, and that when m > 1/2n - 2 and f is a balanced function, the nonlinearity satisfies Nf ≤ 2n-1 - 2m+1. In this work we prove that the general inequality, namely Nf ≤ 2n-1 - 2m, can be improved to Nf ≤ 2n-1 - 2m+1 for m ≥ 0.6n - 0.4, regardless of the balance of the function. We also show that Correlation Immune functions achieving the maximum nonlinearity for these functions have close relationships with plateaued functions. The latter have a number of cryptographically desirable properties.
-
On constructions and nonlinearity of Correlation Immune functions
Advances in Cryptology — EUROCRYPT ’93, 1Co-Authors: Jennifer Seberry, Xian-mo Zhang, Yuliang ZhengAbstract:A Boolean function is said to be Correlation Immune if its output leaks no information about its input values. Such functions have many applications in computer security practices including the construction of key stream generators from a set of shift registers. Finding methods for easy construction of Correlation Immune functions has been an active research area since the introduction of the notion by Siegenthaler. In this paper we study balanced Correlation Immune functions using the theory of Hadamard matrices. First we present a simple method for directly constructing balanced Correlation Immune functions of any order. Then we prove that our method generates exactly the same set of functions as that obtained using a method by Camion, Carlet, Charpin and Sendrier. Advantages of our method over Camion et al's include (1) it allows us to calculate the nonlinearity, which is a crucial criterion for cryptographically strong functions, of the functions obtained, and (2) it enables us to discuss the propagation characteristics of the functions. Two examples are given to illustrate our construction method. Finally, we investigate methods for obtaining new Correlation Immune functions from known Correlation Immune functions. These methods provide us with a new avenue towards understanding Correlation Immune functions.
