1

I am reading this document and wondering the following part on page 13:

"Consider applying Gaussian elimination to the noisy samples to find the first bit"

If we take, for example, $n = 3$, $s = (1,0,1)$, $x_1 = (1,1,0)$, $x_2=(1,1,1)$ and $ x_3=(0,1,0)$, what will $q$ and $SāŠ‚[q]$ be?
Also, how to confirm the probability will be $1/2+2^{-Ī˜(3)}$?

I would be grateful for your help in advance.

iomat
  • 163
  • 4

1 Answers1

2

$q$ is the number of samples and $S$ is the set of indices such that $\sum_{i\in S}x_i = (1,0,...,0)$. In your example, we have $q=3$ and $S=\{1,3\}$. The first bit of the secret $s$ is equals to $\sum_{i\in S}b_i \mod 2$, but with probability $1/2+2^{-\Theta(n)}$ not $1$, because the noises are also considered in this summation. So we need to repeat this procedure $2^{\Theta(n)}$ times to reduce the error probability.

Hamidreza
  • 1,019
  • 6
  • 17
  • Hi Hamidreza, I am also interested in answering the question regarding the probability. Can you perhaps elaborate a bit more on how to come up with $1/2+2^{-Ī˜(n)}$? ā€“ P_Gate Nov 04 '22 at 15:46