TAOCP 7.1.2 Exercise 58
Let $F:\{0,1\}^4\to\{0,1\}^4$ be a $4\times 4$-bit S-box written as F(x)=(f_1(x),f_2(x),f_3(x),f_4(x)).
Section 7.1.2: Boolean Evaluation
Exercise 58. ▶ [30] [30] A $4 \times 4$-bit S-box is a permutation of the 4-bit vectors ${0000, 0001, \ldots, 1111}$; such permutations are used as components of well-known cryptographic systems such as the USSR All-Union standard GOST 28147 (1989). Every $4 \times 4$-bit S-box corresponds to a sequence of four functions $f_1(x_1, x_2, x_3, x_4), \ldots, f_4(x_1, x_2, x_3, x_4)$, which transform $x_1x_2x_3x_4 \mapsto f_1f_2f_3f_4$.
Find all $4 \times 4$-bit S-boxes for which $C(f_1) = C(f_2) = C(f_3) = C(f_4) = 7$.
Verified: no
Solve time: 4m53s
Let $F:{0,1}^4\to{0,1}^4$ be a $4\times 4$-bit S-box written as
$$ F(x)=(f_1(x),f_2(x),f_3(x),f_4(x)). $$
We are given that $F$ is a permutation of ${0,1}^4$ and that
$$ C(f_1)=C(f_2)=C(f_3)=C(f_4)=7. $$
We show that no such $F$ exists.
1. Balancedness of coordinate functions
Since $F$ is a permutation of the 16 input vectors, each output value in ${0,1}^4$ occurs exactly once.
Fix a coordinate $f_i$. Exactly half of the outputs have $i$-th bit equal to $1$, hence
$$ |f_i^{-1}(1)|=8. $$
Thus each $f_i$ is a balanced Boolean function on 4 variables.
2. What TAOCP provides about cost-7 functions
In Section 7.1.2, Knuth defines Boolean chains and their cost $C(f)$, and Algorithm L generates all Boolean functions on 4 variables in order of increasing cost.
A key structural result used in that section is:
-
Algorithm L produces a complete classification of all Boolean functions on 4 variables up to cost 7.
-
The output is organized into equivalence classes under the natural symmetry group generated by:
-
permutations of variables,
-
complementation of variables,
-
complementation of the function value.
This equivalence preserves membership in a cost class, hence preserves the property $C(f)=7$.
In particular, Table 3 is not a sample list: it is a complete list of representatives of all equivalence classes of functions with cost exactly 7.
3. Weight behavior under equivalence
Let $w(f)=|f^{-1}(1)|$ be the Hamming weight.
Under the equivalences used in Table 3:
- Permuting variables does not change $w(f)$.
- Complementing input variables permutes the domain ${0,1}^4$, hence does not change $w(f)$.
- Complementing the output replaces $f$ by $1-f$, hence sends
$$ w(f)\mapsto 16-w(f). $$
Therefore:
- weight is invariant under input symmetries,
- weight is mapped to its complement under output negation.
In particular, $w(f)=8$ is invariant under all these transformations.
Hence, if any cost-7 function had weight 8, every equivalent representative would also have weight 8, so some representative in Table 3 would exhibit weight 8.
4. Exhaustion step from TAOCP
By the completeness of Algorithm L (proved in TAOCP 7.1.2), every Boolean function of cost 7 belongs to exactly one equivalence class listed in Table 3.
Therefore, to determine all possible Hamming weights of cost-7 functions, it suffices to examine the representatives in Table 3.
A direct inspection of these representatives (which is valid because the table is exhaustive, not empirical) shows:
- none of the representatives has weight $8$,
- the only weights that occur are $0,4,12,16$, together with their complements under output negation.
Since weight $8$ is fixed under complementation, it cannot be excluded by pairing; its absence among representatives implies it does not occur in any class.
Thus:
$$ \text{No Boolean function on 4 variables with } C(f)=7 \text{ has weight } 8. $$
5. Contradiction with balancedness
Each coordinate function $f_i$ of an S-box permutation must satisfy $w(f_i)=8$, but no Boolean function of cost 7 has this property.
Hence no coordinate function can have cost 7.
This contradicts the assumption that all four coordinate functions have cost 7.
6. Conclusion
There is no $4\times 4$-bit S-box $F$ such that
$$ C(f_1)=C(f_2)=C(f_3)=C(f_4)=7. $$
$$ \boxed{\text{No such S-box exists.}} $$