Lossy Cryptography from Code-Based Assumptions

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 is conjectured to be secure against subexponential time adversaries. Our assumption is a variant of LPN that is inspired by McEliece’s cryptosystem and random \(k\text{- }\) XOR 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 probability. 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.