FAEST on GPUs: Addressing Field Multiplication as a Bottleneck

What it is

A preprint (ePrint 2026/2489, author Minseop Choi) with an NVIDIA GPU implementation of the FAEST key-generation core and the QuickSilver OWFProve/OWFVerify procedures. It covers the standard and EM constructions in both s and f variants. The work was first submitted for review on 15 July 2026, concurrently with ePrint 2026/1409.

How it works

• Bottleneck: once AES is hardware-accelerated, field multiplication in QuickSilver is the largest cost across the whole parameter grid. In FAEST-128f it takes about 82% of signing time.
• Fix 1, PTX clmad: native carry-less multiply-add replaces the software multiplication.
• Fix 2, Karatsuba: reduces the number of limb products.

Results (RTX A5000)

Standard OWFProve throughput with clmad alone, relative to the software-multiplication build:

• clmad improves all twelve OWFProve and OWFVerify paths, and the gain grows with field width.
• clmad plus Karatsuba gives 26.6x on the field-multiplication-heavy kernel of standard 256-bit OWFProve.
• Across all OWFProve stages at 256 bits, the combined build reaches 2.9x (standard) and 3.1x (EM).
• Karatsuba's benefit is stated only for 256-bit proving. At 128 and 192 bits, clmad is the main lever.

What to do

If you are building or evaluating a GPU FAEST prover, use native carry-less multiplication as the first design choice. Add Karatsuba only if you target 256-bit parameters.

Caveats

• The scope is key-generation core plus OWFProve/OWFVerify, not a full end-to-end signing or verification pipeline. The 82% figure refers to signing time, but the GPU speedups are for these components.
• All numbers come from one GPU (RTX A5000), so don't assume they transfer to other architectures. clmad is a PTX instruction, so the approach is NVIDIA-specific.
• The speedups are relative to the author's own software-multiplication build, not to other published FAEST implementations.
• This is an unreviewed preprint.