BLISS solution

The BLISS signature scheme is an improvement of the LYU [Lyu12] scheme, that is, changing the probability distribution of the signature, such as replacing the discrete Gaussian distribution with the bimodal Gaussian distribution. This improvement significantly reduces the rejection sampling rate, which restricts the signature distribution to a fixed Gaussian distribution, thereby eliminating any information leakage caused by the signature distribution.

BLISS has proven to be vulnerable to side-channel attacks. This vulnerability mainly comes from discrete Gaussian sampling, which plays an important role in lattice cryptography. The following shows the improved BLISS algorithm structure that can effectively resist side-channel attacks.

BLISS private key generation

BLISS signature algorithm

BLISS algorithm verification

First, we implement the Bernoulli sampler in the form of a probability ex by a constant method. The Bernoulli sampler is used in the discrete Gaussian sampling algorithm used by BLISS [DDLL13], and the execution process depends on the bit of x. Specifically, the sampler calls the table to search in x, and the search content is each bit with a value of 1. We perform the search by forcing the program to eliminate this potential source of leakage, regardless of the bit value.

Second, we prevent the attacker from deriving the sampled y by decomposing y into the sum of two independently sampled y1 and y2. Then we first calculate Ay1 and Ay2 and add them to calculate Ay. We carefully choose the standard deviation of y1 and y2 and other parameters so that the statistical distance Δ(y, y1 + y2) can be ignored according to Theorem 3.1 in [Pei10]. Due to the cost of protection techniques (protection techniques), the signature generation process is three times slower than unprotected BLISS, but the speed is still very fast. Therefore, the above-mentioned solution we proposed can give a good balance between security and usability.