I'm trying to read the separation between the classical and quantum random oracle through a paper "Random Oracles in a Quantum World" by Dan Boneh, Ozgur Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner and Mark Zhandry. enter link description here. Boneh et al. gave an example of an identification protocol (IS*) that is secure in the ROM but insecure in the QROM. In the security proof of IS* (the Lemma 4, in Appendix B) against Classical Adversaries, authors consider the probability of finding a collision in one (and r) rounds, there are two inequalities that make me confused and difficult to understand (see attached image below), in which

  • the first inequality is incorrect (in particular, $\frac{\alpha^2}{2\sqrt[3]{2^{\ell}}}\le \frac{\alpha^2}{2\sqrt[3]{n}} $) with the condition $\ell<log(n)$. enter image description here
  • the second inequality, I have tried applying the Chernoff-bound based on different versions of the theorem, but I cannot deduce the factor $1/4$ as in the given proof. \begin{equation} \text { Pr [collCount }>r / 4 ]\leq \exp \left(-\frac{r \alpha^2}{2 \sqrt[3]{n}} \cdot\left(\frac{\sqrt[3]{n}-2 \alpha^2}{2 \alpha^2}\right)^2 \cdot \frac{1}{4}\right) \end{equation} enter image description here

Can anyone help me explain the above question? Thank you so much!



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.