In lattice based digital signature scheme BLISS why the standard deviation is so high (215) compared to the encryption schemes?

| improve this question | | | | |
  • $\begingroup$ do you have a reference for this? $\endgroup$ – b degnan Sep 2 '16 at 22:32
  • $\begingroup$ you can look into this paper eprint.iacr.org/2013/383.pdf, page 24.The standard deviation is around 215. $\endgroup$ – Rick Sep 27 '16 at 8:26

I am assuming you are asking why the standard deviation in BLISS is high compared to that of the errors in encryption schemes. The answer is that the errors in encryption and the random variables with high standard deviation in BLISS (and other lattice signatures) play very different roles. In encryption, one simply needs to generate an error $e$ such that $(a,as+e)$ looks random. You don't need to have a high standard deviation at all for that.

In BLISS, the random variable $y$ that has a high standard deviation is used for masking the secret. In particular, a part of the signature is an element $z=y+sc$ where $s$ is a part of the secret and $c$ is the challenge. What is needed for security is that the distribution of $z$ is completely independent of $s$ -- this ensures that signatures do not leak the secret. The best way we know of how to do that is generate $y$ according to a discrete gaussian distribution of standard deviation proportional to $\|sc\|$ and then do rejection sampling. That is why in BLISS the $\sigma$ is of size proportional to $\|sc\|$.

| improve this answer | | | | |
  • $\begingroup$ Thank you. It is something which I guessed but your explanation clarified all. :-) $\endgroup$ – Rick Nov 24 '16 at 11:32

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.