Welcome to the resource topic for 2003/176
Title:
Patterson-Wiedemann Construction Revisited
Authors: S. Gangopadhyay, P. H. Keskar, S. Maitra
Abstract:In 1983, Patterson and Wiedemann constructed Boolean functions on
n = 15 input variables having nonlinearity strictly greater than
2^{n-1} - 2^{\frac{n-1}{2}}. Construction of Boolean functions on
odd number of variables with such high nonlinearity was not known earlier and also till date no other construction method of such functions are known. We note that the Patterson-Wiedemann construction can be understood in terms of interleaved sequences as introduced by Gong in 1995 and subsequently these functions can be described as repetitions of a particular binary string. As example we elaborate the cases for n = 15, 21. Under this framework, we map the problem of finding Patterson-Wiedemann functions into a problem of solving a system of linear inequalities over the set of integers and provide
proper reasoning about the choice of the orbits. This, in turn, reduces the search space. Similar analysis also reduces the complexity of calculating autocorrelation and generalized nonlinearity for such functions. In an attempt to understand the above construction from the group theoretic view point, we characterize the group of all GF(2)-linear transformations of GF(2^{ab}) which acts on PG(2,2^a).
ePrint: https://eprint.iacr.org/2003/176
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .