Score:2

Where does the 8 come from? Generic Search Problem with Bounded Probabilities

mp flag

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?

Score:4
ng flag

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

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.