Systematization of Shuffling Countermeasures: With an Application to CRYSTALS-Dilithium

Abstract

Shuffling is an essential countermeasure employed during the implementation of cryptographic algorithms to mitigate vulnerabilities against side-channel attacks, regardless of the algorithm’s nature. However, a comprehensive and structured shuffling framework has yet to be established, resulting in the need for developers to create customized solutions adapted to their specific algorithmic or operational requirements. This research paper introduces an innovative and systematic shuffling framework, providing developers with a set of guidelines to effectively select suitable shuffling methodologies aligned with their specific objectives. Additionally, we illustrate the application of this framework to the CRYSTALS-Dilithium signature algorithm, a finalist in NIST’s Post-Quantum Cryptography (PQC) standardization process. By leveraging our framework, we devise shuffling countermeasures and present an extensive array of twelve shuffling schemes. For each scheme, shuffling schemes are applied universally to all operations involving any confidential data, regardless of existence of known attacks targeting corresponding data. We also measured the performance of implementations of our shuffling schemes, the minimal overhead is 12.4%.

Keywords

• Side-channel countermeasure
• hiding countermeasure
• shuffling countermeasure
• horizontal shuffling
• vertical shuffling