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

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.