LSB extraction in MPC: Doubts about correctness

Question

I have doubts about whether the protocol below for LSB extraction (denoted Mod2) from the paper Improved Primitives for Secure Multiparty Integer Computation is correct. Clarifications will be appreciated.

The protocol above calls PRandM(k, 1) in line 1 to generate random shared values $r''$ and $r'_0$ (it ignores $r'$) and then uses them in line 2 to blind $a$ and then reveals it to extract the LSB of the blinded value after which it computes the random secretly shared value $a_0$.

The protocol $looks$ correct because the LSB of $c$ is essentially $r_0\oplus a_0$ and then in line 3 we XOR it again with $r'_0$.

That is... in case $2^{k-1}+[a]+2\cdot [r'']+[r'_0]$ doesn't overflow the prime field $p$. When it overflows the prime field, then the LSB flips and then the math is no longer true.

We also don't know whether $c$ overflows or not, because $[a]$ can be $p-1$ and in that case $c$ will be bigger than $2^{k-1}$ .

Any idea what I am missing here?

Answer 1

The protocol is only designed to work when $a$ is in the range $\{-2^{k-1},\dots,2^{k-1}-1\}$. This ensures that $c$ doesn't overflow mod $p$, as long as $p$ is sufficiently large.

In the paper they ensure this by choosing $p > 2^{k+\kappa+\log n}$, where $\kappa$ is a statistical security parameter and $n$ is the number of parties. See the discussions on p3-5.