Hash function requirements for short Schnorr Signature

Question

Neven et al. stated in their paper Hash Function Requirements for Schnorr Signatures following theorem (using the forking lemma): $\mathbb{G}$ is the generic group (section 2), $s \approx \log_2q$, hash function $H: \lbrace 0,1 \rbrace^* \rightarrow \lbrace 0,1 \rbrace^n$.

Theorem 1 If the discrete logarithm problem in $\mathbb{G}$ is $(t_\text{dlog}, \epsilon_\text{dlog}$-hard, then the Schnorr Signature is $(t_\text{uf-cma}, q_S,q_H, \epsilon_\text{uf-cma})$-secure for $ \epsilon_\text{uf-cma} = \sqrt{(q_H+q_S+1)\epsilon_\text{dlog}} + \frac{q_H+q_S+1}{2^n} + \frac{q_S(q_H+q_S+1)}{q}$ and $t_\text{uf-cma}= t_\text{tdlog}/2 − q_S t_\text{exp} + \mathcal{O}(q_H + q_S + 1)$, where $t_\text{exp}$ is the cost of an exponentiation in the group $\mathbb{G}$.

They conclude that this bound clearly indicates that a hash function with $n = s/2$ output bits should be sufficient to obtain a security level of $s/2$ bits. A term of the form $q_H^2/2^n$ would have advised for an s-bit hash function.

Could someone explain this a bit more detailed to me?

Answer 1

Here, $k$ bits of security means that the advantage is at most $O\left(\frac{T^\alpha}{2^{\alpha k}}\right)$, after doing $T$ operations (of all types) made by the adversary. With this formalism, it allows us to conclude that the adversary need to do $O(2^k)$ "operations" to break the system ($T^\alpha \approx2^{\alpha k}\implies T \approx 2^k$).

Then, we have look in details all the terms in the sum.

When we look the third term: $\frac{q_S(q_H+q_S+1)}{q}\leq\frac{T}{q}$, it is okay.

The second term $\frac{q_H+q_S+1}{2^n}=O(T2^{-n})$: And if we want to have this term in $O(T2^{-s/2})$, we need to have $n\geq s/2$, (recall $n$ is the output size of the hash function).

About first term, it's a little bit more complex: $\sqrt{(q_H+q_S+1)\epsilon_\text{dlog}}\leq\sqrt{T2^{-s/2}}$, but it is also okay (with $\alpha=\frac{1}{2}$).