\(k\)th order symmetric SAC Boolean functions and bisecting binomial coefficients. (English) Zbl 1072.94023
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.
Reviewer: Ioan Tomescu (Bucureşti)
MSC:
| 94C10 | Switching theory, application of Boolean algebra; Boolean functions (MSC2010) |
| 94A60 | Cryptography |
| 05A10 | Factorials, binomial coefficients, combinatorial functions |
Keywords:
Boolean function; strict avalanche criterion; cryptography; symmetric function; binomial coefficientReferences:
| [1] | T.W. Cusick, Boolean functions satisfying a higher order strict avalanche criterion, Adv. in Cryptology, Eurocrypt. (1993) pp. 102-117.; T.W. Cusick, Boolean functions satisfying a higher order strict avalanche criterion, Adv. in Cryptology, Eurocrypt. (1993) pp. 102-117. · Zbl 0951.94506 |
| [2] | R. Forré, The strict avalanche criterion: spectral properties of boolean functions and an extended definition, Adv. in Cryptology, Crypto. (1988) pp. 450-468.; R. Forré, The strict avalanche criterion: spectral properties of boolean functions and an extended definition, Adv. in Cryptology, Crypto. (1988) pp. 450-468. · Zbl 0715.94018 |
| [3] | K. Gopalakrishnan, D.G. Hoffman, D.R. Stinson, A note on a conjecture concerning symmetric resilient functions, Information Process. Lett. 47 (1993) pp. 139-143.; K. Gopalakrishnan, D.G. Hoffman, D.R. Stinson, A note on a conjecture concerning symmetric resilient functions, Information Process. Lett. 47 (1993) pp. 139-143. · Zbl 0785.05007 |
| [4] | S. Lloyd, Counting functions satisfying a higher order strict avalanche criterion, Advances in Cryptology, Eurocrypt (1989) pp. 63-75.; S. Lloyd, Counting functions satisfying a higher order strict avalanche criterion, Advances in Cryptology, Eurocrypt (1989) pp. 63-75. · Zbl 0747.94014 |
| [5] | S. Lloyd, Characterising and counting functions satisfying the strict avalanche criterion of order \(n - 3\); S. Lloyd, Characterising and counting functions satisfying the strict avalanche criterion of order \(n - 3\) · Zbl 0763.94012 |
| [6] | Lloyd, S., Counting binary functions with certain cryptographic properties, J. Cryptology, 5, 107-131 (1992) · Zbl 0755.94007 |
| [7] | Maitra, S.; Sarkar, P., Maximum nonlinearity of symmetric boolean functions on odd number of variables, IEEE Trans. Inform. Theory, 48, 2626-2630 (2002) · Zbl 1062.94073 |
| [8] | Mitchell, C., Enumerating boolean functions of cryptographic significance, J. Cryptology, 2, 155-170 (1990) · Zbl 0705.94010 |
| [9] | Savicky, P., On the bent boolean functions that are symmetric, Europ. J. Comb., 15, 407-410 (1994) · Zbl 0797.94011 |
| [10] | A.F. Webster, S.E. Tavares, On the design of S-boxes, Advances in Cryptology, Crypto. (1985) pp. 523-534.; A.F. Webster, S.E. Tavares, On the design of S-boxes, Advances in Cryptology, Crypto. (1985) pp. 523-534. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
