Small error in security proof on the paper On the Multi-User Security of Short Schnorr Signatures with Preprocessing

st flag

I think I found a small error in the security proof Link end of page 37. It states that

$ \sum_{i\leq q} \frac{3i+2}{p-(3q +2)^2/4} \leq \frac{3(q +1)q/2+2}{p - (3q +2)^2 /4}$.

But shouldn't it be

$\sum_{i\leq q} \frac{3i+2}{p-(3q +2)^2/4} \leq \frac{3(q+1)q/2+2q}{p - (3q +2)^2 /4}$ ?

I think that the proof still works, since we want to show that you need $\mathcal{O}(\sqrt{q})$ queries to succeed but it still bothers me.

Thanks in advance!

cn flag

Yes, you've raised a flaw, you can contact the authors, they will probably update their proof in the paper.

But as you've noticed, it's not a big deal because $2q$ is much smaller than $\frac{3q^2}{2}$ asymptotically. Then both expressions are indeed $\mathcal{O}(\sqrt q)$.


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.