Random bits

This functionality produces a random element $[x] \in \mathbb{F}_p$, with $x \in \{0, 1\}$, uniformly distributed, and its shares also uniformly randomly distributed.

It is denoted as $[x \in_R \{0,1\}]$, and can be pre-computed in the offline phase (so during the computation we assume that we have a collection of random bits).

The method of constructing such $x$ is as follows:

1. Pick a canonical way of constructing a square root over $\mathbb{F}_p$, say, be requiring $\sqrt t \in \{0, ..., \frac{p-1}{2}\}$.
2. Produce a random shared element $[r \in_R \mathbb{F}_p]$.
3. Calculate $r^2$ and open it. If it is $0$, start over (this happens with negligible probability).
4. Set $[x] = \frac{1 + [r] / \sqrt{r^2}}{2}$