Screening Least Square Technique Assisted Multivariate Template Attack Against the Random Polynomial Generation of Dilithium

In recent years, the security of Dilithium against side-channel attacks (SCA) has attracted great attentions from the cryptographic engineering community. However, existing power analysis attacks cannot fully utilize the side-channel leakages of the Dilithium reference implementation to efficiently recover the private key. In light of this, a screening least square technique assisted multivariate template attack (SLST assisted MTA) is proposed in this paper. In SLST assisted MTA, side-channel leakages of coefficient $y_{i}$ of random polynomial y, unsigned number $x_{i}$ and random byte string $a_{i^{\prime }}$ can be utilized simultaneously to recover coefficient $y_{i}$ of random polynomial y with MTA. Then, one can build error-tolerant equations, and the private key $\mathbf {s_{1}}$ can be solved with SLST efficiently. We evaluate the private key recovery efficiency of SLST assisted MTA with real traces measured from the Cortex-M4 processor based Dilithium reference implementation, and the evaluation results show that with MTA, 19.41%, 15.70% and 16.88% of the coefficients of y can be accurately recovered in cases of Dilithium 2, 3 and 5. Besides, using SLST, after five times screening, only 38, 40 and 39 power traces are enough to recover private key $\mathbf {s_{1}}$ of Dilithium 2, 3 and 5 with 100% of success rate.