What is $z_b$ in this introduction to Private Information Retrieval?

Question

I was trying to read this introduction to private information retrieval. On page 12 of the document, a scheme for 1-DB private information retrieval is discussed. I was unable to understand one of the steps of this scheme, I will reproduce it below so you can look at it, and hopefully, someone can clarify what is meant by the step I don't understand.

1. An integer $n$ is defined ahead of time, the database $x$, is a $\sqrt{n} \times \sqrt{n}$ array of bits, whose elements can be indexed as $x_{nm}$.

   We now describe the protocol for Alice to privately determine the quantity $x_{ij}$ for some specific pair $i,j$ as follows:

2. Alice generates two primes of equal length $p_1, p_2$ such that $m = p_1 p_2$ is a semiprime with length $n^{\delta}$ for some choice of $\delta > 1$.

3. Alice generates $\sqrt{n}$ elements of the multiplicative group $Z_m^*$ called $r_1 ... r_\sqrt{n}$ with the property that ALL except $r_i$ (where $i$ is the same as the $i$ in $x_{ij}$) are quadratic residues modulo $m$, and $r_i$ is a quadratic non square modulo $p_1$ and $p_2$.

4. Alice sends $m, r_1 ... r_\sqrt{n}$ to the database.

5. The Database now computes a matrix $c_{ab}$ defined as follows:

$$ c_{ab} = z_b^2 \ \text{if } x_{ab} = 1 \\ c_{ab} = z_b \ \text{if } x_{ab} = 0 $$

Now I'm totally lost, what is $z_b$? Where did it come from? How is it defined?

Answer 1

I am the author of the paper. It is a stupid typo. $z_b$ should be $r_b$.

I have corrected the error in my own copy but I can not correct the copy that is out there officially.

Apologies. My bad!

Answer 2

Long to write as a comment;

Look at the referenced paper 47

2. The user chooses uniformly at random $t$ numbers $y_1,\ldots,y_t \in Z_n^{+}$ such that $y_b$ is a $\text{QNR}$ and $y_j$ , for $j \neq b$, is a $\text{QR}$. It sends these $t$ numbers to DB (total of $t \cdot k$ bits).

3. The database, DB, computes for every row $r$ a number $z_r \in Z_N^*$ as follows: It first computes (in $Z_N^*$)

   $$w_{i,j} = \begin{cases} y_j^2 & \textbf{if } M_{r,j} =0\\ y_j & \textbf{if } M_{r,j} =1 \end{cases}$$

   and then it computes

   $$z_r \ \prod_{j=1}^{t} w_{r,j}$$

...

Therefore, one needs to look at the references to see them in more detail. Survey authors may skip some steps that may trivial to themself but that is not true for all.