In lattice based digital signature scheme BLISS why the standard deviation is so high (215) compared to the encryption schemes?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ do you have a reference for this? $\endgroup$– b degnanSep 2, 2016 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$– RickSep 27, 2016 at 8:26
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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\|$.
-
$\begingroup$ Thank you. It is something which I guessed but your explanation clarified all. :-) $\endgroup$– RickNov 24, 2016 at 11:32