Paper 2024/548

Efficient isochronous fixed-weight sampling with applications to NTRU

Décio Luiz Gazzoni Filho, Instituto de Computação, Universidade Estadual de Campinas (UNICAMP), Department of Electrical Engineering, State University of Londrina
Tomás S. R. Silva, Instituto de Matemática, Estatística e Computação Científica, Universidade Estadual de Campinas (UNICAMP)
Julio López, Instituto de Computação, Universidade Estadual de Campinas (UNICAMP)
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)
PDF
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.