1
$\begingroup$

Sketch of some basics of lattice signature schemes.

KeyGen: AS=T; S: private; A, T: public.

Signing:

  1. Y <- random distribution.
  2. C <- Hash(AY|message).
  3. Z <- Y+SC.
  4. Rejection sampling on Z, possibly restart. (Note here)

Verifying: Accept iff

  1. Z is reasonably small.
  2. c == Hash(AZ-TC|message).

What I know:

Rejection sampling is for making sure Z is independent of S so as to not leak info about secret key like NTRUSign. That's also why we need Y over a pretty wide range.

(Discrete) Gaussian distribution is used in BLISS to reduce signature size.

What I want to know:

  1. What if the coefficients of S, A, Y are like one-time pads? Sampled uniformly within {0,1,2,..,q-1} - the full range of $Z_q$ where $q$ is the modulus of the coefficients?
  2. Would we be able to eliminate rejection sampling then?
  3. Would we be able to have smaller dimension with smaller coefficients?

Reason for asking.

Curiosity I had when working on the precision of BLISS sampler.

$\endgroup$
2
$\begingroup$

In fact you can sample $Y$ from uniform in $Z_q^n$. An example of such schemes is the NTRU modular lattice signature scheme [1] but it is not the case here. There are mainly 3 reasons that BLISS family of schemes [2] uses discrete Gaussian distribution.

Firstly, the signer need to prove that he knows the trapdoor (a short basis) namely

$[S, -I],$

to the lattice

$L = \{(u,v): uA+vT = 0 \mod q\}$

Anyone can find vectors of length $q$ for this lattice, i.e., $(q,0,0,...,0)$; but only the signer can find vectors significantly smaller than $q$. This is known as the Ring Short Integer Solution (R-SIS) problem.

Now, if the vector $Z$ has uniform coefficients in $Z_q$, an attacker is able to find a large vector in $L$, namely $U$, that is a multiple of $C$, i.e., $U = S'C$ for some $S'$. This $U$ is large but it doesn't matter to the verification procedure now, because every legit signature has large $SC$. If required, he can repeat it enough times to ensure that $Z' = Y+S'C$ is uniform in $Z_q^n$. Then $Z'$ will look like a legitimate signature.

In a nutshell, the signer is not able to prove the knowledge of the trapdoor if $Z$ is large. And if both $S$ and $A$ are uniform in $Z_q^n$, there is in fact no trapdoor in the lattice to authenticate the signer. On the other hand, this attack will not be possible, if $Z$ and $Y$ are small and discrete Gaussian, in which case $SC$ must be small too.

(NTRU modular lattice signature uses a different approach to prove the knowledge of the trapdoor so $Z$ doesn't need to be short.)

Secondly, you still need to perform rejection sampling even if $S,A,Y$ are uniform in $Z_q^n$. Because even if $Y$ is uniform in $Z_q^n$, $Z = Y+SC$ will be somewhat uniform in a different range, which is more or less $Z_q^n$ shifted by $SC$. So if you publish $Z$ with out rejection sampling, each transcript will leak partial information on $SC$.

The third reason of using discrete Gaussian distribution, as you have mentioned, is that $Z$ is also a discrete Gaussian which allows for compression. For example, in BLISS [2], to store an discrete Gaussian vector in $Z_q^n$, you only require $n(log q-2)$ bits, rather than $nlogq$ bits as if the vector were uniform in $Z_q^n$.

[1] https://eprint.iacr.org/2014/457.pdf

[2] https://eprint.iacr.org/2013/383.pdf

$\endgroup$
  • $\begingroup$ That's what I thought. I just realized that any forger can break it by solving AZ=AY+TC in no more than O(n^3). $\endgroup$ – DannyNiu Oct 5 '16 at 15:39
1
$\begingroup$

$S$ and $A$ are already uniformly random but in a smaller range (well, sometimes they are not to obtain a smaller key size by introducing some structure). The key point in your question is what happens if we use a uniform distribution for $Y$.

If you look at step 3 of the signing algorithm, $Z$ is $Y$, shifted by something depending on the secret $S$. As $Z$ and $C$ form the signature and are hence known to the adversary, this leaks information about the secret key if you remove the rejection sampling. More precisely, it follows a discrete Gaussian distribution with mean $SC$. This would allow to determine $S$ after seeing a reasonably big number of signatures. The rejection sampling prevents this, making sure that $Z$ follows a discrete Gaussian with mean $0$.

If you replace the discrete Gaussian for $Y$ with the uniform distribution over a finite range, the same issue applies. $Y$ would be sampled from a uniform distribution over a range centred at $0$ and consequently $Z$ follows a uniform distribution over a range centred at $SC$. Hence, we again need rejection sampling, to make the $Z$'s that we output follow a uniform distribution over a range with centre $0$. Indeed, the rejection probability goes up as a lot of the probability mass of the shifted distribution as probability 0 according to the 0-centred distribution.

$\endgroup$
  • $\begingroup$ Sorry. My key point is not just uniformly sampling Y. My key point would be to sample coefficients of Y in full range i.e. 0,1,2,...,q-1 where q is the modulus of the coefficients. $\endgroup$ – DannyNiu Oct 5 '16 at 13:59
  • $\begingroup$ But then your signatures get really large... $\endgroup$ – mephisto Oct 6 '16 at 17:49

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.