### Efficiently Masking Binomial Sampling at Arbitrary Orders for Lattice-Based Crypto

Tobias Schneider, Clara Paglialonga, Tobias Oder, and Tim Güneysu

##### Abstract

With the rising popularity of lattice-based cryptography, the Learning with Errors (LWE) problem has emerged as a fundamental core of numerous encryption and key exchange schemes. Many LWE-based schemes have in common that they require sampling from a discrete Gaussian distribution which comes with a number of challenges for the practical instantiation of those schemes. One of these is the inclusion of countermeasures against a physical side-channel adversary. While several works discuss the protection of samplers against timing leaks, only few publications explore resistance against other side-channels, e.g., power. The most recent example of a protected binomial sampler (as used in key encapsulation mechanisms to sufficiently approximate Gaussian distributions) from CHES 2018 is restricted to a first-order adversary and cannot be easily extended to higher protection orders. In this work, we present the first protected binomial sampler which provides provable security against a side-channel adversary at arbitrary orders. Our construction relies on a new conversion between Boolean and arithmetic (B2A) masking schemes for prime moduli which outperforms previous algorithms significantly for the relevant parameters, and is paired with a new masked bitsliced sampler allowing secure and efficient sampling even at larger protection orders. Since our proposed solution supports arbitrary moduli, it can be utilized in a large variety of lattice-based constructions, like NewHope, LIMA, Saber, Kyber, HILA5, or Ding Key Exchange.

##### Metadata
Available format(s)
Category
Implementation
Publication info
A minor revision of an IACR publication in PKC 2019
DOI
10.1007/978-3-030-17259-6_18
Keywords
MaskingPost-quantum Cryptography
Contact author(s)
tobias schneider-a7a @ rub de
History
2019-08-08: received
Short URL
https://ia.cr/2019/910
License

CC BY

BibTeX

@misc{cryptoeprint:2019/910,
author = {Tobias Schneider and Clara Paglialonga and Tobias Oder and Tim Güneysu},
title = {Efficiently Masking Binomial Sampling at Arbitrary Orders for Lattice-Based Crypto},
howpublished = {Cryptology ePrint Archive, Paper 2019/910},
year = {2019},
doi = {10.1007/978-3-030-17259-6_18},
note = {\url{https://eprint.iacr.org/2019/910}},
url = {https://eprint.iacr.org/2019/910}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.