Improved algorithms in parallel evaluation of large cryptographic S-boxes. Issue 4 (3rd July 2020)

• Record Type: Journal Article
• Authors: Khadem, Behrooz; Ghasemi, Reza
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 35:Issue 4(2020)
• Page Start: 461
• Page End: 472
• Publication Date: 2020-07-03
• Subjects: S-boxes -- fast Walsh Hadamard transform -- non-linearity -- computational complexity -- implementation -- parallelisation; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2020.1760863
• Languages: English
• ISSNs: 1744-5760

Abstract

ABSTRACT: 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 ( 2 n + 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.