I know that this is a very specific question, but I still hope that someone can help me. I'm trying to understand the security of the short schnorr signature a little bit better. The security parameter is $k$. The Schnorr Signature $\sigma = (s,e)$ with $s,e \in \mathbb{Z}_q$ has a signature length of $4k$ bits ($s$ and $e$ have $2k$ bits, $e$ is a hash output). The Short Schnorr Signature uses a shorter hash output of $k$ bit length so that the resulting signature has a length of $3k$ bits. Apparently, the Short Schnorr Signature has the same security level as the "normal" Schnorr Signature. As stated in the security proofs on the last page of the paper 'Security of Signed ElGamal Encryption', Schnorr, Jakobsson (page 85). I'm just going to cite the part that I don't understand and hope that someone can explain it to me without me having to give more context.
... a CCA-attacker does not succeed better than with probability
$\frac{1}{2}+t^2/q+l(2^{-k}-\frac{1}{q})$, where $l$ is the number of
decryptor interactions. This shows that random hash values can
securely range over a set of $\sqrt q$ values.
( $q \approx 2^{2k}$ )
Thanks a lot in advance!
