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?

  • $\begingroup$ Breaking it would be equivalent to breaking the same scheme with $n$ replaced by $l$, and all other parameters unchanged. $\endgroup$
    – LeoDucas
    Jul 5, 2019 at 20:06


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.