Joo Woo

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.

In 2009, Lyubashevsky proposed a lattice-based signature scheme using the Schnorr-like identification and the Fiat-Shamir heuristic and proved its security under the collision resistance of a generalized compact knapsack function. However, their security analysis requires the witness indistinguishability property, leading to significant inefficiency and an increase of sizes of public key and signature. To overcome the efficiency issue associated with the WI property, we introduce a new lattice-based assumption, called the target-modified one-wayness problem of the GCK function and show its reduction to well-known lattice-based problems. Additionally, we present a simple and efficient GCK-based signature scheme, GCKSign, whose security is based on the Module GCK-TMO problem in the random oracle model. GCKSign is a natural extension of Lyubashevsky’s scheme in a module setting, but achieves considerable efficiency gains due to eliminating the witness indistinguishability property. As a result, GCKSign achieves approximately 3.4 times shorter signature size and 2.4 times shorter public key size at the same security level.