2
$\begingroup$

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.

BLISS-I sampler test

In essence, my questions are:

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

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

$\endgroup$
  • $\begingroup$ I just upgraded it to an 56-bit precision one, but precomputation is still done using IEEE-754 binary64 format. Image looks largely the same. $\endgroup$ – DannyNiu Jul 25 '16 at 5:10
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the absolutely helpful input. As such area are under intense research, I cannot yet accept it as correct just hope you know. $\endgroup$ – DannyNiu Sep 23 '16 at 6:36
  • $\begingroup$ I did a bit of calculation, and as the deviation changes linearly, the required precision changes logarithmically (not too much change) assuming attacker can't make the server sign more than 2^64 NEWHOPE ephemeral parameters. I posted the awk calculation codes below in my answer, all for presets requires about around 40 bits of precision. $\endgroup$ – DannyNiu Oct 1 '16 at 11:47
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ There's no need to specify a date in your answer, SE will log this sort of thing automatically in the edit history :) $\endgroup$ – SEJPM Sep 20 '16 at 11:20
  • $\begingroup$ @SEJPM, I needed a time tag for the bug in my software :) $\endgroup$ – DannyNiu Sep 20 '16 at 12:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.