Paper 2022/110

Revisiting Higher-Order Masked Comparison for Lattice-Based Cryptography: Algorithms and Bit-sliced Implementations

Jan-Pieter D'Anvers, Michiel Van Beirendonck, and Ingrid Verbauwhede

Abstract

Masked comparison is one of the most expensive operations in side-channel secure implementations of lattice-based post-quantum cryptography, especially for higher masking orders. First, we introduce two new masked comparison algorithms, which improve the arithmetic comparison of D'Anvers et al. and the hybrid comparison method of Coron et al. respectively. We then look into implementation-specific optimizations, and show that small specific adaptations can have a significant impact on the overall performance. Finally, we implement various state-of-the-art comparison algorithms and benchmark them on the same platform (ARM-Cortex M4) to allow a fair comparison between them. We improve on the arithmetic comparison of D'Anvers et al. with a factor $\approx 20\%$ by using Galois Field multiplications and the hybrid comparison of Coron et al. with a factor $\approx 25\%$ by streamlining the design. Our implementation-specific improvements allow a speedup of a straightforward comparison implementation of $\approx 33\%$. We discuss the differences between the various algorithms and provide the implementations and a testing framework to ease future research.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
Lattice-Based CryptographySide-Channel ProtectionMaskingFujisaki-Okamoto transform
Contact author(s)
janpieter danvers @ esat kuleuven be
michiel vanbeirendonck @ esat kuleuven be
History
2022-04-14: revised
2022-01-31: received
See all versions
Short URL
https://ia.cr/2022/110
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/110,
      author = {Jan-Pieter D'Anvers and Michiel Van Beirendonck and Ingrid Verbauwhede},
      title = {Revisiting Higher-Order Masked Comparison for Lattice-Based Cryptography: Algorithms and Bit-sliced Implementations},
      howpublished = {Cryptology ePrint Archive, Paper 2022/110},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/110}},
      url = {https://eprint.iacr.org/2022/110}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.