# Estimating the Security of SIS-Based Signature, by verifiying a subset of coordinates?

As I understood, the GPV signature scheme works as follows:
KeyGen($$1^n$$) : Generate a Lattice with public $$A \in Z_q^{n.m}$$ and a secret trapdoor $$t$$.
Sign $$m$$: compute $$\vec y = H(m) \in Z_q^n$$ and output short vector $$\vec u \in Z_q^m$$ such that $$A.\vec u = \vec y$$ using the trap $$t$$. The signature is then $$\sigma = (\vec u)$$.
Verify $$(\sigma, m)$$ : Compute $$\vec y = H(m)$$ and verify that $$A.\vec u = \vec y$$ and that $$\vec u$$ is "short".

This scheme was proven existentially unforgeable in the GPV Article (page 24-25) based on the collision resistance of the hash function $$H$$ with a certain probability $$2^{-\omega (\log n)}$$.

I was thinking of an example, that instead of verifying that $$(A.\vec u) [1\dots n] = H(m) [1\dots n]$$, we will verify that $$(A.\vec u) [1\dots l] = H(m) [1\dots l]$$, ($$l = n/2$$ for example). This means that in order for an adversary to forge a new signature, he only needs to output a vector $$\vec u'$$ that verifies the equality for the first $$l$$ coordinates of $$H(m)$$, instead of all of its $$n$$ coordinates$. Will this verification be also existentially unforgeable with a certain probability less than that of the full verification, with a function of $$l$$, or will it be much simpler for an adversary to output a vector $$\vec u$$ that verifies the desired verification? • Breaking it would be equivalent to breaking the same scheme with$n$replaced by$l\$, and all other parameters unchanged. – LeoDucas Jul 5 at 20:06