0
$\begingroup$

In the paper "Efficient Pseudorandom Correlation Generators: Silent OT Extension and More (https://doi.org/10.1007/978-3-030-26954-8)" Boyle et. al. proposed subfield vole.

For standard vector oblivious linear evaluation correlation one has, $\vec{v}+\vec{w}=\vec{u}*x$ ($v_i, w_i, u_i, x \in \mathbb{F}_p$).

And for subfield VOLE correlation, $x \in \mathbb{F}_q$ ($q = p^r$), $v_i, w_i \in \mathbb{F}_q$, $u_i \in \mathbb{F}_p$. Boyle et. al. mentioned that $\vec{u} * x$ can be seen as the tensor product (vector outer product).

My question is when considering VOLE over $\mathbb{Z}_{2^k}$, is it secure to do such subfield VOLE while interpreting $x \in \mathbb{Z}_{2^k}^{r}$ as a vector of $\mathbb{Z}_{2^k}$?

Thanks for any suggestions and helps.

$\endgroup$
2
  • $\begingroup$ One of the authors, Geoffroy Couteau regularly posts here. Can you expand the acronym (VOLE) in the question? $\endgroup$
    – kodlu
    Commented Mar 18, 2023 at 16:16
  • 1
    $\begingroup$ The short answer is "yes but some care is in order", I'll expand when I get some time. $\endgroup$ Commented Mar 18, 2023 at 19:34

1 Answer 1

2
$\begingroup$

I am assuming that you are referring to the comment on page 9 of this paper. Indeed, given a pseudorandom $x\in \mathbb{F}_{p^r}$, you can parse it as a pseudorandom $\vec x \in \mathbb{F}_{p}^r$, and re-interpret the additive shares of $x\cdot \vec u \in \mathbb{F}_p^n$ as shares of $\vec x \otimes \vec u \in \mathbb{F}_p^{n\cdot t}$.

Now, if you do a VOLE over $\mathbb{Z}_{2^k}$, you can perfectly use $\vec x\in \mathbb{Z}_{2^k}^r$ to get shares of $\vec x \otimes \vec u$ over $\mathbb{Z}_{2^k}^{r \cdot n}$. This does not even use subfield VOLE (which, here, would actually be subring VOLE, since we're not working over a field). Indeed, this is simply doing $r$ parallel VOLEs with receiver inputs $x_1, \cdots, x_r$, fixing a sender vector $\vec u$. Our construction easily allows fixing the vector $\vec u$ across multiple instances, so nothing goes wrong here.

Regarding security, however, a word of caution: the space where you generate the VOLEs is tied to the underlying assumption. When generating VOLE over $\mathbb{Z}_{2^k}$, you end up with a construction that is secure under a variant of the LPN / syndrome decoding problem over the ring $\mathbb{Z}_{2^k}$. This has been used in several works (e.g. here and here). For a recent study of this assumption, see here. In particular, this work points out that there is an easy "reduce modulo 2" attack on LPN over this ring that reduces the instance to an LPN instance over $\mathbb{F}_2$ and halves the amount of noise (since a random noise over $\mathbb{Z}_{2^k}$ is sent to 0 modulo 2 with probability half). This has to be taken into account when choosing parameters.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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