CryptoDB
Lossy Cryptography from CodeBased Assumptions
Authors: 


Download: 

Presentation:  Slides 
Conference:  CRYPTO 2024 
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 cryptography from codebased 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 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. 
BibTeX
@inproceedings{crypto202434277, title={Lossy Cryptography from CodeBased Assumptions}, publisher={SpringerVerlag}, doi={10.1007/9783031683824_2}, author={Quang Dao and Aayush Jain}, year=2024 }