Paper 2022/158
Bitslicing Arithmetic/Boolean Masking Conversions for Fun and Profit with Application to Lattice-Based KEMs
Olivier Bronchain and Gaëtan Cassiers
Abstract
The performance of higher-order masked implementations of lattice-based based key encapsulation mechanisms (KEM) is currently limited by the costly conversions between arithmetic and boolean masking. While bitslicing has been shown strongly speed up to masked implementations of symmetric primitives, it has never been used in higher-order arithmetic-to-boolean and boolean-to-arithmetic masking conversion gadgets. In this paper, we first show that bitslicing can indeed accelerate existing conversion gadgets. We then optimize these gadgets, exploiting the degrees of freedom offered by bitsliced implementations. As a result, we introduce new arbitrary-order boolean masked addition, arithmetic-to-boolean and boolean-to-arithmetic masking conversion gadgets, each in two variants: modulo \(2^k\) and modulo \(p\) (for any integers \(k\) and \(p\)). Practically, our new gadgets achieve a speedup of up to 25x over the state of the art. Turning to the KEM application, we develop the first open-source embedded (Cortex-M4) implementations of Kyber768 and Saber masked at arbitrary order. The implementations based on the new bitsliced gadgets achieve a speedup of 1.8x for Kyber and 3x for Saber, compared to the implementation based on state of the art gadgets. The bottleneck of the bitslice implementations is the masked Keccak-f[1600] permutation.
Metadata
- Available format(s)
- Category
- Implementation
- Publication info
- Preprint.
- Keywords
- MaskingLattice-based KEMKyberSaberBitslicePINI
- Contact author(s)
- olivier bronchain @ uclouvain be,gaetan cassiers @ uclouvain be
- History
- 2022-07-14: revised
- 2022-02-12: received
- See all versions
- Short URL
- https://ia.cr/2022/158
- License
-
CC BY