Rejscore: Lightweight Accelerator Enables Efficient Rejection Sampling for Multivariate Public Key Cryptography

Post-quantum cryptography offers promising solutions to secure communications against future threats, but many schemes demand substantial computational resources, particularly during a critical step called rejection sampling. Malik Imran, Safiullah Khan, and Zain Ul Abideen, alongside colleagues from Queen’s University Belfast, Manchester Metropolitan University, Carnegie Mellon University, and Umm Al-Qura University, address this challenge with RejSCore, a novel hardware accelerator designed to efficiently perform rejection sampling within post-quantum cryptographic systems. This research significantly advances the practicality of schemes like QR-UOV, a leading candidate in the National Institute of Standards and Technology’s standardization process, by reducing both area and power consumption without compromising performance. Through implementation on both Artix-7 FPGAs and 65nm CMOS technology, RejSCore demonstrates a substantial improvement in resource efficiency, paving the way for deployment in devices with limited power and space, such as embedded systems and mobile devices.

The study pioneers a dedicated hardware implementation for this computationally intensive step, which has remained largely unexplored in prior work focusing on signature generation. RejSCore incorporates an AES-CTR-128-based pseudorandom number generator, utilizing a fully unrolled and pipelined AES-128 encryption engine to efficiently generate the random values essential for the sampling process. To minimize resource consumption, the team employed a lightweight iterative architecture for rejection sampling, implementing an efficient data buffering strategy that reduces area overhead.

This innovative approach addresses the need for compact hardware solutions suitable for resource-constrained devices. The performance of RejSCore underwent comprehensive evaluation on both Artix-7 FPGAs and 65nm CMOS technology, utilizing Area-Delay Product and Power-Delay Product metrics to assess its efficiency. Experiments demonstrate that RejSCore achieves an area of 2042 slices and 464,866 μm2, operating at frequencies of 222MHz on Artix-7 and 565MHz on 65nm CMOS. When processing QR-UOV parameters for security level I, the core completes its operation in 8525 clock cycles. These results confirm RejSCore’s suitability for deployment in environments demanding both security and limited resources, such as embedded systems and edge devices. The work represents a significant advancement in post-quantum cryptographic hardware.

RejSCore Accelerates QR-UOV Signature Generation

The team presents RejSCore, a hardware accelerator designed to efficiently perform rejection sampling, a computationally intensive step within post-quantum cryptographic schemes. This work specifically targets the QR-UOV signature scheme, a promising candidate in the ongoing NIST standardization process for post-quantum cryptography. The core employs an AES-CTR-128-based pseudorandom number generator and a lightweight iterative method for rejection sampling, achieving a balance between reduced resource consumption and acceptable latency. Evaluations on both Artix-7 FPGAs and 65nm CMOS technology demonstrate RejSCore’s suitability for resource-constrained devices and security-critical applications.

The core achieves operation in 8525 clock cycles using specific QR-UOV parameters, and performance metrics, such as Area-Delay Product and Power-Delay Product, confirm its efficiency. While the current design prioritizes performance evaluation, the authors acknowledge the need for future work addressing resilience against physical attacks. Planned extensions include incorporating support for alternative pseudorandom number generators and expanding RejSCore’s capabilities to encompass all security levels within the QR-UOV scheme.