A Compact and Parallel Swap-Based Shuffler Based on Butterfly Network and Its Complexity Against Side Channel Analysis

A prominent countermeasure against side-channel attacks, the hiding countermeasure , typically involves shuffling operations using a permutation algorithm. This is especially crucial in the era of Post-quantum Cryptography, where computational characteristics of lattice and code-based cryptography heighten the need for robust defenses. In this context, securely and efficiently generating permutations is critical for an algorithm’s overall security and performance. Among the various approaches, the Fisher-Yates shuffle is widely adopted due to its security and ease of implementation. However, it is limited by a complexity of \(\mathcal {O}(N)\) due to its sequential nature. In response, we propose a time-area tradeoff swap algorithm, \(\mathsf {FSS}\) , that leverages a Butterfly Network structure, achieving only \(\log (N)\) depth, \(\log (N)\) work, and \(\mathcal {O}(1)\) operation time in parallel. Our analysis calculates the maximum gain an attacker can achieve through butterfly operations with \(\log (N)\) depth from a side-channel analysis perspective. Notably, we derive a generalized formula for the attack complexity of higher-order side-channel attacks for arbitrary input sizes, utilizing the fractal structure of the butterfly network. Moreover, our research demonstrates the efficiency and security of this permutation approach across different platforms. We include practical implementation results on ASIC as well as on CPU and GPU architectures, which underscore the algorithm’s performance advantages and robustness across diverse hardware environments. Through this exploration, we show that efficient and secure permutations can indeed be achieved with minimal randomness requirements.