💻 computer science

Public Key Encryption from High-Corruption Constraint Satisfaction Problems

This paper proposes a public key encryption scheme with plausible quasi-exponential security based on the conjectured hardness of constraint satisfaction problems with high corruption rates, utilizing a novel trapdoor planting method and a new error-correcting code capable of decoding from nearly all corruptions.

Original authors: Isaac M Hair, Amit Sahai

Published 2026-04-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Isaac M Hair, Amit Sahai

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Locking the Door with a Broken Key

Imagine you want to send a secret message to a friend. In the digital world, we use Public Key Encryption to do this. It's like having a special mailbox: anyone can drop a letter in (using the public key), but only you have the unique key to open it and read the letter (the private key).

For decades, we've built these mailboxes using math problems that are hard to solve, like factoring huge numbers or finding patterns in grids. But there's a worry: Quantum computers might soon be able to crack these locks easily.

This paper proposes a brand new way to build these mailboxes. Instead of using number puzzles, the authors use Constraint Satisfaction Problems (CSPs).

What is a CSP?
Think of a CSP as a giant, messy logic puzzle.

You have a bunch of variables (like light switches).
You have a bunch of rules (like "Switch A and Switch B must be different").
The goal is to find a setting for all the switches that satisfies all the rules.

Usually, these puzzles are easy if the rules are clear. But this paper introduces a twist: The "High-Corruption" Twist.

The Core Idea: The "Broken" Puzzle

Imagine you are given a logic puzzle, but someone has taken a red marker and scribbled over 99% of the rules.

The original rule was: "Switch A must be ON."
The scribbled version says: "Switch A must be OFF" (or maybe just a random nonsense symbol).

The puzzle is now a mess. Most of the rules are lies. The only thing that remains true is a tiny, hidden pattern buried under a mountain of noise.

The authors' big claim is: It is computationally impossible to find the hidden pattern in this mountain of noise. Even if you have a supercomputer, the noise is so overwhelming that you can't tell if there's a secret solution or if the whole thing is just random garbage.

They rely on two specific types of these "broken" puzzles:

The LARP-CSP: A puzzle with a very complex, expanding structure where the rules themselves are random and huge.
The kXOR: A classic math puzzle (like a game of "Odd or Even") where almost every answer has been flipped to a random value.

The Magic Trick: Planting a Trapdoor

If the puzzle is so broken that no one can solve it, how do you (the sender) send a message that only you can read? You need a Trapdoor.

In cryptography, a trapdoor is a secret piece of information that makes a hard problem easy for you, but impossible for everyone else.

The Analogy: The "Label Extended" Map
Imagine you have a giant, chaotic city map (the public key) where almost every street sign is wrong or missing.

The Public: Sees the map and thinks, "I can't navigate this. It's too messy."
The Secret Key: You have a special "decoder ring" (the trapdoor). This ring doesn't just point to the right streets; it tells you exactly which of the wrong signs are actually the real ones, and which ones are just noise.

The authors invented a new way to plant this trapdoor. They use a technique involving a "Label Extended Factor Graph."

Think of the puzzle as a web of connections.
The authors create a "shadow map" of this web.
They hide the real structure of the web inside this shadow map.
To the public, the shadow map looks like random static.
To you, with the secret key, the shadow map reveals the hidden "skeleton" of the original puzzle, allowing you to ignore the noise and solve the problem instantly.

The New Super-Code

To make this work, the authors also had to invent a new type of Error-Correcting Code.

Normal Codes: Like a text message that can handle a few typos.
This New Code: Like a text message that can handle it if 99% of the letters are replaced with random gibberish, and you can still read the original message perfectly.

They built this code using a special type of mathematical structure called a Reed-Muller code, but they arranged it in a way that creates a "strongly expanding" network. This ensures that even if almost everything is destroyed, the remaining pieces are still connected enough to reconstruct the whole picture.

Why This Matters: The "Win-Win"

The authors argue that this is a "Win-Win" situation for science:

If it works: We get a super-secure encryption method that quantum computers probably can't break.
If it fails: If someone figures out how to solve these "broken" puzzles, they will have made a massive breakthrough in mathematics and computer science, teaching us something profound about how logic and randomness interact.

Summary in a Nutshell

The Problem: Current encryption might be broken by future quantum computers.
The Solution: Build encryption based on logic puzzles that are 99% corrupted with random noise.
The Catch: No one can solve these puzzles unless they have a secret "decoder ring" (the trapdoor) that knows exactly where the tiny bit of truth is hidden.
The Result: A new, incredibly secure way to send messages that relies on the sheer impossibility of finding a needle in a haystack made of other needles.

The paper essentially says: "We found a way to hide a secret so deep inside a mountain of noise that even the best algorithms can't find it, but we built a secret map that lets us walk right to it."

1. Problem Statement and Motivation

The Core Challenge:
Public Key Encryption (PKE) is a fundamental cryptographic primitive. Currently, secure PKE schemes rely on a very narrow set of computational hardness assumptions, primarily number-theoretic problems (e.g., Integer Factorization, Discrete Logarithm) and lattice/coding-theoretic problems (e.g., LWE, McEliece). Number-theoretic problems are vulnerable to quantum computers (Shor's algorithm), and there is a risk that mathematical breakthroughs could compromise lattice-based schemes. The authors aim to construct PKE from Constraint Satisfaction Problems (CSPs), specifically those with high corruption rates ( $1 - o(1)$ ), to diversify the foundations of cryptography.

The Specific Problem:
The paper addresses the construction of PKE from CSPs where the constraints are defined over a factor graph, but the vast majority of constraint outputs are replaced with random noise (corruption).

Standard CSPs: Usually involve finding a hidden assignment that satisfies a large fraction of constraints.
High-Corruption CSPs: The "planted" solution satisfies the constraints only with probability $o(1)$ , while the remaining $1-o(1)$ fraction of constraints are replaced with random outputs.
The Barrier: Previous attempts to build PKE from high-corruption CSPs (e.g., Applebaum, Barak, Wigderson) were limited to quasi-polynomial security ( $\lambda^{O(\log \lambda)}$ ) because decryption required a brute-force search over a logarithmic-sized hidden component.

Goal:
Construct a PKE scheme with quasi-exponential security ( $\exp(2^{\log^{\Omega(1)} \lambda})$ ) based on the intractability of two specific high-corruption CSPs, without resorting to brute-force decryption.

2. Methodology and Key Techniques

The authors introduce a novel framework that combines two distinct hardness conjectures and a new method for "planting" cryptographic trapdoors.

A. The Two Hardness Conjectures

The security of the scheme relies on the simultaneous intractability of two problems, both instantiated with a corruption rate of $1 - o(1)$ :

High-Corruption LARP-CSP (Large Alphabet Random Predicate CSP):
- Setup: A strongly expanding factor graph $H$ (arbitrary but expanding). Variables take values from a large alphabet $\Sigma$ . Constraints are defined by random functions $f_i: \Sigma^k \to \Gamma$ .
- Corruption: Each constraint output $b_i$ is replaced with a random element of $\Gamma$ with probability $1 - o(1)$ .
- Hardness Source: The massive entropy contributed by the random predicates and the large alphabet size makes the problem indistinguishable from random noise, even for powerful algorithms. The factor graph is not random, but the predicates are.
High-Corruption Random kXOR:
- Setup: A random factor graph $H$ . Variables are binary ( $\mathbb{F}_2$ ). Constraints are parity checks (XOR) of $k$ variables.
- Corruption: Each parity output is replaced with a random bit with probability $1 - o(1)$ .
- Hardness Source: This is a variant of the Learning Parity with Noise (LPN) problem but with a random factor graph and extremely high noise. It is known to fool local algorithms, linear tests, and low-degree polynomial algorithms.

B. The "Label Extended Factor Graph" Trapdoor

The core innovation is a new method for planting a trapdoor that allows efficient decryption without brute force.

Concept: Instead of hiding a secret key directly, the scheme uses the label extended factor graph of the LARP-CSP.
Mechanism:
1. Key Generation: The secret key includes a mapping $\zeta$ that identifies a specific subgraph within the public key matrix $H$ . This subgraph corresponds to the "uncorrupted" constraints of a hidden linear code (specifically, a subcode of a Reed-Muller code).
2. Public Key: The public key $H$ is constructed by listing all local pre-images of the LARP-CSP constraints. Crucially, $H$ looks like a random matrix to an adversary because the LARP-CSP conjecture implies that the planted structure is indistinguishable from random noise.
3. Encryption: Encrypting a bit $0$ involves generating a vector that is a noisy codeword of the hidden linear code (using the random kXOR structure). Encrypting $1$ involves generating a purely random vector.
4. Decryption: The secret key $\zeta$ allows the decryptor to extract the specific rows of the ciphertext corresponding to the hidden linear code. This reduces the decryption problem to distinguishing a noisy codeword from random noise, which is solvable efficiently using a specific error-correcting code decoder.

C. New Error-Correcting Code Construction

To make the above work, the authors construct the first uniform, explicit error-correcting code with:

An expanding, low-density generator matrix (LDGM).
The ability to efficiently decode from a $1 - o(1)$ fraction of corruptions (and erasures).
Construction: They utilize Reed-Muller codes of sufficiently low rate. They prove that a randomized algorithm can sample an expanding generator matrix that generates a subcode of a Reed-Muller code, and they leverage existing decoding results (Saptharishi, Shpilka, Volk) to show that these codes can be decoded from high noise.

3. Key Contributions

First Quasi-Exponential PKE from High-Corruption CSPs:
The paper presents the first PKE scheme based on high-corruption CSPs that achieves quasi-exponential security ( $\exp(2^{\log^{\Omega(1)} \lambda})$ ), significantly surpassing the previous quasi-polynomial barrier. This is achieved by avoiding brute-force decryption.
New Hardness Conjectures (LARP-CSP):
The authors propose the High-Corruption LARP-CSP conjecture. Unlike Goldreich's PRG (which uses a fixed predicate), this uses random predicates over a large alphabet. The authors argue this provides sufficient entropy to resist known attacks on structured factor graphs.
Comprehensive Lower Bounds:
To support the LARP-CSP conjecture, the paper provides rigorous lower bounds ruling out several classes of attacks:
- Low Complexity Embedding Attacks: Generalizing the Oliveira-Santhanam-Tell attacks on Goldreich's PRG. The authors show that the entropy of random predicates makes these attacks ineffective.
- Low Degree Polynomial Algorithms: Proving that degree- $n^{0.99}$ polynomials cannot distinguish the planted distribution from random.
- Polynomial Calculus Refutations: Showing that refutations require size $\exp(n^{0.99})$ .
Explicit Expanding Code Construction:
The paper provides the first explicit, uniform construction of an error-correcting code with an expanding generator matrix that is decodable from $1 - o(1)$ corruption. Previous work (Oliveira et al.) only proved the existence of such graphs non-constructively.

4. Results

Theorem 1.3: Assuming the High-Corruption LARP-CSP and High-Corruption kXOR conjectures hold, there exists a semantically secure public key encryption scheme.
Security Level: The scheme achieves security of $\exp(2^{\log^{\Omega(1)} \lambda})$ , which is significantly higher than quasi-polynomial and approaches sub-exponential security.
Efficiency: The key generation, encryption, and decryption algorithms run in polynomial time relative to the security parameter (specifically, the running time is dominated by writing the output matrix).
Correctness: The scheme has high correctness probability ( $> 1 - o(1)$ ) due to the properties of the Reed-Muller subcode and the decoding algorithm.

5. Significance and Impact

Diversifying Cryptographic Foundations: By basing PKE on CSPs rather than number theory or lattices, this work provides a "win-win" scenario. If the scheme is broken, it implies a breakthrough in understanding average-case complexity of CSPs (a major theoretical goal). If it remains secure, it offers a post-quantum alternative to current standards.
Overcoming the Brute-Force Barrier: The work demonstrates that high-corruption CSPs can support strong cryptography without the decryption bottleneck that plagued previous attempts. This opens a new avenue for designing cryptographic primitives based on average-case hardness.
Theoretical Insights: The paper deepens the understanding of the relationship between expander graphs, random predicates, and cryptographic trapdoors. The "label extended factor graph" technique offers a new tool for embedding secrets in seemingly random structures.
Coding Theory Advances: The construction of explicit expanding codes decodable from high corruption rates is a significant contribution to coding theory, with potential applications beyond cryptography (e.g., in communication over noisy channels).

In summary, Hair and Sahai successfully bridge the gap between average-case complexity theory and practical cryptography, proposing a robust, high-security encryption scheme based on the intractability of highly corrupted constraint satisfaction problems.