Paper 2003/176

Patterson-Wiedemann Construction Revisited

S. Gangopadhyay, P. H. Keskar, and 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)$.

Note: This is a substantially revised version of the paper that has been presented in R. C. Bose Centenary Symposium on Discrete Mathematics and Applications, Indian Statistical Institute, Calcutta, December 2002.

Metadata
Available format(s)
PDF PS
Category
Secret-key cryptography
Publication info
Published elsewhere. Presented in R. C. Bose Centenary Symposium on Discrete Mathematics and Applications, Indian Statistical Institute, Calcutta, December 2002.
Keywords
Boolean functions
Contact author(s)
subho @ isical ac in
History
2003-08-28: received
Short URL
https://ia.cr/2003/176
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2003/176,
      author = {S.  Gangopadhyay and P.  H.  Keskar and S.  Maitra},
      title = {Patterson-Wiedemann Construction Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2003/176},
      year = {2003},
      note = {\url{https://eprint.iacr.org/2003/176}},
      url = {https://eprint.iacr.org/2003/176}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.