Sparse matrices for LPN (proposed by Sunghyeon)

We are looking for an infinite family of (distributions on) matrices in $\mathbb{F}_2^{n \times m}$, parametrized by their dimensions $n$ and $m \approx n^e$, having the following properties. (Let $\delta$ be a fixed constant between 0 and 1):

If $M$ is a random $n \times m$ matrix sampled from the distribution, then:

• Each column of $M$ has at most $k = 6$ nonzero entries.
• With probability at least $1 - \nu(n)$, every nonzero vector $v$ such that $Mv = 0$ has at least $n^{\delta}$ nonzero entries. Here $\nu(n)$ is a negligible function of $n$; that is, $\nu(n) < O(n^{-i})$ for any positive integer $i$.

Parameters

Your solution is better if $m$ is larger: we want $m \approx n^c$ for some $c > 1$, the bigger the better.

Your solution is better if $k$ is smaller. $6$ is a fine value.

Your solution is better if $\delta$ is larger.

Remark

For one construction, see Theorem 7.18 $$[AK19](https://eccc.weizmann.ac.il/report/2019/011/)$$ . Can you do better?

Motivation

Learning parity with noise (LPN) is an encryption scheme: a vector $v$ over $\mathbb{F}_2$ is encrypted as $(A, sA + v + e)$, where $s$ is a secret key, and $e$ is a randomly chosen vector with some fraction $\epsilon \ll 1$ of its entries equal to 1. (For this to be a sensible encryption scheme, you can suppose for instance that $v$ is known to be either $(0, 0, ..., 0)$ or $(1, 1, ..., 1)$.)

For certain applications, it is useful for $A$ to have a special structure: $A = TM$, where $T$ is a random matrix (maybe square), and $M$ is drawn from the distribution described above.