Cryptology ePrint Archive: Report 2021/483

Masking Kyber: First- and Higher-Order Implementations

Joppe W. Bos and Marc Gourjon and Joost Renes and Tobias Schneider and Christine van Vredendaal

Abstract: In the final phase of the post-quantum cryptography standardization effort, the focus has been extended to include the side-channel resistance of the candidates. While some of the schemes have been already extensively analyzed in this regard, there is no such study yet of the finalist Kyber.

In this work, we demonstrate the first completely masked implementation of Kyber which is protected against first- and higher-order attacks. To the best of our knowledge, this results in the first higher-order masked implementation of any post-quantum secure key encapsulation mechanism algorithm. This is realized by introducing two new techniques. First, we propose a higher-order algorithm for the one-bit compression operation. This is based on a masked bit-sliced binary-search that can be applied to prime moduli. Second, we propose a technique which enables one to compare uncompressed masked polynomials with compressed public polynomials. This avoids the costly masking of the ciphertext compression while being able to be instantiated at arbitrary orders.

We show performance results for first-, second- and third-order protected implementations on the Arm Cortex-M0+. Notably, our implementation of first-order masked Kyber decapsulation requires 12.2 million cycles. This is a factor 2.2 overhead compared to an unprotected implementation. We experimentally show that the first-order implementation of our new modules is hardened against attacks using 100,000 traces and mechanically verify the security in a fine-grained leakage model using the verification tool scVerif.

Category / Keywords: implementation /

Date: received 15 Apr 2021

Contact author: joppe bos at nxp com

Available format(s): PDF | BibTeX Citation

Version: 20210415:202639 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]