Linear Time Encodable Binary Code Achieving GV Bound with Linear Time Encodable Dual Achieving GV Bound

In this work, we prove that such a fast good code with fast good dual indeed exists.

As we discuss later, the encoding time is in fact practically fast. For example, with $\epsilon =0.0001$ there is a boolean circuit with binary gates implementing the encoding map with size $8(n-1)$. Unfortunately we do not now how to bound more precisely the encoding time of $𝒞$ and ${𝒞}^{⟂}$ in terms of $\epsilon$. However, empirically the constant in front of $n$ is very small; see Table 1 and the surrounding discussion. We additionally note that Boolean circuits of size $O_{\epsilon }(n)$ and depth $O_{\epsilon }(\log n)$ can implement the encoding map, should low depth be desired.

While we will provide a much broader overview of our proof technique later, we now briefly outline the idea. Firstly, we emphasize that our construction is randomized. Both $𝒞$ and ${𝒞}^{⟂}$ will be sampled in such a way that they are reminiscent of repeat multiple accumulate ($RMA$) codes. Essentially, $RMA$ codes are defined by multiple rounds, where in each round a coordinate permutation is applied, followed by an accumulation step, which is just the prefix-sum modulo 2. In particular, these rounds can be implemented very quickly (just $n-1$ xor’s). The idea is to consider random $RMA$ codes, where the coordinate permutations are chosen uniformly at random, and demonstrate they are likely to have very good distance.

Fortunately for us, a sequence of works [22, 23, 2, 18, 24, 6] have shown these codes achieve good distance. The basic idea of these works is, given two weights $\alpha$ and $\beta$, to analyze the expected number of message vectors of weight $\alpha$ that are mapped to a codeword of weight $\beta$. Using some coding-theoretic jargon, this is called the input-output weight-enumerator function, or IOWEF for short. Concretely, for a fixed generator matrix $G\in {𝔽}_2^{k\times n}$ we define

Then, if $𝐆$ denotes a random generator matrix (sampled according to some given distribution), the IOWEF will be ${𝔼}_{𝐆}\left[N_{𝐆}(\alpha ,\beta )\right]$. The pleasant feature of this code ensemble is that its IOWEF has a fairly simple expression. To show a code achieves minimum distance $\delta$ with probability $1-p$ for some $p\in (0,1)$, by Markov’s inequality it suffices to show that the sum of the IOWEF over all $\alpha ,\beta$ with $\beta \le \delta$ is $\le p$.

Now, it is not difficult to see that an $RMA$ code has constant weight dual codewords (assuming the number of rounds is constant, as we always do). Hence, they are unsuitable for our target. Nonetheless, we note that the inverse of the accumulation step is quite simple: namely, one just takes the xor of the previous two coordinates. We view this operation as a discrete derivative. While this operation is not very helpful in terms of achieving good distance (it can at most double the weight of a vector, and in the worst case can drop it all the way down to $1/n$), as it corresponds to doing an accumulation step in the dual, it increases the dual distance! Thus, we can hope for both distance and dual distance to be large. A main challenge is to argue that these discrete derivative rounds are unlikely to harm the minimum distance.

Thus, our task is to bound the IOWEF of codes where accumulation rounds are interleaved with discrete derivative rounds. As in prior works [18, 24, 6], roughly speaking we break the analysis into the case where $(\alpha ,\beta )$ are small or large. The first case is handled largely by combinatorial reasoning concerning binomial coefficients; the latter case is handled by looking at the exponent of the IOWEF, i.e., looking at $\frac{1}{n}\log$ of the IOWEF and bounding it via analytic means: this function is often called the spectral shape function. In some sense, we manage to bound the spectral shape functions of our code ensembles by that of an $RMA$ code, allowing us to obtain the same distance guarantees. This is the sense in which we manage to show the discrete derivative rounds don’t harm minimum distance. In particular, we can get distance $\epsilon$-close to the GV bound, where the closeness to the GV bound is determined by the number of “rounds” of our encoding maps.

We believe that the existence of such a code is interesting, and likely to find further applications in coding theory, cryptography, or theoretical computer science more broadly. As a small proof of concept, we show their utility for the task of computing encrypted matrix-vector product (EMVP), as studied by Benhamouda et al [4]. The task is as follows. In an initial offline phase, a client sends an encryption $\widehat{M}$ of a matrix $M\in {𝔽}^{m\times \mathrm{\ell }}$ to a server, while keeping a (short) secret key. In the online phase, the client may send encryptions $\widehat{q}$ of query vectors $q\in {𝔽}^{\mathrm{\ell }}$; based on these encryptions, the server computes a value $M^{\prime }$, which the client can use to determine the matrix-vector product $Mq$. Importantly, the server learns nothing about the matrix $M$ or the query vectors $q$. As Benhamouda et al [4] discuss, this is an important subroutine for efficient secure computation tasks in a number of domains, including encrypted fuzzy search and secure ML. Additionally, note that the special case of each $q$ being a unit vector (i.e., having a single $1$ entry) is equivalent to (single-server) private information retrieval (PIR). While we provide more details later of this application in Section 4, the fast encoding time for the $𝒞$ and ${𝒞}^{⟂}$ we construct yield improved running times for the protocol of Benhamouda et al [4].

Again, we emphasize that this is just a small proof-of-concept for our codes. We consider the main contribution of this work to be the code construction itself, along with the (fairly involved) analysis. Nonetheless, we flesh out this application further in Section 4.

To the best of our knowledge, ours is the first work to construct “fast good codes” with “fast good duals.” However, our codes are heavily inspired by so-called repeat-multiple-accumulate (RMA) codes. These codes were initially introduced as containing only a single round of permuting and accumulating by Divsalar, Jin and McEliece [11], and then extended to contain multiple rounds by Pfister and Siegel in an 1999 conference paper [22]. A series of works [23, 18, 24, 6] (that we build upon) have managed to show that such codes can have minimum distance approaching the GV bound²²2There are some minor caveats concerning the speed at which one approaches the GV bound which we discuss later, but for practical purposes such codes achieve essentially this rate/distance tradeoff. along with linear-time encoding. We will introduce these codes more formally later (Section 2.1) and discuss in detail how we build upon the analyses of these works. We remark that the codes in these works are, like ours, non-explicit.

Regarding the task of constructing explicit linear-time encodable binary codes that are asymptotically good (namely, rate and minimum distance are positive constants), Spielman [27] provided a construction based on expander codes; these codes can also be decoded in linear time. Many works have built off this construction, allowing for more and more sophisticated decoding guarantees; however, this is somewhat tangential from our main focus. Note that the proven rate/distance tradeoff of Spielman’s code is quite far from the GV bound. Guruswami and Indyk [13] are the first to construct linear-time encodable codes achieving the GV bound, but only over sufficiently large fields (and in fact, they work in the regime where the distance can be $1-R-\epsilon$, i.e., roughly the Singleton bound).

A work in the same vein as ours is by Druk and Ishai [12]; therein, the authors give a (randomized, non-explicit) construction of a code meeting the GV bound which is linear-time encodable, and additionally outline some cryptographic applications of these codes. Finally, we mention a work by Rudra and Wootters [25] which, among other results, demonstrates the existence of linear-time encodable binary codes of rate $\mathrm{\Omega }({\epsilon }^2)$ that are list-decodable up to radius $1/2-\epsilon$, where we recall that a code $𝒞\subseteq {𝔽}_2^n$ is called $(\rho ,L)$-list-decodable if from every vector $z\in {𝔽}_2^n$ there are at most $L$ codewords $c\in 𝒞$ satisfying $d(c,z)\le \rho$ (the list-size $L$ in this work is a constant depending only on $\epsilon$). In fact, this code is obtained by randomly folding Spielman’s linear-time encodable code.

We remark that such prior constructions of linear time encodable codes typically have sparse parity-checks; in particular, the duals cannot be asymptotically good. This is a challenge that we overcome, by carefully adding encoding steps specifically designed to improve the dual distance while also not harming the original code’s distance.

Before moving onto the technical portion of our paper, we now take some time to highlight some open problems that we consider worthy of study. Firstly, our analysis is inherently limited to the binary field case. One could naturally define similar codes over larger fields: the main thing which should change is that instead of just randomly permuting, one should also randomly rescale the entries, i.e., multiply by a uniformly random full-rank diagonal matrix.³³3Note that over ${𝔽}_2$, the only full-rank diagonal matrix is the identity; hence, this is a natural generalization. However, even for the case of $RMA$ codes most analyses up till now have focused on the binary case. The simple reason for this is that, once $q>3$ the IOWEF is in fact exponentially large;⁴⁴4For $q=3$ as well it is unclear how to bound the IOWEF; already for this field size, new ideas appear to be required. thus, an argument simply applying Markov’s inequality cannot succeed. This is elucidated in the work of Block et al [5], where the authors managed to develop some nontrivial analysis of the minimum distance of RA codes over large fields that does not directly use Markov’s inequality. Nonetheless, the current best argument proving that RMA codes over large alphabets have nontrivial distance follows from simply analyzing the code over ${𝔽}_2$, and then using the same generator matrix to define a code over ${𝔽}_{2^t}$, i.e., some (large) extension of ${𝔽}_2$ [6]. It would be very interesting to find an analysis over large fields that leads to improved rate/distance tradeoffs.

Continuing with questions concerning $RMA$ codes, we now have a fairly good understanding of their minimum distance; in particular, Brehm et al [6] provide a fairly thorough investigation of the probability they fail to achieve good distance, demonstrating they achieve good distance for concrete values of $n$. A next task could be to determine what list-decodability they might possess. A reasonable approach for this could be to show that they are locally similar to random linear codes [15, 21], which would (roughly) imply that they inherit the list-decodability of a typical linear code.⁵⁵5Technically, $RMA$ will not be fully locally similar to random linear codes, as they contain constant-weight codewords with an overly large probably $1/\mathrm{poly}(n)$. The same issue arises with LDPC codes, but can be resolved [20]. It would additionally be very interesting to find explicit $RMA$ codes achieving nontrivial distance; to the best of our knowledge the only result in this vein is due to Guruswami and Machmouchi [14], which essentially partially derandomizes the construction of an asymptotically good $RAA$ code (namely, it requires only the second permutation to be sampled randomly; the first can be deterministically chosen). Finally, we remark that every question asked above could additionally be asked for the codes we define and study.

Next, we list a couple interesting questions motivated by cryptographic applications. Specifically, we consider the code property of multiplicativity. Given two vectors $x,y\in {𝔽}^n$, we define their (Schur) product as $x\ast y:=(x_1\cdot y_1,\mathrm{\dots },x_n\cdot y_n)$ as the component-wise product, and then given two linear codes $𝒞$ and $𝒟$ their (Schur) product is defined as $𝒞\ast 𝒟:=\mathrm{span}\{c\ast d:c\in 𝒞,d\in 𝒟\}$. A code pair $(𝒞,𝒟)$ is said to be multiplicative if $𝒞\ast 𝒟\ne {𝔽}^n$; namely, it does not span the whole space. Firstly, it can be observed that a binary linear code $𝒞\le {𝔽}_2^n$ and its dual ${𝒞}^{⟂}$ are multiplicative, as $𝒞\ast {𝒞}^{⟂}$ only contains even weight vectors. It is known [9] that multiplicative codes yield multiplicative secret-sharing schemes,⁶⁶6Briefly, secret-sharing schemes allow a dealer holding to a secret $s$ to generate shares $(s_1,\mathrm{\dots },s_n)$ to be given to $n$ parties such that authorized sets of parties can reconstruct the secret, but no unauthorized set of parties can. As for multiplicativity, this can be viewed as an additional property allowing parties to locally convert shares of secrets $a,b$ into a new value $c_i$ such that the product $ab$ is a linear combination of the $c_i$’s. and additionally that such a multiplicative secret-sharing scheme can be used for general-purpose secure multiparty computation (MPC) [3, 28]. The encoding efficiency of the codes $𝒞$ and ${𝒞}^{⟂}$ directly translate into the complexity of sharing a secret [12], which must be done by each party for each multiplication gate of the circuit representing the function one is securely computing. Thus, in the quest for “constant-overhead cryptography [16]” (where the hope is that, if the cost of computing a functionality without security is $N$, the cost of computing it with security is just $O(N)$) multiplicative secret-sharing scheme with linear-time encoding can play an important role. We observe that typical multiplicative secret-sharing schemes are “algebraic” (e.g., Shamir secret-sharing [26], which is based on polynomial evaluations); here, one can deal the shares in quasilinear time (using fast Fourier-transform-type ideas), but getting linear-time dealing appears to require more “combinatorial” approaches.

To summarize the above, our work provides a multiplicative secret sharing scheme over ${𝔽}_2$ with linear-time encoding. One could hope for more. Firstly, one can hope for higher-degree multiplicative secret-sharing [1] allowing for multiplying more secrets together, again with linear-time algorithms for dealing the shares. Next, one could additionally hope for strong multiplicativity of a secret-sharing scheme, which informally would follow from a pair of asymptotically good codes $𝒞,𝒟$ such that $𝒞\ast 𝒟$ has constant distance (such codes are said to satisfy the multiplication property). Note that for a linear code $𝒞$ and its dual ${𝒞}^{⟂}$, as $𝒞\ast {𝒞}^{⟂}$ only contains even weight vectors, it has minimum distance $\ge 2/n$, which is nontrivial, but far from constant. Strongly multiplicative secret-sharing schemes lead to general MPC protocols with malicious security [9], i.e., security even in the presence of parties that may actively deviate from the prescribed protocol. One could hope to have such multiplication codes with linear time encoding towards getting general-purpose MPC with constant-computational overhead and malicious security. We remark that prior work has already considered the possibility of constructing somewhat “combinatorial” codes (i.e., codes that could admit linear time encoding) that additionally have the multiplication property [10].

Broadly speaking, we view our work as a stepping stone towards a broader suite of “fast codes” with interesting combinatorial properties. We emphasize that from a cryptographic perspective, decodability is often not required,⁷⁷7And in fact, in certain cases the security of the scheme rests on the assumed hardness of decoding; this is (essentially) the case for the encrypted matrix-vector product protocol we sketch in Section 4. but instead ask for nontrivial conditions concerning, e.g., the dual code or multiplicativity.

The remainder of this paper is organized as follows. In Section 2 we set notation, define RMA codes and review their existing analysis, after which we define our pair of dual codes. In Section 3 we give a broad overview of our proof strategy for Theorem 2. We leave the details of this proof to Sections 4 and 5 in the full version of this paper [7]. Finally, in Section 4, we discuss the utility of these codes in the context of the encrypted matrix-vector product problem.

The codes introduced in this paper are directly inspired by $R{A}^m$ codes and their analysis as introduced by the previously cited works. As hinted in the introduction, our idea is to “fix” the distance of the dual code, and to do that we introduce rounds where we perform the inverse of the accumulation operation. This inverse operation is the following:

• $\mathrm{■}$

  Let $D\in {𝔽}_2^{n\times n}$ denote the discrete derivative matrix, i.e., $D_{ij}=1$ iff $i-1=j$ or $i=j$.

To see this is the inverse, note that if $y=Ax$ we have $y_i={\sum }_{j=1}^i{x}_j$, so ${(Dy)}_i=({\sum }_{j=1}^i{x}_j)+({\sum }_{j=1}^{i-1}{x}_j)=x_i$. Again, this $D$ matrix can be implemented with $n-1$ xor gates (and in fact here the depth is just $1$!).

With this $D$ operation in hand, we are able to construct pairs of dual codes of rate $1/2$. For instance the $RAD$ and $RDA$ codes are dual to one another when $r=2$, assuming the accumulation orders are “reversed” (i.e., in one code, $A$ and $D$ are transposed). More precisely, we have the following.