Why the Naive Version Leaks

The obvious thing to try is translating Schnorr into the module setting piece by piece. This note does that, and then breaks it.

01.The direct translation

Replace the group by $R_q^\ell$, the exponentiation by matrix multiplication, and $t = g^s$ by $\mathbf{t} = A\mathbf{s}_1$. The protocol becomes:

1. Commit. Sample $\mathbf{y} \in R_q^\ell$ with small coefficients, send $\mathbf{w} = A\mathbf{y}$.
2. Challenge. Receive a small $c \in R_q$.
3. Respond. Send $\mathbf{z} = \mathbf{y} + c\mathbf{s}_1$.

The verifier checks $A\mathbf{z} - c\mathbf{t} = \mathbf{w}$, which holds because

$$A\mathbf{z} - c\mathbf{t} \;=\; A(\mathbf{y} + c\mathbf{s}_1) - cA\mathbf{s}_1 \;=\; A\mathbf{y} \;=\; \mathbf{w}.$$

Algebraically this is fine. It is the exact lattice analogue of $g^z = w \cdot t^c$, and every equation balances.

It also hands over the secret key.

02.The leak, in one line

$$\mathbf{z} - \mathbf{y} \;=\; c\,\mathbf{s}_1 .$$

Every signature releases $\mathbf{z}$, which is the secret multiplied by a known challenge and hidden under a mask $\mathbf{y}$ that has bounded size. Averaging over many signatures pulls the secret out of the mask.

This is the point where the group argument fails. In Schnorr, $y$ was uniform over the whole group, so $y + cs$ was still exactly uniform and the shift was invisible. Here $\mathbf{y}$ has small coefficients drawn from a bounded range, so $\mathbf{y} + c\mathbf{s}_1$ is that same bounded range shifted. The shift is exactly $c\mathbf{s}_1$, and a shifted distribution is distinguishable from an unshifted one.

03.Watching it happen

Forget the ring for a moment and work with a single integer secret, which makes the arithmetic legible.

Take $s = 3$. Let the challenge $c$ be $+1$ or $-1$ at random, and let $y$ be uniform on $[-100, 100]$. The released value is $z = y + cs$.

When $c = +1$, $z$ is uniform on $[-97, 103]$, whose mean is $+3$.

When $c = -1$, $z$ is uniform on $[-103, 97]$, whose mean is $-3$.

So an attacker who collects signatures, separates them by which challenge was used, and takes the mean of each group, will see the two means separated by exactly $2s$.

Simulating that with 400,000 signatures:

$$\text{mean}(z \mid c = +1) \;=\; +3.269, \qquad \text{mean}(z \mid c = -1) \;=\; -3.033 .$$

Half the difference is

$$\frac{3.269 - (-3.033)}{2} \;=\; 3.151 ,$$

against a true secret of $3$. The attacker has recovered it to within rounding, using nothing but arithmetic means.

This is not a side-channel attack and it does not depend on any implementation flaw. It is an algebraic property of the construction. The released values are a shifted distribution and the shift is the secret.

04.Why more noise does not fix it

The natural first response is to make $\mathbf{y}$ much larger, so the shift is proportionally smaller and harder to detect.

That helps only slowly. The statistical detectability of a shift of size $s$ in a distribution of width $\gamma$, given $N$ samples, grows like $s\sqrt{N}/\gamma$. So doubling $\gamma$ forces the attacker to quadruple $N$, and $N$ is free to them under EUF-CMA, where they may request unlimited signatures.

Meanwhile $\gamma$ cannot grow without bound. It sets the size of $\mathbf{z}$, which is most of the signature, so doubling it costs a bit per coefficient across $\ell \cdot 256$ coefficients on every signature ever sent. Buying security this way is paying continuously to make the attacker's job merely tedious.

What is needed is not a bigger mask. It is a construction where the released values carry no shift at all, regardless of the secret.

That exists, and it is the subject of the next note.