kth order symmetric SAC Boolean functions and bisecting binomial coefficients

DOI10.1016/J.DAM.2005.02.006MaRDI QIDQ2387429zbMATH OpenOpenAlexFDO

Authors Yuan Li, Thomas W. Cusick

Publication date 2 September 2005

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2005.02.006

zbMATH Keywords

binomial coefficientBoolean functioncryptographystrict avalanche criterionsymmetric function

Mathematics Subject Classification ID

Factorials, binomial coefficients, combinatorial functions (05A10) Cryptography (94A60)

Review text

A Boolean function in \(n\) variables is said to satisfy SAC if complementing any one of the \(n\) input bits results in changing the output bit with probability one half and it satisfies the SAC of order \(k\), \(0\leq k\leq n-2\), if whenever \(k\) input bits are fixed arbitrarily, the resulting function of \(n-k\) variables satisfies the SAC. In this paper, based on bisecting binomial coefficients and S. Lloyd' s work, a method to find \(k\)th order symmetric SAC functions (SSAC(\(k\))) is described. Also, all the SSAC(\(k\)) \(n\)-variable functions for \(n\leq 30\), \(k=1,2,\ldots ,n-2\) are determined and for infinitely many \(n\), some nontrivial binomial coefficient bisections are given. Note that the existence of nontrivial bisections makes the problem to find all SSAC(\(k\)) functions very difficult.

Recommendations

• Publication:4934737
• Symmetric Boolean Functions
• Bounds on the number of functions satisfying the Strict Avalanche Criterion
• An upper bound on the number of functions satisfying the strict avalanche criterion
• scientific article; zbMATH DE number 16477

Cites work

• A note on a conjecture concerning symmetric resilient functions
• Counting binary functions with certain cryptographic properties
• Enumerating Boolean functions of cryptographic significance
• scientific article; zbMATH DE number 4179290 (Why is no real title available?)
• scientific article; zbMATH DE number 16477 (Why is no real title available?)
• scientific article; zbMATH DE number 67085 (Why is no real title available?)
• scientific article; zbMATH DE number 1394321 (Why is no real title available?)
• Maximum nonlinearity of symmetric Boolean functions on odd number of variables
• On the bent Boolean functions that are symmetric

Cited in

(13)

• Linear structures of symmetric functions over finite fields
• Generalized Walsh transforms of symmetric and rotation symmetric Boolean functions are linear recurrent
• A variation on bisecting the binomial coefficients
• Walsh-Hadamard transforms of generalized \(p\)-ary functions and \(C\)-finite sequences
• Bisecting binomial coefficients
• Generalized exponential sums and the power of computers
• Asymptotic behavior of perturbations of symmetric functions
• Certificate complexity and symmetry of nested canalizing functions
• Modular periodicity of exponential sums of symmetric Boolean functions
• Strict avalanche criterion over finite fields
• Short k-rotation symmetric Boolean functions
• On monomial dihedral symmetric Boolean functions
• Exploring confusion in product ciphers through regression analysis

This page was built for publication: \(k\)th order symmetric SAC Boolean functions and bisecting binomial coefficients

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2387429)