Score:0

Is it secure to do subfield vector oblivious linear evaluation (VOLE) over a Ring $\mathbb{Z}_{2^k}$?

ml flag

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.

kodlu avatar
sa flag
One of the authors, Geoffroy Couteau regularly posts here. Can you expand the acronym (VOLE) in the question?
Geoffroy Couteau avatar
cn flag
The short answer is "yes but some care is in order", I'll expand when I get some time.
Score:1
cn flag

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.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.