How would low-precision Gaussian sampling impact the security of BLISS?

Question

For digital signature, I implemented BLISS in my cryptographic suite, and wrote the Gaussian sampler based on Lattice Signatures and Bimodal Gaussians. But unlike the reference implementation and StrongSwan, I used 32-bit floating-point pre-computed constants instead of integer arrays, which I assume will be available on my targeted platforms.

And the picture shows 16384 iterations of accumulative sampling distribution image of my BLISS-I sampler preset.

In essence, my questions are:

• How will low-precision Gaussian sampling impact security or anything?
• And is using 32-bit floating-point a bad idea in cryptographic sampling?

Note the peak singularity in the picture is due to horizontally scaling before shifting and arithmetic performed rounding towards zero, not an error in the implementation. (And the image generation algorithm has been modified)

Answer 1

For your first question: I assume you are talking about the precomputed values in Algorithm 8 of the original BLISS paper. A more recent paper of Bai et al. has shown (see Table 1) that these values can be stored with a lower precision than originally claimed, without harming the security. For BLISS-I, the analysis yields a precision of 40 bits. For other sets of parameters, you'll have to recompute the precision using the formulas of the paper.

For your second question: The required precision depends on how you sample; there are so many ways of sampling Gaussians, and it also depends of the parameters of your scheme... That being said, 32 bits seem very, very low. The precision of 40 bits obtained in the paper aforementioned is the best I am aware of.

Answer 2

The purpose of Gaussian sampling is to prevent the signature from leaking information about the product of the secret key and the callange, and the better quality the samples, the better security.

As we know, the reason NTRUSign is broken is because it's not zero-knowledge. When you sign about 400 messages with the same key-pair, the distribution of the signatures roughly makes up a (high-dimension) cube whose edges follows that of the secret key vectors.

The same would apply to BLISS if attacker would be able to statistically distinguish bad signatures from good discrete Gaussian. The attacker would then draw a rough picture of Sc - challenge multiplied by secret vectors, then take challenge out of the equation there by recovering the secret private key.

This is why we need to calculate some transcendent functions to high precisions to perform Gaussian and rejection sampling.

I'll soon update this answer once I've learned more from references such as this about how much precision is needed to achieve full and/or practical zero-knowledge.

Also, the distribution of signature polynomials z1 and z2 are Gaussian after rejection sampling, where as I generated Huffman coding table for the pre-rejection distribution as of the 2016-09-15 release. Obviously I did not fully understand the rejection sampling process.

Based on this, I did the following calculation:

$ awk "BEGIN { s = sqrt(2*${pi})*215 ; l = log(0.22*s*s*(1+2*15*s))/log(2) ; printf(\"%f, %f, \n\", s, l) ; }
END { printf(\"%f\n\", (log(l*1024)/log(2) + 64)/2) ; }" /dev/null
538.925079, 29.944378, 
39.452107
$ awk "BEGIN { s = sqrt(2*${pi})*107 ; l = log(0.22*s*s*(1+2*15*s))/log(2) ; printf(\"%f, %f, \n\", s, l) ; }
END { printf(\"%f\n\", (log(l*1024)/log(2) + 64)/2) ; }" /dev/null
268.209225, 26.924290, 
39.375418
$ awk "BEGIN { s = sqrt(2*${pi})*250 ; l = log(0.22*s*s*(1+2*15*s))/log(2) ; printf(\"%f, %f, \n\", s, l) ; }
END { printf(\"%f\n\", (log(l*1024)/log(2) + 64)/2) ; }" /dev/null
626.657069, 30.597140, 
39.467662
$ awk "BEGIN { s = sqrt(2*${pi})*271 ; l = log(0.22*s*s*(1+2*15*s))/log(2) ; printf(\"%f, %f, \n\", s, l) ; }
END { printf(\"%f\n\", (log(l*1024)/log(2) + 64)/2) ; }" /dev/null
679.296262, 30.946228, 
39.475846
$

Looks like 40-bit precision might do for now.