Hardness and Algorithms for Batch LPN under Dependent Noise

본문 미리보기

We study the Batch Learning Parity with Noise (LPN) variant, where the oracle returns $k$ samples in a batch and draws the noise vector from a joint noise distribution $\mathcal{D}$ over $\mathbb{F}_2^k$ instead of from an i.i.d. product distribution. This model captures a broad range of correlated or structured noise patterns studied in cryptography and learning theory. Consequently, understanding which dependent-noise distributions preserve the hardness of LPN has become an important question.