Problem in softspoken_ote

[maths644311798]

In softspoken_ote.cc, I do not understand the algorithm in inline void XorReduce(uint64_t k, absl::Span<uint128_t> inout). How does it work? To be concrete, $F_p$ should be a subfield of $F_{2^k}$ and $q = 2^k$ in Figure 7 of the Softspoken paper. But what is $p$ and $l$? How does inout represent elements in $F_p^l$? Then how can XorReduce compute $\sum x \cdot inout[x]$?

[Chrisdehe]

@maths644311798
Please wait, answer @liang-xiaojian is currently in progress

[liang-xiaojian]

Hi, @maths644311798

Form your comments, I extract three questions as below,
(1) What is $p$ and $\ell$ in SoftspokenOte
(2) What is the connection between XorReduce and $\sum x \cdot inout[x]$ ?
(3) How does SoftspokenOte work?

What is $p$ and $\ell$ in SoftspokenOte

It's better to understand the correlation between subfield VOLE and COT.

As described in PCG19 section 2.3, the functionality for subfield VOLE over $( \mathbb F_p , \mathbb F_q = \mathbb F_{p^k} )$ would pass $(\mathbf u \in \mathbb F_p^\ell , \mathbf v \in \mathbb F_q^\ell)$ to sender and pass $( x \in \mathbb F_q , \mathbf w \in \mathbb F_q^\ell)$ to receiver s.t. $\mathbf w = x \cdot \mathbf u + \mathbf v$.

Here comes a problem: $x \in \mathbb F_q$ and $\mathbf u \in \mathbb F_p^\ell$, how to perform the multiplication over field and its subfield.

1. As mentioned in PCG19 footnote 9, the elements of $\mathbb F_p$ could be embedded into $\mathbb F_q$, then we could treat $x \cdot \mathbf u$ as the multiplication over $\mathbb F_q$.
2. The element over $\mathbb F_q = \mathbb F_{p^r}$ could be viewed as a vector over $\mathbb F_p^r$, then $x \cdot \mathbf u$ could be treated as the tensor product over $\mathbb F_q$. For example, $x \cdot \mathbf u = \mathbf x \otimes \mathbf u \in \mathbb F_p^{r \times \ell}$. (PCG19 section 2.3)

In other words, subfield VOLE would pass $( \mathbf u \in \mathbb F_p^\ell , \mathbf v \in \mathbb F_p^{k \times \ell})$ to sender and pass $(\mathbf x \in \mathbb F_p^{k} , \mathbf w \in \mathbb F_p^{k \times \ell})$ to receiver s.t. $\mathbf w = \mathbf x \otimes \mathbf u + \mathbf v$.

In the case that $p=2$, the following equations would hold,

• $\forall i \in [k] ,\forall j \in [\ell], w_{i,j} = x_i \cdot u_j + v_{i,j}$
• $\forall j \in [\ell], \mathbf w_{\star,j} = \mathbf x \cdot u_j + \mathbf v_{\star,j}$

Supposed that we view $\mathbf x$ as the $\Delta$ of COT, $u_j$ as the $j$-th choice for COT, $\mathbf v_{\star,j}$ is the $j$-th receiving blocks s.t.

Thus, a subfield VOLE with length $\ell$ over $(\mathbb F_2 , \mathbb F_{2^k})$ is exactly $\ell$ COTs with length $k$.

As a result, in SoftspokenOte, $p = 2$ and $\ell$ is the number of COT.

What is the connection between XorReduce and $\sum x \cdot inout[x]$ ?

Obviously, $\mathbf R_{0,\star} = \sum_{ \forall i \in [2^k], lsb(i) = 1 } inout[i]$ , $\mathbf R_{1,\star} = \sum_{ \forall i \in [2^k], lsb(i/2) = 1 } inout[i]$, ...

It can be visualized as a k-depth full binary tree where the leaves are the inout vectors. Then $\mathbf R_{i,*}$ is exactly the sum of right-side nodes in (k-i)-level.

Easily, we could perform addition to pairs of elements at each level of the tree and effectively "reduce" the tree (that is how XorReduce works)

Then, we could learn that inout[1 << i] is equal to $\mathbf R_{i,*}$ and inout[0] is $\sum inout[i]$

how does SoftspokenOte work?

To gain insight into SoftspokenOte protocol, it is recommended to review the talk delivered by Lawrence Roy in TPMPC2022.

[maths644311798]

l <= 128? inout[i] is a variable of type uint128_t.
Now the main obstruction of understanding your picture about XorReduce is the code inout[i + depth] = inout[i + stride]; in line 130.

[liang-xiaojian]

inout[i] is a variable of type uint128_t

$\ell$ is the number of OTs.
In our implementation (INKP or Softspoken), we define kBatchSize = 128, then set batch_num as $\lceil \ell / kBatchSize \rceil$.
Thus, XorReduce or GenSfVole would process the data in batches with size 128 (uint128_t).

inout[i + depth] = inout[i + stride]

As described in line 125, stride = static_cast<uint64_t>(1) << (depth - 1);.
As a result, it would move the element in inout[1<<i] to inout[i+1] which means inout[1], ... , inout[k] are $\mathbf R = \sum x \cdot inout[x]$.

[maths644311798]

Thanks, I understand the implementation of softspoken_ote now. :)