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!


1 Answer 1


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


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.