0
$\begingroup$

I am studying Pseudorandom Number Generators and when reading the discussion on One-Way Functions and Hardcore Predicates, I came upon this equation.

$$b(x,r)=\displaystyle \bigoplus_jx_jr_j$$

I understand that the $b(x,r)$ is the hardcore predicate (either a $1$ or $0$) but I do not understand the operation being performed here. Specifically, I have never before seen the XOR symbol ($\oplus$) used in this way and do not understand what it signifies. Is it the sum of the values found by XORing $x_j$ and $r_j$? $\bmod 2$?

$\endgroup$
1
  • $\begingroup$ I'm guessing this mean AND $x$ and $r$ together, then XOR the bits of the resulting value together. Or in other, words, $x_j$ means the $j$-th bit of $x$ (similarly $r_j$). So, we AND the corresponding bit from $x$ and $j$, then XOR with the previous value. $\endgroup$ – mikeazo Nov 30 '15 at 19:25
2
$\begingroup$

Assume $x$ and $r$ are bit strings of same length and $x_i$ and $r_i$ denotes the $i$-th bit of $x$ and $r$ respectively. The operation performed between $r_j,x_j$ is multiplication which is equivalent to AND ($\wedge$) as they can both only take the values $1$ or $0$.

Generally any large symbol like $\displaystyle\sum_jf(j)$, $\displaystyle\bigwedge_jf(j)$ and $\displaystyle\bigoplus_jf(j)$ applies the operation denoted by the large sign "between" each iterated value of $f(j)$, resulting in $\displaystyle\sum_jf(j)=f(j_1)+f(j_2)+\dots$, $\displaystyle\bigwedge_jf(j)=f(j_1)\wedge f(j_2)\wedge\dots$ and $\displaystyle\bigoplus_jf(j)=f(j_1)\oplus f(j_2)\oplus\dots$.

So the formula you gave can be read as follows:
$$b(x,r)=\displaystyle\bigoplus_{j}x_jr_j=\displaystyle\bigoplus_{j}x_j\cdot r_j=x_0r_0\oplus x_1r_1\oplus \dots=(x_0\wedge r_0)\oplus(x_1 \wedge r_1)\oplus\dots$$.

$\endgroup$
2
  • $\begingroup$ If anybody knows how to put the $j$ below the big sign please tell me. $\endgroup$ – SEJPM Nov 30 '15 at 19:56
  • $\begingroup$ SEJPM: \displaystyle should do it. $\endgroup$ – Mikero Nov 30 '15 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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