You are looking at a specific version 20210415:202639 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Contact author(s)
joppe bos @ nxp com
History
2021-08-02: revised
2021-04-15: received
See all versions
Short URL
https://ia.cr/2021/483
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.