Lossy Cryptography from Code-Based Assumptions
<|reference_start|>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 $SZK$ (statistical zero-knowledge); as a consequence, they can only be based on assumptions that are broken in $BPP^{SZK}$. This poses a barrier for building advanced primitives from code-based assumptions, as the only known such assumption is Learning Parity with Noise (LPN) with an extremely low noise rate $\frac{\log^2 n}{n}$, which 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 $BPP^{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\mbox{-}$XOR in average-case complexity.   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.<|reference_end|>
@article{dao2024lossy,
    title={Lossy Cryptography from Code-Based Assumptions},
    author={Quang Dao, Aayush Jain},
    journal={arXiv preprint arXiv:2402.03633},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.03633},
    primaryClass={cs.CR cs.CC cs.IT math.IT}
}