Paper 2022/555

Adapting Belief Propagation to Counter Shuffling of NTTs

Julius Hermelink, Bundeswehr University Munich, Infineon Technologies (Germany)
Silvan Streit, Fraunhofer Institute for Applied and Integrated Security
Emanuele Strieder, Fraunhofer Institute for Applied and Integrated Security
Katharina Thieme, Fraunhofer Institute for Applied and Integrated Security

The Number Theoretic Transform (NTT) is a major building block in recently introduced lattice based post-quantum (PQ) cryptography. The NTT was target of a number of recently proposed Belief Propagation (BP)-based Side Channel Attacks (SCAs). Ravi et al. have recently proposed a number of countermeasures mitigating these attacks. In 2021, Hamburg et al. presented a chosen-ciphertext enabled SCA improving noise-resistance, which we use as a starting point to state our findings. We introduce a pre-processing step as well as a new factor node which we call shuffle node. Shuffle nodes allow for a modified version of BP when included into a factor graph. The node iteratively learns the shuffling permutation of fine shuffling within a BP run. We further expand our attacker model and describe several matching algorithms to find inter-layer connections based on shuffled measurements. Our matching algorithm allows for either mixing prior distributions according to a doubly stochastic mix matrix or to extract permutations and perform an exact un-matching of layers. We additionally discuss the usage of sub-graph inference to reduce uncertainty and improve un-shuffling of butterflies. Based on our results, we conclude that the proposed countermeasures of Ravi et al. are powerful and counter Hamburg et al., yet could lead to a false security perception -- a powerful adversary could still launch successful attacks. We discuss on the capabilities needed to defeat shuffling in the setting of Hamburg et al. using our expanded attacker model. Our methods are not limited to the presented case but provide a toolkit to analyze and evaluate shuffling countermeasures in BP-based attack scenarios.

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in TCHES 2023
Kyber NTT belief propagation side-channel attack CCA
Contact author(s)
julius hermelink @ unibw de
silvan streit @ aisec fraunhofer de
emanuele strieder @ aisec fraunhofer de
k thieme @ stud uni-goettingen de
2022-10-13: revised
2022-05-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Julius Hermelink and Silvan Streit and Emanuele Strieder and Katharina Thieme},
      title = {Adapting Belief Propagation to Counter Shuffling of NTTs},
      howpublished = {Cryptology ePrint Archive, Paper 2022/555},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.