Join Log in
Score:3
einsteinwein avatar Crypto

Hash function requirements for short Schnorr Signature

st flag
einsteinwein

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?

169
0 + 0
Score:2
Ievgeni avatar Crypto
cn flag
Ievgeni

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

0 + 0
einsteinwein avatar
st flag
einsteinwein
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.
0
Reply
Ievgeni avatar
cn flag
Ievgeni
They say it's a corollary of Multi-signatures in the plain public-key model and a general forking lemma.
1
Reply
einsteinwein avatar
st flag
einsteinwein
Alright. Thank you very much for your answers!
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.