Paper 2024/548
Efficient isochronous fixed-weight sampling with applications to NTRU
Abstract
We present a solution to the open problem of designing a linear-time, unbiased and timing attack-resistant shuffling algorithm for fixed-weight sampling. Although it can be implemented without timing leakages of secret data in any architecture, we illustrate with ARMv7-M and ARMv8-A implementations; for the latter, we take advantage of architectural features such as NEON and conditional instructions, which are representative of features available on architectures targeting similar systems, such as Intel. Our proposed algorithm improves asymptotically upon the current approach based on constant-time sorting networks ($O(n)$ versus $O(n \log^2 n)$), and an implementation of the new algorithm applied to NTRU is also faster in practice, by a factor of up to $6.91\ (591\%)$ on ARMv8-A cores and $12.89\ (1189\%)$ on the Cortex-M4; it also requires fewer uniform random bits. This translates into performance improvements for NTRU encapsulation, compared to state-of-the-art implementations, of up to 50\% on ARMv8-A cores and 72\% on the Cortex-M4, and small improvements to key generation (up to 2.7\% on ARMv8-A cores and 6.1\% on the Cortex-M4), with negligible impact on code size and a slight improvement in RAM usage for the Cortex-M4.
Metadata
- Available format(s)
- Category
- Implementation
- Publication info
- Published by the IACR in CIC 2024
- Keywords
- Post-quantum cryptographyNTRUSamplingARM
- Contact author(s)
-
decio gazzoni @ ic unicamp br
tomas @ ime unicamp br
jlopez @ ic unicamp br - History
- 2024-06-29: revised
- 2024-04-09: received
- See all versions
- Short URL
- https://ia.cr/2024/548
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/548, author = {Décio Luiz Gazzoni Filho and Tomás S. R. Silva and Julio López}, title = {Efficient isochronous fixed-weight sampling with applications to {NTRU}}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/548}, year = {2024}, url = {https://eprint.iacr.org/2024/548} }