Hash function requirements for short Schnorr Signature

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?

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}$$).

• And do you perhaps know where I can find a proof of this theorem? The paper only says that it is not a new result, but no source is given. Oct 31, 2021 at 16:11
• They say it's a corollary of Multi-signatures in the plain public-key model and a general forking lemma. Oct 31, 2021 at 16:58
• Alright. Thank you very much for your answers! Oct 31, 2021 at 17:08