Energy-Efficient NTT Sampler for Kyber Benchmarked on FPGA

• URL: http://arxiv.org/abs/2505.01782v1
• Date: Sat, 03 May 2025 10:54:01 GMT
• Title: Energy-Efficient NTT Sampler for Kyber Benchmarked on FPGA
• Abstract summary: Kyber is a lattice-based key encapsulation mechanism selected for standardization by the NIST Post-Quantum Cryptography (PQC) project.<n>A critical component of Kyber's key generation process is the sampling of matrix elements from a uniform distribution over the ring Rq.<n>Existing approaches to this sampling rely on rejection sampling.<n>We propose Modified SampleNTT, which substantially educes the average number of bits required from SHAKE-128 to generate elements in Rq.
• Score: 0.8049701904919515
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Kyber is a lattice-based key encapsulation mechanism selected 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 one of the most computationally intensive tasks in the scheme, significantly impacting performance in low-power embedded systems such as Internet of Things (IoT), wearable devices, wireless sensor networks (WSNs), smart cards, TPMs (Trusted Platform Modules), etc. Existing approaches to this sampling, notably conventional SampleNTT and Parse-SPDM3, rely on rejection sampling. Both algorithms require a large number of random bytes, which needs at least three SHAKE-128 squeezing steps per polynomial. 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 educes 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, outperforming both state-of-the-art methods, which never succeed in two squeezes of SHAKE-128. Furthermore, our algorithm 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. Our results confirm that Modified SampleNTT is an efficient and practical alternative for uniform polynomial sampling in PQC schemes such as Kyber, especially for low-power security processors.

Related papers

• Large-Scale Quantum Circuit Simulation on an Exascale System for QPU Benchmarking [0.2578242050187029]
  Noise continues to limit the amount of useful information that can be extracted from quantum processors.<n>We benchmark Quantinuum Helios-1, a 98-qubit trapped-ion quantum processing unit, using the linear ramp quantum approximate optimization algorithm (LR-QAOA)<n>We perform large-scale noiseless simulations on JUPITER, Europe's first exascale supercomputer, for circuits of up to 48 qubits and 3,384 two-qubit gates.
  arXiv  Detail & Related papers  (2026-04-29T08:32:55Z)
• BWTA: Accurate and Efficient Binarized Transformer by Algorithm-Hardware Co-design [71.97035034203275]
  We analyze zero-point distortion in binarization and propose a Binary Weights & Ternary Activations (BWTA) quantization scheme.<n>For training, we propose Smooth Multi-Stage Quantization, combining a Levelwise Degradation Strategy and a MagnitudeAlignment Projection Factor.<n>Experiments show that BWTA approaches full-precision performance for Transformer-based models, with an average 3.5% drop on GLUE and less than 2% drop on five tasks.
  arXiv  Detail & Related papers  (2026-04-05T04:25:07Z)
• SHIELD8-UAV: Sequential 8-bit Hardware Implementation of a Precision-Aware 1D-F-CNN for Low-Energy UAV Acoustic Detection and Temporal Tracking [4.962717354668883]
  SHIELD8-UAV is a sequential 8-bit hardware implementation of a precision-aware 1D feature-driven CNN accelerator.<n>The design performs layer-wise execution on a shared multi-precision datapath, eliminating the need for replicated processing elements.<n>Results show that sequential execution combined with precision-aware quantisation and serialisation-aware pruning enables practical low-energy edge inference.
  arXiv  Detail & Related papers  (2026-03-01T12:09:15Z)
• BPDQ: Bit-Plane Decomposition Quantization on a Variable Grid for Large Language Models [56.504879072674015]
  We propose Bit-Plane Decomposition Quantization (BPDQ), which constructs a variable quantization grid via bit-planes and scalar coefficients.<n>BPDQ enables serving Qwen2.5-72B on a single GTX 3090 with 83.85% GSM8K accuracy (vs. 90.83% at 16-bit)
  arXiv  Detail & Related papers  (2026-02-04T02:54:37Z)
• A Quantized VAE-MLP Botnet Detection Model: A Systematic Evaluation of Quantization-Aware Training and Post-Training Quantization Strategies [2.2940141855172036]
  Two widely used quantization strategies--Quantization-Aware Training (QAT) and Post-Training Quantization (PTQ)--are evaluated in terms of their impact on detection performance, storage efficiency, and inference latency.<n>Results: PTQ yielded a 6x speedup and 21x reduction in size, while QAT achieved a 3x speedup and 24x compression, demonstrating the practicality of quantization for device-level IoT botnet detection.
  arXiv  Detail & Related papers  (2025-11-05T05:33:27Z)
• AI-Hybrid TRNG: Kernel-Based Deep Learning for Near-Uniform Entropy Harvesting from Physical Noise [0.0]
  AI-Hybrid TRNG is a deep-learning framework that extracts near-uniform entropy directly from physical noise.<n>It relies on a low-cost, thumb-sized RF front end, plus CPU-timing jitter, for training, and then emits 32-bit high-entropy streams without any quantization step.
  arXiv  Detail & Related papers  (2025-06-30T18:01:40Z)
• Gaussian Weight Sampling for Scalable, Efficient and Stable Pseudo-Quantization Training [5.908471365011943]
  Pseudo-quantization training (PQT) addresses the issues of fully quantized training (FQT)<n>We show that PQT with weight sampling is (3) stable while pre-training GPT2 and Llama2 models with up to 1B parameters and 300B tokens.
  arXiv  Detail & Related papers  (2025-05-16T12:14:12Z)
• Perturbation-efficient Zeroth-order Optimization for Hardware-friendly On-device Training [48.91359197313493]
  Zeroth-order (ZO) optimization is an emerging deep neural network (DNN) training paradigm that offers computational simplicity and memory savings.<n>ZO requires generating a substantial number of Gaussian random numbers, which poses significant difficulties and even makes it infeasible for hardware platforms, such as FPGAs and ASICs.<n>We propose PeZO, a perturbation-efficient ZO framework that significantly reduces the demand for random number generation.<n>Our experiments show that PeZO reduces the required LUTs and FFs for random number generation by 48.6% and 12.7%, and saves at maximum 86% power consumption
  arXiv  Detail & Related papers  (2025-04-28T23:58:07Z)
• FR-Spec: Accelerating Large-Vocabulary Language Models via Frequency-Ranked Speculative Sampling [59.8051705468084]
  Speculative sampling has emerged as an important technique for accelerating the auto-regressive generation process of large language models.<n>We present FR-Spec, a frequency-ranked speculative sampling framework that optimize draft candidate selection through vocabulary space compression.
  arXiv  Detail & Related papers  (2025-02-20T18:58:10Z)
• Efficient Hardware Implementation of Constant Time Sampling for HQC [2.5234156040689237]
  HQC is one of the code-based finalists in the last round of the NIST post quantum cryptography standardization process.<n>A critical compute kernel with respect to efficient hardware implementations and security in HQC is the sampling method used to derive random numbers.<n>Due to its security criticality, recently an updated sampling algorithm was presented to increase its robustness against side-channel attacks.
  arXiv  Detail & Related papers  (2023-09-28T14:57:48Z)
• SqueezeLLM: Dense-and-Sparse Quantization [80.32162537942138]
  Main bottleneck for generative inference with LLMs is memory bandwidth, rather than compute, for single batch inference. We introduce SqueezeLLM, a post-training quantization framework that enables lossless compression to ultra-low precisions of up to 3-bit. Our framework incorporates two novel ideas: (i) sensitivity-based non-uniform quantization, which searches for the optimal bit precision assignment based on second-order information; and (ii) the Dense-and-Sparse decomposition that stores outliers and sensitive weight values in an efficient sparse format.
  arXiv  Detail & Related papers  (2023-06-13T08:57:54Z)
• One-Dimensional Deep Image Prior for Curve Fitting of S-Parameters from Electromagnetic Solvers [57.441926088870325]
  Deep Image Prior (DIP) is a technique that optimized the weights of a randomly-d convolutional neural network to fit a signal from noisy or under-determined measurements. Relative to publicly available implementations of Vector Fitting (VF), our method shows superior performance on nearly all test examples.
  arXiv  Detail & Related papers  (2023-06-06T20:28:37Z)
• Quantum Circuit Simulation by SGEMM Emulation on Tensor Cores and Automatic Precision Selection [2.9385229328767988]
  We use the range statistics of input tensor elements to select which Cores we use for the GEMM operation. We evaluate our method on Random Circuit Sampling (RCS), including Sycamore's quantum circuit, and show that the throughput is 1.86 times higher at maximum.
  arXiv  Detail & Related papers  (2023-03-15T23:35:41Z)
• UniPC: A Unified Predictor-Corrector Framework for Fast Sampling of Diffusion Models [92.43617471204963]
  Diffusion probabilistic models (DPMs) have demonstrated a very promising ability in high-resolution image synthesis. We develop a unified corrector (UniC) that can be applied after any existing DPM sampler to increase the order of accuracy. We propose a unified predictor-corrector framework called UniPC for the fast sampling of DPMs.
  arXiv  Detail & Related papers  (2023-02-09T18:59:48Z)
• Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
  tensor network (TN) algorithms can be mapped to parametrized quantum circuits (PQCs) We propose a new protocol for approximating TN states using realistic quantum circuits. Our results reveal one particular protocol, involving sequential growth and optimization of the quantum circuit, to outperform all other methods.
  arXiv  Detail & Related papers  (2022-09-01T17:08:41Z)
• Efficient experimental characterization of quantum processes via compressed sensing on an NMR quantum processor [4.291616110077346]
  We employ the compressed sensing (CS) algorithm and a heavily reduced data set to experimentally perform true quantum process tomography (QPT) on an NMR quantum processor. We obtain the estimate of the process matrix $chi$ corresponding to various two- and three-qubit quantum gates with a high fidelity. We also experimentally characterized the reduced dynamics of a two-qubit subsystem embedded in a three-qubit system.
  arXiv  Detail & Related papers  (2021-09-27T17:05:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.