3
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Oct 31, 2021 at 16:11
  • 1
    $\begingroup$ They say it's a corollary of Multi-signatures in the plain public-key model and a general forking lemma. $\endgroup$
    – Ievgeni
    Oct 31, 2021 at 16:58
  • $\begingroup$ Alright. Thank you very much for your answers! $\endgroup$ Oct 31, 2021 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.