Learning subspace with noise

For a uniformly random rank-$k$ secret matrix $\mathbf{C}\in {\mathbb{F}}^{k\times n}$, the $(k,n,\mu )$-LSN assumption states that samples ${\mathbf{a}}_i^T\mathbf{C}+{\mathbf{e}}_i$ — where each ${\mathbf{e}}_i$ is uniform in ${\mathbb{F}}^n$ with probability $\mu$ and zero otherwise — are computationally indistinguishable from uniform.

TODO: syntax and security definition.

Participates in

Builds on Learning subspace with noise

• LSN ⇒ LPN
• LSN ⇒ Secret-Key PIR (SK-PIR)