Over the past few decades, we have seen a proliferation of advanced cryptographic primitives with lossy or homomorphic properties built from various assumptions such as Quadratic Residuosity, Decisional Diffie–Hellman, and Learning with Errors. These primitives imply hard problems in the complexity class \(\mathcal {SZK}\) (statistical zero-knowledge); as a consequence, they can only be based on assumptions that are broken in \(\mathcal {BPP}^{\mathcal {SZK}}\) . This poses a barrier for building advanced cryptography from code-based assumptions such as Learning Parity with Noise (LPN), as LPN is only known to be in \(\mathcal {BPP}^{\mathcal {SZK}}\) under an extremely low noise rate \(\frac{\log ^2 n}{n}\) , for which it is broken in quasi-polynomial time. In this work, we propose a new code-based assumption: Dense-Sparse LPN, that falls in the complexity class \(\mathcal {BPP}^{\mathcal {SZK}}\) and we conjecture to be secure against subexponential time adversaries. Our assumption is a variant of LPN that is inspired by McEliece’s cryptosystem and the random \(k\text{- }\) XOR problem in average-case complexity. Roughly, the assumption states that \(\begin{aligned}({\textbf{T}}\, {\textbf{M}}, {\textbf{s}} \,{\textbf{T}}\, {\textbf{M}} + {\textbf{e}}) \quad \text {is indistinguishable from}\quad ({\textbf{T}} \,{\textbf{M}}, {\textbf{u}}),\end{aligned}\) for a random (dense) matrix \({\textbf{T}}\) , random sparse matrix \({\textbf{M}}\) , and sparse noise vector \({\textbf{e}}\) drawn from the Bernoulli distribution with inverse polynomial noise rate. We leverage our assumption to build lossy trapdoor functions (Peikert-Waters STOC 08). This gives the first post-quantum alternative to the lattice-based construction in the original paper. Lossy trapdoor functions, being a fundamental cryptographic tool, are known to enable a broad spectrum of both lossy and non-lossy cryptographic primitives; our construction thus implies these primitives in a generic manner. In particular, we achieve collision-resistant hash functions with plausible subexponential security, improving over a prior construction from LPN with noise rate \(\frac{\log ^2 n}{n}\) that is only quasi-polynomially secure.
