International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Idempotents in the Neighbourhood of Patterson-Wiedemann Functions having Walsh Spectra Zeros

Authors:
Sumanta Sarkar
Subhamoy Maitra
Download:
URL: http://eprint.iacr.org/2007/427
Search ePrint
Search Google
Abstract: In this paper we study the neighbourhood of $15$-variable Patterson-Wiedemann (PW) functions, i.e., the functions that differ by a small Hamming distance from the PW functions in terms of truth table representation. We exploit the idempotent structure of the PW functions and interpret them as Rotation Symmetric Boolean Functions (RSBFs). We present techniques to modify these RSBFs to introduce zeros in the Walsh spectra of the modified functions with minimum reduction in nonlinearity. Our technique demonstrates 15-variable balanced and $1$-resilient functions with currently best known nonlinearities 16272 and 16264 respectively. In the process, we find functions for which the autocorrelation spectra and algebraic immunity parameters are best known till date.
BibTeX
@misc{eprint-2007-13707,
  title={Idempotents in the Neighbourhood of Patterson-Wiedemann Functions having Walsh Spectra Zeros},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / Boolean functions},
  url={http://eprint.iacr.org/2007/427},
  note={Extended version (new results are included) of WCC 07. subho@isical.ac.in 13858 received 14 Nov 2007, last revised 11 Dec 2007},
  author={Sumanta Sarkar and Subhamoy Maitra},
  year=2007
}