An efficient algorithm for computing Boolean function expressions of S-boxes

This paper attempts to address the problem of Boolean function expression calculation of S-boxes in block ciphers, which has been the algebraic basis of construction and evaluation of the secure S-boxes. By adopting the swap memory method (SMM), an efficient algorithm is developed to generate the Boolean function expressions directly from the truth tables. The algorithm exhibits a number of advantages such as conceptual simplicity, memory economy and applicability in handling multi-output problems. Furthermore, the algorithm can be executed in a parallel manner. A complete example is studied to illustrate the efficiency of the algorithm.