Compact Lifting for NTT-Unfriendly Modulus
摘要
In the NIST standardization competition, LAC and Saber served as frontrunners due to their small parameter sizes. However, this emphasis on minimalism introduced a trade-off: the modulus chosen was incompatible with the Number Theoretic Transform (NTT), thereby substantially reducing computational efficiency. In this work, we present a novel compact lifting technique, inspired by the work of Chung et al. (TCHES 2021) and Basso et al. (ePrint 2021), which demonstrates the potential to revitalize these algorithms. Our approach transitions the polynomial computation to an NTT-friendly ring with a compact modulus, and minimizes the number of NTT operations, thereby enhancing overall efficiency. Notably, we accelerate the polynomial multiplication in LAC by \(7 \times \) , propelling its Public Key Encryption (PKE) efficiency to exceed that of Kyber. Our compact lifting can also be applied to Saber, achieving a speed-up of up to \(35\%\) for a polynomial multiplication. Our method demonstrates that through strategic modifications, it is possible to retain the size advantage of LAC-like cryptosystems while enhancing their efficiency to outperform Kyber, thereby restoring their competitive edge in the PQC standardization.