Improved algorithms in parallel evaluation of large cryptographic S-boxes
Behrooz Khadem, Reza Ghasemi · International Journal of Parallel Emergent and Distributed Systems · 2020
Nowadays computational complexity of fast Walsh Hadamard transform and non-linearity for Boolean functions and large cryptographic substitution boxes is a major challenge of modern cryptography research on strengthening encryption schemes against linear and differential attacks. Time and memory complexities of the best existing algorithm for computing fast Walsh Hadamard transform and non-linearity for n×m substitution boxes is O(2n+m). This paper proposes three new innovation in acceleration methods that improve the computation time for paralleled Walsh matrix up to 68 folds and the evaluation time for non-linearity degree up to 1021 folds. These methods include defining and accessing Walsh matrix transpose and combining an important part of evaluation process of non-linearity in the computation algorithm of Walsh matrix. The validity of the proposed algorithms is verified by means of simulation and experiments.The overall analysis of resource consumption of proposed algorithms is compared with previous ones.