Template Attack of LWE/LWR-Based Schemes with Cyclic Message Rotation

The side-channel security of lattice-based post-quantum cryptography has gained extensive attention since the standardization of post-quantum cryptography. Based on the leakage mechanism in the decapsulation stage of LWE/LWR-based post-quantum cryptography, a message recovery method, with templates and cyclic message rotation targeting the message decoding operation, was proposed. The templates were constructed for the intermediate state based on the Hamming weight model and cyclic message rotation was used to construct special ciphertexts. Using the power leakage during operation, secret messages in the LWE/LWR-based schemes were recovered. The proposed method was verified on CRYSTAL-Kyber. The experimental results demonstrated that this method could successfully recover the secret messages used in the encapsulation stage, thereby recovering the shared key. Compared with existing methods, the power traces required for templates and attack were both reduced. The success rate was significantly increased under the low SNR, indicating a better performance with lower recovery cost. The message recovery success rate could reach 99.6% with sufficient SNR.