Limitations to Computing Quadratic Functions on Reed-Solomon Encoded Data

We now formalize our problem. We consider the simplest setting for non-linear evaluation, which is computing quadratic monomials on top of Reed-Solomon codes.

A dimension-$k$ RS code encodes a message vector $𝐟=(f_0,f_1,\mathrm{\dots },f_{k-1})$ as evaluations of the polynomial $f(x)={\sum }_{i=0}^{k-1}{f}_i{x}^i$. For some $i,j\in [0,k-1]$, we wish to compute $g_{i,j}(𝐟):=f_i{f}_j$. To formalize the model described informally above, we first define a leakage function, which outputs a single bit.

Each server may evaluate any (non-negative) number of leakage functions as part of a scheme to compute $g_{i,j}(𝐟)$. We formalize this as follows.

Our main result is the following.

As noted above, this result shows that computing the quadratic monomial $g_{i,j}=f_i{f}_j$ requires download bandwidth nearly equal to the cost of representing both $f_i,f_j\in {𝔽}_q$ separately. When $k=2$, Theorem 4 shows that naive polynomial interpolation is essentially optimal for the problem of computing quadratic monomials.

Additionally, we establish an even stronger lower bound for leakage functions that are linear over the base field ${𝔽}_p$. This is notable because prior work on computing linear functions $g$ often crucially relies on ${𝔽}_p$-linear leakage functions [18, 36, 34, 23].³³3We note that the method used to aggregate the leakage functions may be non-linear, and so it is not trivial that the leakage functions must be non-linear to compute a non-linear function.

The formal statement, proof of Theorem 5 is given in Section 6 of the full version [3]. When $k=2$, Theorem 5 implies that no scheme with linear leakage functions can perform even one bit better than the naive strategy of recovering all of $𝐟$. As mentioned above, we view our results as an important step towards understanding the bandwidth cost of general non-linear computation. But the quadratic monomial case is already interesting in the context of prior work across many domains. We discuss these connections more in Section 1.4. Highlights include:

• $\mathrm{■}$

  Combined with existing work on regenerating codes [36, 10], our work implies that for $k=2$, there are many linear functions $f_1\alpha +f_0$ that can be computed with substantially less bandwidth than the quadratic monomial $f_0\cdot f_1$.

• $\mathrm{■}$

  Our work contrasts with work on low-bandwidth secret sharing. It is known to be possible to recover a secret shared with standard Shamir sharing with non-trivial bandwidth [21, 20]; our work implies that, for a natural multiplicative variant of Shamir sharing, no deterministic low-bandwidth recovery is possible.

  Unfortunately, this does not imply that “multiplicative Shamir sharing” is leakage resilient in the information-theoretic sense, as we demonstrated in Appendix A of the full version of this paper [3].

• $\mathrm{■}$

  Our work provides lower bounds on the download bandwidth single-client homomorphic secret sharing [6, 7], for multiplication of two secrets with a natural multi-secret version of Shamir sharing.

We now overview the proof Theorem 4, which we prove in Section 4.3. First, we observe that it suffices to prove Theorem 4 in the case where $k=2$ and $i=0$, $j=1$. At a high level, this follows from the fact that for arbitrary $k$ and distinct $i,j\in [0,k-1]$, any $t$-bit, $s$-server QM scheme $\mathrm{\Phi }$ computing $g_{i,j}(𝐟)$ is a $t$-bit, $s$-server QM scheme over a two-dimensional subspace $𝒞$ containing all $𝐟=c_i{e}_i+c_j{e}_j$, where $c_i,c_j\in {𝔽}_q$, and $e_i,e_j\in {𝔽}_q^k$ are the standard basis vectors. If $\mathrm{\Phi }$ can compute $g_{i,j}(𝐟)$ with strictly fewer bits downloaded than required by Theorem 4, then we may reduce it to a $k=2$, $i=0$, $j=1$ instance of the problem, noting that $𝒞\simeq {\mathrm{RS}}_q[n,2]$. For more detail, see Section 4.3.

We thus assume $k=2$, $i=0$, and $j=1$ for the rest of this discussion. We begin with a sketch, before elaborating on each step. We first bound the bandwidth of any QM solution by the round complexity of an iterative algorithm, which partitions all the lines $f(x)=mx+b$ into buckets determined by their coefficient product $g(𝐟):=g_{0,1}(𝐟)=mb$. More precisely, for each $\gamma \in {𝔽}_q$, we partition the lines into buckets

We then imagine receiving bits from the leakage functions sequentially, one per round; each round, we “prune” away all of the lines $f(x)$ disagreeing with the leakage bit. The algorithm terminates when only one non-empty bucket $B_{\gamma }$ remains, corresponding to the correct coefficient product $\gamma$. If an instance of QM has bandwidth $t$, then the corresponding instance of this algorithm must halt within $t$ steps. Thus, the round complexity of the iterative algorithm yields a lower bound on the bandwidth $t$.

Analyzing how these buckets of lines evolve as we prune them seems challenging, so our second step restricts both the sets of possible servers and of possible coefficient products in order to introduce symmetry aiding our analysis. In more detail, we demand that the coefficient product $g(𝐟)$ belongs to a specially structured set ${\mathrm{\Omega }}_q\subseteq {𝔽}_q$ of size about $q/2$. (When $q$ is odd ${\mathrm{\Omega }}_q$ is the set of quadratic residues, and when $q$ is even it is the even powers of a specially chosen primitive element.) We similarly restrict queries to servers indexed by ${\mathrm{\Omega }}_q$. This assumption is without loss of generality: restricting the value of $g(𝐟)$ makes the QM problem easier, and thus makes impossibility results stronger; furthermore, restricting the set of servers is allowed because in Definition 3, the client must be able to query any set of $s$ servers.

The set ${\mathrm{\Omega }}_q$ is designed so that restricting to this special case introduces useful symmetry in the buckets $B_{\gamma }$ described above. In our third step, we use this symmetry to carefully “project” each bucket $B_{\gamma }\subseteq {𝔽}_q[x]$ of lines onto a subset of ${𝔽}_q$, in a way that the higher dimensional characteristics of lines are sufficiently represented in the lower dimensional projection. In particular, we show that when one runs an analogous algorithm on the projected buckets (iteratively pruning out projections of lines that are inconsistent with the leaked bits), then it remains the case that the round complexity of the projected algorithm is a lower bound on the bandwidth of QM.

The fourth and final step is to bound the round complexity of the projected algorithm. This problem turns out to be more tractable than the original problem of differentiating buckets of lines, and via the logic above, it implies Theorem 4.

Next, we expand slightly upon each of these steps.

In this section we summarize related work across several domains.

• $\mathrm{■}$

  It would be interesting to extend our results to higher degree monomials. Our results show that about $2{\log }_2(q)$ bits are necessary for computing quadratic monomials $g$ on RS-encoded data. For monomials of degree $d>2$, one conjecture is that about $d{\log }_2(q)$ bits are needed. Is this conjecture true?

• $\mathrm{■}$

  It would also be interesting to know if our lower bound is achievable. That is, is it possible to evaluate quadratic monomials on top of Reed-Solomon codes of dimension $k>2$, with bandwidth approaching $2{\log }_{2}q$? For $k=2$, this can be done by naive polynomial evaluation. For $k>2$, there are RS codes over ${𝔽}_q$ that admit repair of individual codeword symbols with download bandwidth converging to ${\log }_2(q)$ bits [35]. If a similar result holds for message symbols, this would provide an algorithm for evaluating quadratic monomials with bandwidth approaching our lower bound. We are not aware of such a result (for message symbols) in the regenerating codes literature; does such a result hold, or are there other algorithms for computing quadratic monomials with about $2{\log }_{2}q$ bits?

• $\mathrm{■}$

  Finally, it would be interesting to extend our results to arbitrary quadratic functions, not just quadratic monomials. It is not hard to see that at least $k$ bits are required to recover an arbitrary quadratic function (even an arbitrary linear function [34]). When $k$ is large, this implies that a stronger bound should hold; what is the correct bound?

We now give an algorithmic characterization of QMs (Definition 3), in light of Assumption 8.

In other words, $B_{\gamma }(\alpha )$ is the image of the evaluation map ${\mathrm{ev}}_{\alpha }:{𝔽}_q[x]\to {𝔽}_q$, $f\mapsto f(\alpha )$ on a set of lines $B_{\gamma }$. We now show that any $t$-bit, $s$-server QM is equivalent to an instance of Algorithm 1.

In Section 2.1, we established that determining the optimal download bandwidth incurred by an instance of QM is equivalent to bounding the round complexity of the corresponding instance of Algorithm 1. Rather than directly analyzing Algorithm 1, we pursue an alternate strategy: within the scope of all parameter regimes for which QM must succeed, we find a subset whose corresponding algorithmic view can be greatly simplified. Instead of tracking the number of lines in each set $𝐁(\gamma )$, consider an alternate implementation of Algorithm 1 that tracks the size of ${\mathrm{ev}}_{\alpha }(𝐁(\gamma ))=\{f(\alpha ):f\in 𝐁(\gamma )\}\subseteq {𝔽}_q$ for any $\alpha \in {𝔽}_q^{\ast }$. It turns out that we can construct such a correspondence between linear functions and their evaluations which, within a restricted parameter regime, yields a simpler but equivalent algorithm. To state this restricted parameter regime, we first give the following definition.

When $q=p^e$ where $p>2$, exactly half of ${𝔽}_q^{\ast }$ lies in ${\mathrm{QR}}_q$, while the other half lies in ${𝔽}_q\setminus {\mathrm{QR}}_q$. We state this formally below.

Note that ${\mathrm{QR}}_q$ is the image of ${𝔽}_q^{\ast }$ under the map $x\mapsto x^2$; when $q=2^e$, the map $x\mapsto x^2$ is the Frobenius automorphism, implying ${\mathrm{QR}}_{2^e}={𝔽}_{2^e}^{\ast }$. Since the quadratic residues do not yield an interesting subset of the multiplicative subgroup in binary extension fields, we consider an alternative construction. First, we recall the definition of the field trace.

The following result⁹⁹9This result holds in considerably more generality: given any finite extension field $E$ and a field trace from $E$ to a subfield $F$ - not necessarily the base field - there exists a primitive element $\omega \in E^{\ast }$ whose trace $\mathrm{Tr}(\omega )=\mathrm{Tr}({\omega }^{-1})=\alpha \in F$ for arbitrary $\alpha \in F$. Note that $\omega$ is primitive if and only if ${\omega }^{-1}$ is primitive. See [27], Theorem 3.75. ([8, 27]) shows that, in all binary extension fields of order at least $2^e\ge 8$, there always exists a generator of the multiplicative subgroup whose inverse lies in the kernel of the field trace.

We may now state our restricted parameter regime.

As discussed in the introduction and formalized in Section 4.3, restricting to this parameter regime is without loss of generality. That is, any impossibility result for the restricted parameter regime in Definition 17 implies an impossibility result for QM in general.

We describe the algebraic structure of $B_{\gamma }(\alpha )$ when both $\gamma$ (the coefficient product; see Definition 9) and $\alpha$ (the evaluation parameter; see Definition 10) are restricted to $\alpha ,\gamma \in {\mathrm{\Omega }}_q$. Consider the case where $\gamma =1$, so that

It turns out that, up to scaling, $B_1(1)$ describes all $B_{\gamma }(\alpha )$ for $\gamma ,\alpha \in {\mathrm{\Omega }}_q$. To express the exact scaling factor, we first define a notion of square roots over ${\mathrm{\Omega }}_q$. Note this is possible since ${\mathrm{\Omega }}_q\subseteq {\mathrm{QR}}_q$ for all prime powers $q$, with exceptions¹⁰¹⁰10These exceptions do not affect the main result of Theorem 4, since the bound is trivial over ${𝔽}_2,{𝔽}_4$. Indeed, $2{\log }_2(q-2)-4\le 0$ when $q=2,4$. only when $q=2,4$.

Our goal is to understand $B_{\gamma }(\alpha )$ in terms of $B_1(1)$. We have the following lemma, whose proof is deferred to [3].

Such a multiplicative relationship between two images $B_{\gamma }(\alpha )$ and $B_1(1)$ allows us to work entirely over scalar multiples of $B_1(1)\subseteq {𝔽}_q$. The following observation gives the size of $B_1(1)$; we defer the proof to [3].

Let $h_m^{\gamma }:=m^{-1}\sqrt{\gamma }x+m\sqrt{\gamma }$ so that $B_{\gamma }=\{h_m^{\gamma }:m\in {𝔽}_q^{\ast }\}$ for every $\gamma \in {\mathrm{\Omega }}_q$. Note that every element of $B_{\gamma }$ is then fully specified by some $m\in {𝔽}_q^{\ast }$ and $\gamma \in {\mathrm{\Omega }}_q$.

The observation follows trivially from $h_m^{\gamma }=\sqrt{\gamma }\cdot h_m^1$, but its significance is that we need only consider $B_1\subseteq {𝔽}_q[x]$, since any line $h_m^{\gamma }\in B_{\gamma }$ is simply a multiple of $g_m\in B_1$.

Hence, we can check whether any line $h_m^{\gamma }$, evaluated at $\alpha \in {𝔽}_q$, is in a set $T$ just by considering whether $g_m(\alpha )\in B_1(\alpha )$ is in a multiple of $T$. We show that multiplying an evaluation map image $B_{\gamma }(\alpha )\subseteq {𝔽}_q$ by some scalar is equivalent to a permutation of $B_{\gamma }\subseteq {𝔽}_q[x]$.

Note that ${\varphi }_{\alpha }^{\gamma }$ is mapping one line in $B_{\gamma }$ to another line also in $B_{\gamma }$. The following observation shows why we have chosen to call it a relabeling; the proof follows from the fact that for any $\alpha \in {\mathrm{\Omega }}_q$, the map $m\mapsto m\sqrt{\alpha }$ is a permutation of ${𝔽}_q^{\ast }$, and that each element $m\in {𝔽}_q^{\ast }$ corresponds to a distinct element $h_m^{\gamma }\in B_{\gamma }$.

Given some $h_m^{\gamma }\in B_{\gamma }$ and $\alpha \in {\mathrm{\Omega }}_q$, we denote by ${\varphi }_{\alpha }^{\gamma }[h_m^{\gamma }](\alpha )$ the evaluation of the $\alpha$-relabel of $h_m^{\gamma }$ at an evaluation point $\alpha$. We show that the multiplicative relationship between lines in $B_{\gamma }$ and lines in $B_1$ (Observation 21) is preserved by this relabeling.

The proof is deferred to [3]. We extend Theorem 25 with the following corollary, whose proof is immediate. This is the $\alpha$-relabel analogue of Observation 22, and it is the tool we will need to reduce a subset of QM to a simpler algorithm in the following section.