Paper 2024/175
Lossy Cryptography from CodeBased Assumptions
Abstract
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 DiffieHellman, and Learning with Errors. These primitives imply hard problems in the complexity class $\mathcal{SZK}$ (statistical zeroknowledge); 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 primitives from codebased 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 quasipolynomial time. In this work, we propose a new codebased assumption: DenseSparse 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\mbox{}$XOR in averagecase complexity. Roughly, the assumption states that \[(\mathbf{T}\, \mathbf{M}, \mathbf{s} \,\mathbf{T}\, \mathbf{M} + \mathbf{e}) \quad \text{is indistinguishable from}\quad (\mathbf{T} \,\mathbf{M}, \mathbf{u}),\] for a random (dense) matrix $\mathbf{T}$, random sparse matrix $\mathbf{M}$, and sparse noise vector $\mathbf{e}$ drawn from the Bernoulli distribution with inverse polynomial noise probability. We leverage our assumption to build lossy trapdoor functions (PeikertWaters STOC 08). This gives the first postquantum alternative to the latticebased construction in the original paper. Lossy trapdoor functions, being a fundamental cryptographic tool, are known to enable a broad spectrum of both lossy and nonlossy cryptographic primitives; our construction thus implies these primitives in a generic manner. In particular, we achieve collisionresistant hash functions with plausible subexponential security, improving over a prior construction from LPN with noise rate $\frac{\log^2 n}{n}$ that is only quasipolynomially secure.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint.
 Keywords
 codebased cryptographylossy trapdoor functionsLearning Parity with NoiseLPNSZK
 Contact author(s)

qvd @ andrew cmu edu
aayushja @ andrew cmu edu  History
 20240206: approved
 20240206: received
 See all versions
 Short URL
 https://ia.cr/2024/175
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/175, author = {Quang Dao and Aayush Jain}, title = {Lossy Cryptography from CodeBased Assumptions}, howpublished = {Cryptology ePrint Archive, Paper 2024/175}, year = {2024}, note = {\url{https://eprint.iacr.org/2024/175}}, url = {https://eprint.iacr.org/2024/175} }