SMAUG (-T), Revisited: Timing-Secure, More Compact, Less Failure

Abstract

SMAUG-T is a Module-LWE/LWR-based Key Encapsulation Mechanism (KEM) scheme, one of the Round 2 candidates in the Korean Post-Quantum Cryptography (KpqC) Standardization Competition. It partly follows the design of Kyber, the NIST’s PQC standard, while utilizing the sparse secret to achieve smaller sizes with better performance. Recently, Bernstein (KpqC-bulletin 2024) claimed that SMAUG-T contains sub-procedures that are not constant-time, which makes it vulnerable to an efficient key recovery attack. Additionally, Lee et al. (EPRINT 2024) presented an improved version of May’s Meet-LWE attack (Crypto 2021) on LWE using sparse secrets of fixed weights, which lowered the security of SMAUG-T level-5 parameter than the claimed security. In this paper, we first examine potential mitigation enabling SMAUG-T to be constant-time and assess their impact on performance. The performance decreases significantly compared to the original SMAUG-T, losing one of its strengths. Moreover, to make SMAUG-T secure against the attack of Lee et al., either sizes or decryption failure probability increases by a lot. To overcome this, we introduce new designs for SMAUG-T that allow us to bypass potential non-constant time vulnerabilities and attacks exploiting the sparse secret of fixed weights. These designs not only allow efficient timing-secure implementation but also reduce the sizes and the probability of decryption failures. Notably, the public key and ciphertext sizes are reduced by 10-20% for the level-5 parameters. When comparing constant-time implementations, the new SMAUG-T outperforms Kyber, the NIST’s PQC standard, by up to $1.6\times $ for encapsulation and $1.4\times $ for decapsulation.

Keywords

• Constant-time implementation
• fixed weight polynomial sampler
• key encapsulation mechanism
• Korean post-quantum cryptography competition
• lattice-based cryptography
• SMAUG-T