# 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?

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

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$.

• 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). – DannyNiu Oct 5 '16 at 15:39

$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.

• 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. – DannyNiu Oct 5 '16 at 13:59
• But then your signatures get really large... – mephisto Oct 6 '16 at 17:49