SFAFFT speeds up boolean polynomial multiplication and makes HQC arithmetic measurably less annoying across platforms.
3 comments
Saving this for later, HQC arithmetic has been annoying for too long...
The cross-platform part is the real win here, especially if you care about one codebase not turning into a zoo of hand-tuned paths. Compared with Toom-Cook-Karatsuba, though, it still loses on plain AVX2 for the two smaller HQC parameter sets, so I wouldn’t call this a universal replacement for the old school multiply.
Compared with the earlier FAFFT-based multiplications, SFAFFT seems to clean up the field-size and CRT baggage and that’s probably where the annoyingness drops in practice. But if your deployment is mostly AVX2 and the small params matter, the cloud bill may still prefer the boring polynomial schoolbook-ish stuff over another fancy FFT variant.
the non-power-of-two bit matters, hqc’s awkward degrees are where clean fft code usually gets ugly.