Simple question:

I just learn the existence of the great Yao's Xor lemma (see a quick sum-up at the end of this post). I'd like to use a similar argument, but instead of a simple function, I've a two rounds (quantum) protocol that outputs a secret $s$ that the adversary may poorly describe. Is there any extension of Yao's Xor lemma to protocols that could let me say that there is no way to get the xor of several repetitions of the protocol? (or other any hardness amplification method that could apply to this setting?)

Bonus: and what about for quantum protocols?

More details: to give a bit more details, basically I've a quantum protocol that produces a uniform bit $s$, and using some information theory arguments I should be able to prove that there is no quantum circuit that can guess $s$ with probability better than $1/2+\mu$, with $\mu$ being a constant strictly smaller than $1/2$ (even conditioned on the case where the protocol does not abort). Note that an unbounded adversary could compute $s$ so here we really need to have a polynomially bounded quantum adversary. Now, I'd like to state that when I repeat this protocol several times and get several uniformly distributed secrets $s_i$, the adversary cannot get the xor of these $s_i$ with probability better than $1/2 + \text{negl}(n)$. ($n$ is a security parameter, that could be linked with the number of repetitions of the algorithm)

Are you aware of any generalisation of Yao Xor lemma to (quantum) protocols instead of functions? Thanks!

-- EDIT --

Here is a simplified version of Yao Xor Lemma. I chosed this simplified version as the real one is a bit harder to read because it uses lot's of notations $\varepsilon, \delta, \dots$ and the exact definition is not useful here, but the interested reader may want to read this review or this course for more details.

Yao's xor lemma (informal/simplified): If a function $f: \{0,1\}^n \rightarrow \{0,1\}$ is hard to predict for a (computationnally) bounded adversary with probability better than $1-\delta$, then it is hard to guess the xor of several random "instances" $$\bigoplus_{i=1}^t f(x_i) $$ with probability better than $1/2+(1-\delta)^t$

  • $\begingroup$ Explicitly state Yao's Lemma for ease of the reader, please. $\endgroup$
    – kodlu
    Feb 3, 2019 at 21:39
  • $\begingroup$ @kodlu I added a simplified version at the end $\endgroup$ Feb 4, 2019 at 21:53


Your Answer

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