Paper 2022/494

Single-Trace Side-Channel Attacks on ω-Small Polynomial Sampling: With Applications to NTRU, NTRU Prime, and CRYSTALS-DILITHIUM

Emre Karabulut, Erdem Alkim, and Aydin Aysu


This paper proposes a new single-trace side-channel attack on lattice-based post-quantum protocols. We target the ω-small polynomial sampling of NTRU, NTRU Prime, and CRYSTALS-DILITHIUM algorithm implementations (which are NIST Round-3 finalists and alternative candidates), and we demonstrate the vulnerabilities of their sub-routines to a power-based side-channel attack. Specifically, we reveal that the sorting implementation in NTRU/NTRU Prime and the shuffling in CRYSTALS-DILITHIUM's ω-small polynomial sampling process leaks information about the ‘-1’, '0’, or ’+1' assignments made to the coefficients. We further demonstrate that these assignments can be found within a single power measurement and that revealing them allows secret and session key recovery for NTRU/NTRU Prime, while reducing the challenge polynomial's entropy for CRYSTALS-DILITHIUM. We execute our proposed attacks on an ARM Cortex-M4 microcontroller running the reference software submissions from NIST Round-3 software packages. The results show that our attacks can extract coefficients with a success rate of 99.78% for NTRU and NTRU Prime, reducing the search space to 2^41 or below. For CRYSTALS-DILITHIUM, our attack recovers the coefficients’ signs with over 99.99% success, reducing rejected challenge polynomials’ entropy between 39 to 60 bits. Our work informs the proposers about the single-trace vulnerabilities of their software and urges them to develop single-trace resilient software for low-cost microcontrollers.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. 2021 IEEE International Symposium on Hardware Oriented Security and Trust (HOST)
Side-channel attacksPost-quantum cryptographyNTRUCRYSTALS-DILITHIUM
Contact author(s)
ekarabu @ ncsu edu
2022-04-23: received
Short URL
Creative Commons Attribution


      author = {Emre Karabulut and Erdem Alkim and Aydin Aysu},
      title = {Single-Trace Side-Channel Attacks on ω-Small Polynomial Sampling: With Applications to NTRU, NTRU Prime, and CRYSTALS-DILITHIUM},
      howpublished = {Cryptology ePrint Archive, Paper 2022/494},
      year = {2022},
      doi = {10.1109/HOST49136.2021.9702284},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.