I am working with lossy ID-schemes and their security in the QROM. Following the article of Kiltz et al. , I am at a loss of the number 8 appearing in most reductions throughout the article. I know it comes from the Generic Search Problem for Bounded Probabilites, however how?

The Lemma from the article as wee as the game for a quantum adversary is:

enter image description here

With the following proof in the appendix:

enter image description here enter image description here

Any and all help would be greatly appreciated. I have been looking at line 02 for the $GSPB_{\lambda}$ game and wondering if it could have anything to do with the probability of $\lambda(x)$ being greater than $\lambda$ ?

I have also followed the proof to the original source, but nor here do I seem to find anything explaining the 8...

My main goal for looking at this was finding the bound for a classical adversary $\mathcal{B}$ against the GSPB. I would believe this to be simply $Pr[GSPB^{\mathcal{B}}_{\lambda} \Rightarrow 1] = \lambda \cdot Q$. Is this intuition right?


1 Answer 1


As the paper states, you should look directly at HRS16, Theorem 1. The proof there seems fairly straightforward, but it seems to depend on theorem 7.2 of Zhandry2012. This itself appears to depend on another Zhandry2012, namely theorem 3.2

Theorem 3.2. Fix $q$, and let $D_\lambda$ be a family of distributions on $H_{X,Y}$ indexed by $\lambda\in[0,1]$. Suppose there are integers $d$ and $\Delta$ such that for every $2q$ pairs $(x_i, r_i)\in X\times Y$, the function $p(\lambda) = \Pr_{H\gets D_\lambda}[H(x_i) = r_i\forall i\in\{1,\dots,2q\}]$ satisfies:

  • $p$ is a polynomial in $\lambda$ of degree at most $d$, and
  • $p^{(i)}(0)$, the $i$th derivative of $p$ at 0, is 0 for each $i\in\{1,\dots, \Delta-1\}$.

Then any quantum algorithm $A$ making $q$ quantum queries can only distinguish $D_\lambda$ from $D_0$ with probability at most $\frac{4^\Delta}{(2\Delta)!}\lambda^\Delta d^{2\Delta}.$

It appears your paper later applies this with $\Delta = 1$ and $d = 2(Q+1)$, giving a bound of $\frac{4}{2}\lambda (2(Q+1))^2 = 8\lambda (Q+1)^2$.


Your Answer

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

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