Cryptology ePrint Archive: Report 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.

Category / Keywords: implementation / Masking, Lattice-based KEM, Kyber, Saber, Bitslice, PINI

Date: received 11 Feb 2022, last revised 11 Feb 2022

Contact author: olivier bronchain at uclouvain be, gaetan cassiers at uclouvain be

Available format(s): PDF | BibTeX Citation

Version: 20220212:065215 (All versions of this report)

Short URL: ia.cr/2022/158


[ Cryptology ePrint archive ]