Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a public key encryption (PKE) scheme based on the conjectured hardness of two constraint satisfaction problems (CSPs) with near-total corruption: a large alphabet random predicate CSP (LARP-CSP) and a $k$XOR problem. The security of the scheme relies on a novel method for planting cryptographic trapdoors using the label extended factor graph of a CSP. The authors provide lower bounds against various attacks on LARP-CSPs and construct an error-correcting code with expanding, low-density generator matrix that enables efficient decoding from a $1 - o(1)$ fraction of corruptions.
Public key encryption can be plausibly secured against quasi-exponential attacks by exploiting the surprising hardness of constraint satisfaction problems where almost all constraints are corrupted.
We give a public key encryption scheme with plausible quasi-exponential security based on the conjectured intractability of two constraint satisfaction problems (CSPs), both of which are instantiated with a corruption rate of $1 - o(1)$. First, we conjecture the hardness of a new large alphabet random predicate CSP (LARP-CSP) defined over an arbitrary but strongly expanding factor graph, where the vast majority of predicate outputs are replaced with random outputs. Second, we conjecture the hardness of the standard $k$XOR problem defined over a random factor graph, again where the vast majority of parity computations are replaced with random bits. In support of our hardness conjecture for LARP-CSPs, we give a variety of lower bounds, ruling out many natural attacks including all known attacks that exploit non-random factor graphs. Our public key encryption scheme is the first to leverage high corruption CSPs while simultaneously achieving a plausible security level far above quasi-polynomial. At the heart of our work is a new method for planting cryptographic trapdoors based on the label extended factor graph for a CSP. Along the way to achieving our result, we give the first uniform construction of an error-correcting code that has an expanding, low density generator matrix while simultaneously allowing for efficient decoding from a $1 - o(1)$ fraction of corruptions.