Multivariate Template Attack against NTT based Polynomial Multiplication of Dilithium Reference Implementation

According to previous works, NTT based polynomial multiplication of Dilithium can be a main target for side-channel analyzers. In detail, the leakage of ˆ u = ˆ cˆ s1 can be used to recover the private key s1 with correlation power analysis (CPA). However, it is not enough to evaluate the side-channel resistance of NTT based polynomial multiplication of Dilithium with CPA. Considering that template attack (TA) is information theoretically the strongest side-channel attack style, one should evaluate the side-channel resistance of NTT based polynomial multiplication of Dilithium with TA. Besides, previous works did not use the leakage of ˆ w = ˆ Aˆ y to recover s1. In light of this, the leakage of ˆ w = ˆ Aˆ y is used in TA to recover s1 for the first time. In fact, the leakage of ˆ w = ˆ Aˆ y can be K times the leakage of ˆ u = ˆ cˆ s1, which can significantly optimize the efficiency of TA. Finally, the leakage of ˆ w = ˆ Aˆ y and the leakage of ˆ u = ˆ cˆ s1 can be used simultaneously to recover s1. In light of this, multivariate template attack (MTA) against NTT based polynomial multiplication of Dilithium is proposed for the first time. The performances of three versions of TA are evaluated in both simulated scenario and real scenario. The evaluation results show that, in simulated scenario where the signal-to-noise ratio (SNR) of both the leakage of ˆ w = ˆ Aˆ y and the leakage of ˆ u = ˆ cˆ s1 is varied from 1 to 0.1, MTA can perform the best among three versions of TA; in real scenario where NTT based polynomial multiplication of Dilithium reference implementation on Cortex M4 is targeted, MTA also performs the best, and only 15, 11, 9 traces are needed in the attack phase of MTA to recover s1 used by Dilithium 2, 3, 5. Overall, a powerful tool which can be used to evaluate the side-channel resistance of NTT based polynomial multiplication of Dilithium in a leakage profiling scenario is proposed.