Résumé
At CHES 2017, Primas, Pessl and Mangard presented an attack on RLWE cryptosystem based on Belief Propagation. The attack applies on the Number Theoretic Transform (NTT) used to decipher a message. It gathers power consumption leakage of the multiplication by roots of unity in the NTT and then applies Belief Propagation to circulate the information of all leakage nodes, until the combined leakage reveal most of the output coefficients of the NTT. In this paper we present some randomisations which either induce in NTT some random mask on values or randomly rearrange the sequence of operations. We evaluate the level of randomisation provided by the proposed countermeasures and also the effect on the processed values in the NTT. We apply Belief Propagation on the proposed randomised NTT and we study how these randomisations affect the attack. Finally we point out that a set of three combined strategies provide a high level of randomisation and a good protection against Belief Propagation attack of Primas et al.