safeRNSgcd: Accelerating Falcon key generation with RNS in SafeGCD

Cesare Huang; Bo-Yin Yang

Paper 2026/2507

safeRNSgcd: Accelerating Falcon key generation with RNS in SafeGCD

Cesare Huang

, Institute of Information Science, Academia Sinica

Bo-Yin Yang, Institute of Information Science, Academia Sinica

Abstract

The deepest level of Falcon's NTRU solver needs only one Bézout coefficient from two large integer resultants already represented in a residue number system (RNS). We give $\mathtt{safeRNSgcd}$, which computes this coefficient while keeping the large states in RNS. Its central insight is that centered explicit CRT can recover the exact low bits needed by SafeGCD batches using single-word fixed-point arithmetic. Integrated into $\mathtt{ntrugen}$, our C implementation reduces inversion and private-key basis-generation costs on a Raspberry Pi 5 and two x86-64 processors, compared with original $\mathtt{ntrugen}$ and a variant omitting the unused coefficient.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Preprint.
Keywords: Falcon SafeGCD RNS Explicit CRT fixed-point arithmetic
Contact author(s): cesarehuang @ icloud com
byyang @ iis sinica edu tw
History: 2026-10-17: approved; 2026-10-16: received; See all versions
Short URL: https://ia.cr/2026/2507
License: CC BY

BibTeX

@misc{cryptoeprint:2026/2507,
      author = {Cesare Huang and Bo-Yin Yang},
      title = {{safeRNSgcd}: Accelerating Falcon key generation with {RNS} in {SafeGCD}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2507},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2507}
}