Résumé
Post-Quantum key encapsulation mechanisms based on the re-encryption framework of Fujisaki and Okamoto have proved very sensitive to Plaintext Checking Oracle (PCO) attacks. The first theoretic works on PCO attacks were rapidly followed by practical attacks on real implementations, notably on NIST standardized ML-KEM. The actual realization of a PCO relies on side-channel leakages that are inherently noisy ; even more so if the implementation embeds side-channel countermeasures.
In this paper we tackle the often overlooked complications caused by highly noisy PCOs. We demonstrate that the impact of wrong oracle answers can be very efficiently reduced with the use of the so-called Sequential Probability Ratio Test (SPRT). This test can be seen as an elegant and natural early abort strategy on top of the commonly used approaches based on majority-voting or the likelyhood ratio test. As far as we know, this is the first use of SPRT in the context of side-channel attacks. We show that it allows to divide by a factor up to 3 the attack complexity compared to the traditional approaches. By establishing new comparisons with recently published noisy PCO attacks we emphasize that SPRT should be considered as the novel baseline for all future works in this line of research.