The Star Product of Uniformly Random Codes

Technical Summary: The Star Product of Uniformly Random Codes

Problem Statement
This paper investigates the expected dimension of the star product (also known as the Schur or Hadamard product) of two independent, uniformly random linear codes, $C_1$ and $C_2$, over a finite field $\mathbb{F}_q$. The codes have prescribed dimensions $k_1$ and $k_2$ and length $n$. While the star product is a fundamental operation in coding theory with applications in quantum error correction, private information retrieval (PIR), and secure distributed matrix multiplication (SDMM), the dimension of the star product of two random codes is not trivial to determine. Previous work, such as [19], estimated this dimension by analyzing the linear independence of rank-1 matrices, establishing that the expected dimension equals $\min\{n, k_1k_2\}$ with high probability under restricted parameter regimes. This paper aims to provide a more general and explicit analysis of the expected dimension and its variance, extending beyond those restricted regimes.

Methodology
The authors establish a correspondence between the star product of two codes and the evaluation of bilinear forms. Specifically, if $C_1$ and $C_2$ have generator matrices $G_1$ and $G_2$, the star product $C_1 \star C_2$ is identified as the image of a linear map $\psi_{G_1, G_2}$ acting on the space of bilinear forms $B = \text{Bil}(\mathbb{F}_q^{k_1}, \mathbb{F}_q^{k_2})$. The dimension of the star product is given by $k_1k_2 - \dim(\ker \psi_{G_1, G_2})$.

To analyze the expected dimension, the authors focus on computing the expected size of the kernel, $\mathbb{E}[|\ker \psi_{C_1, C_2}|]$. They utilize a probabilistic model where codes are generated by choosing the last $n-k$ columns of a systematic generator matrix uniformly at random. The analysis involves:

1. Enumerative Combinatorics: Counting the number of bilinear forms (represented as matrices) of a specific rank $r$ that vanish on the columns of the generator matrices. This requires counting matrices with zero diagonals and specific zero patterns.
2. Explicit Formulas: Deriving an explicit formula for the expected kernel size using $q$-binomial coefficients and inclusion-exclusion principles (Lemma 3.5 and Theorem 3.9).
3. Asymptotic Analysis: Investigating the behavior of these formulas as the field size $q \to \infty$ and as the code dimensions $k_1, k_2 \to \infty$ under specific growth conditions.
4. Variance Analysis: Using the derived bounds on the expected kernel size to upper bound the variance of the star product dimension.

Key Contributions and Results

1. Explicit Lower Bound: The paper provides an explicit formula for the expected size of the kernel of the evaluation map, which yields an explicit lower bound on the expected dimension of the star product for all parameter choices (Corollary 3.11). This approach differs from previous rank-1 matrix analyses by offering a direct combinatorial count of the kernel.

2. Asymptotics in Field Size ($q \to \infty$):

   • The authors prove that as the field size $q$ tends to infinity, the expected dimension of the star product asymptotically reaches its maximum possible value, $\min\{n, k_1k_2\}$, regardless of the relationship between $k_1$ and $k_2$ (Corollary 4.2).
   • Specifically, if $k_1k_2 < n$, the expected kernel size approaches 1; if $k_1k_2 = n$, it approaches 2; and if $k_1k_2 > n$, it diverges.
   • The variance of the dimension is shown to decay asymptotically to 0, with rates depending on whether $k_1k_2 < n$ or $k_1k_2 \ge n$ (Proposition 4.3).

3. Asymptotics in Code Dimensions ($k_1, k_2 \to \infty$):

   • Under "admissible" growth conditions (where $k_1$ and $k_2$ grow strictly monotonically and $k_1k_2$ does not grow too rapidly relative to $q^{k_1}$), the paper proves that the expected kernel size stabilizes (Theorem 5.7).
   • Consequently, the expected dimension of the star product attains $\min\{n, k_1k_2\}$ with high probability as dimensions increase (Corollary 5.12).
   • The variance is shown to vanish asymptotically under these conditions, decaying at least exponentially if $n < k_1k_2$ or if the gap $n - k_1k_2$ grows linearly (Proposition 5.14).

4. Comparison with Prior Work: The results are compared with the rank-1 matrix approach of [19]. The authors note that their results cover a broader range of parameter regimes, particularly for larger field sizes $q \ge 3$, where their bounds on the growth of dimensions are strictly stronger than those in [19] (Remark 5.13).

Significance and Implications
The paper claims that these results have direct implications for several areas:

• Private Information Retrieval (PIR): In PIR schemes based on star products, the retrieval rate is bounded by the dimension of the star product. The results suggest that while random codes asymptotically yield maximal star product dimensions (leading to lower retrieval rates compared to structured codes like GRS), there remains a non-negligible probability over small fields (e.g., $\mathbb{F}_2$) of sampling code pairs with sub-maximal dimensions. This implies that experimental searches for favorable random code pairs for PIR are viable, especially in error-free settings.
• Secure Distributed Matrix Multiplication (SDMM): Similar to PIR, the recovery threshold and straggler tolerance in SDMM depend on the star product dimension. The findings indicate that random constructions typically do not achieve asymptotically low recovery thresholds, but practical instances with favorable parameters may still be found over small fields.
• Quantum Error Correction: The paper discusses binary CSS-T codes, which require $C_2 \subseteq C_1 \cap (C_1 \star C_1)^\perp$. The results imply that for uniformly random codes of sufficiently large dimension, the star product $C_1 \star C_1$ is likely to be large, forcing the orthogonal complement to be small. This suggests that constructing high-distance CSS-T codes using random $C_1$ is unlikely, as the resulting quantum code would have a weak lower bound on minimum distance.
• Cryptanalysis: The star product dimension is used as a distinguisher in code-based cryptography (e.g., against Goppa codes). The paper notes that while their results confirm that random codes generally have maximal star product dimensions (making them distinguishable from structured codes like Goppa codes which have smaller squares), the specific parameter ranges analyzed do not currently threaten the security of standard McEliece systems. However, the methodology opens the door to analyzing star products of different code pairs to explore new parameter ranges.

Conclusion
The paper concludes that the expected dimension of the star product of two uniformly random codes asymptotically reaches its theoretical maximum as the field size increases, and under specific growth conditions, as the code dimensions increase. The variance vanishes in these regimes, indicating a concentration of measure. The authors identify the derivation of tight lower bounds for the variance and the analysis of non-asymptotic cases as open problems for future work.