Authors - Paresh Baidya, Rourab Paul, Vikas Srivastava, Sumit Kumar Debnath Abstract - Kyber is a lattice-based key encapsulation mechanism se lected for standardization by the NIST Post-Quantum Cryptography (PQC) project. A critical component of Kyber’s key generation process is the sampling of matrix elements from a uniform distribution over the ring Rq. This step is computationally intensive and significantly impact ing task in the performance of low-power embedded systems such as Internet of Things (IoT), wireless sensor networks (WSNs), smart cards, etc. Existing approaches like SampleNTT and Parse-SPDM3 rely on rejec tion sampling, need at least three SHAKE-128 squeezing steps per poly nomial. As a result, it causes significant amount of latency and energy. In this work, we propose a novel and efficient sampling algorithm, namely Modified SampleNTT, which substantially reduces the average number of bits required from SHAKE-128 to generate elements in Rq—achieving approximately a 33% reduction compared to conventional SampleNTT. Modified SampleNTT achieves 99.16% success in generating a complete polynomial using only two SHAKE-128 squeezes. Furthermore, our algo rithm maintains the same average rejection rate as existing techniques and passes all standard statistical tests for randomness quality. FPGA implementation on Artix-7 demonstrates a 33.14% reduction in energy, 33.32% lower latency, and 0.28% fewer slices compared to SampleNTT.
