Jonghyun Kim

In CRYPTO 2013, Ducas et al. introduced a bimodal discrete Gaussian distribution into the Fiat-Shamir with abort paradigm, proposing a signature scheme called BLISS, which significantly improved rejection sampling efficiency and reduced the number of required abort steps compared to all previously proposed (uni-modal) lattice-based signature schemes. Although the theoretical structure of the bimodal distribution is elegant, the BLISS implementation suffers from several side-channel vulnerabilities. The primary issue arises from the fact that the probability mass function of the bimodal discrete Gaussian distribution is a transcendental function, which makes it difficult to implement solely with integers in constant-time. To address this issue, we introduce a new distribution called ‘Generalized Centered Binomial Distribution (GCBD)’ that can replace the (bimodal) discrete Gaussian distribution. As a generalized form of the centered binomial distribution (CBD), GCBD is simple and efficient in sampling integers from distributions with large standard deviations. GCBD sampling consists of sampling uniformly random bitstrings and integer addition/subtraction operations, allowing for efficient constant-time implementation. Furthermore, bimodal rejection sampling using GCBD can be implemented only with integer operations in constant-time, with the help of the Newton-Raphson method. By incorporating the bimodal GCBD rejection sampling into BLISS, we present a new variant of BLISS that can be implemented in constant-time, thereby eliminating the side-channel vulnerabilities associated with timing attacks. Finally, we compare the performance of our variant to GALACTICS, a previous constant-time implementation of BLISS. While the signing algorithm of our variant is about 3.3 times slower than that of GALACTICS, GCBD can serve as an alternative to the discrete Gaussian distribution for designing bimodal lattice signatures.

NTRU was the first practical public key encryption scheme constructed on a lattice over a polynomial-based ring and has been considered secure against significant cryptanalytic attacks over the past few decades. However, NTRU and its variants suffer from several drawbacks, including difficulties in achieving worst-case correctness error in a moderate modulus, inconvenient sampling distributions for messages, and relatively slower algorithms compared to other lattice-based schemes. In this work, we propose a new NTRU-based key encapsulation mechanism (KEM), called NTRU+, which overcomes nearly all existing drawbacks. NTRU+ is constructed based on two new generic transformations: ACWC ₂ and FO ^⊥ (a variant of the Fujisaki-Okamoto transform). ACWC ₂ is used to easily achieve worst-case correctness error, while FO ^⊥ is used to achieve chosen-ciphertext security without re-encryption. Both ACWC ₂ and FO ^⊥ are defined using a randomness-recovery algorithm and an encoding method. In particular, our simple encoding method, the semi-generalized one-time pad (SOTP), allows us to sample a message from a natural bit-string space with an arbitrary distribution. We provide four parameter sets for NTRU+ and present implementation results using NTT-friendly rings over cyclotomic trinomials.