Public Key Encryption from High-Corruption Constraint Satisfaction Problems

Titel: Public Key Encryption from High-Corruption Constraint Satisfaction Problems

Auteurs: Isaac M. Hair (UCSB, UCLA) en Amit Sahai (UCLA)
Datum: 14 april 2026 (voorgesteld)

1. Probleemstelling en Context

Het doel van dit onderzoek is het ontwikkelen van een Public Key Encryption (PKE) schema dat gebaseerd is op nieuwe, minder onderzochte aannames van computationele hardheid, specifiek om de afhankelijkheid van traditionele problemen (zoals factorisatie of discrete logaritmen, die kwetsbaar zijn voor quantumcomputers) te verminderen.

De auteurs richten zich op Constraint Satisfaction Problems (CSP's) met een extreem hoge corruptiegraad. In tegenstelling tot traditionele cryptografische CSP's waarbij slechts een klein deel van de constraints corrupt is, werken deze auteurs met een corruptiegraad van $1 - o(1)$. Dit betekent dat in een scenario met een "geplante" oplossing (een verborgen secret), bijna elke constraint onafhankelijk wordt vervangen door een willekeurige, corrupte waarde.

De uitdaging ligt in het vinden van een methode om een "trapdoor" (een geheime sleutel voor decryptie) te planten in een dergelijk chaotisch systeem, terwijl het voor een aanvaller onmogelijk blijft om de oplossing te vinden zonder deze trapdoor.

2. Kernmethodologie en Aannames

De auteurs introduceren twee nieuwe hardheidsvermoens (conjectures) die de basis vormen voor hun PKE-schema:

A. High Corruption LARP-CSP Conjecture

Dit is een nieuw type CSP genaamd Large Alphabet Random Predicate CSP (LARP-CSP).

• Structuur: Gegeven een sterk expanderende factorgraf (een matrix $H$) en een set van $m$ willekeurige functies $f_i$ die variabelen uit een groot alfabet $\Sigma$ afbeelden naar een output-alfabet $\Gamma$.
• Corruptie: Met een zeer hoge waarschijnlijkheid ($1 - o(1)$) wordt de output van de functie vervangen door een willekeurige waarde in plaats van de echte berekening.
• Hardheid: Het vermoeden stelt dat het onmogelijk is om te onderscheiden tussen een set van volledig willekeurige constraints en een set waar een verborgen toewijzing $s$ aan de basis ligt, zelfs als de meeste constraints corrupt zijn. De enorme entropie die wordt bijgedragen door de willekeurige functies en het grote alfabet maakt dit probleem weerstandbiedend tegen bekende aanvallen.

B. High Corruption Random kXOR Conjecture

Dit is een variant van het klassieke $k$XOR-probleem (pariteitscontroles).

• Structuur: Een willekeurige factorgraf $H$ met $k$-variabelen per constraint.
• Corruptie: Net als bij LARP-CSP is de corruptiegraad $1 - o(1)$.
• Verschil: Waar traditionele cryptografie vaak werkt met een lage corruptiegraad (bijv. $1/poly(n)$), werkt dit schema met een corruptiegraad die bijna 1 is.

C. Nieuwe Techniek: Trapdoors via Label Extended Factor Graphs

Het meest innovatieve aspect van dit werk is de methode om de trapdoor te planten.

• In plaats van de trapdoor direct in de encryptie te verstoppen, gebruiken de auteurs de label extended factor graph van de LARP-CSP.
• Tijdens het genereren van de publieke sleutel worden alle lokale pre-images (oplossingen) van de constraints in de LARP-CSP verzameld om een nieuwe matrix $H$ te vormen.
• De geheime sleutel is een mapping die aangeeft welke rijen in deze nieuwe matrix $H$ corresponderen met de oorspronkelijke, niet-gecorrumpeerde structuur van een onderliggende lineaire code. Dit maakt decryptie mogelijk zonder dat de aanvaller de volledige structuur kan reconstrueren.

3. Belangrijkste Bijdragen en Resultaten

1. Quasi-exponentiële Beveiliging

De meeste bestaande PKE-schema's gebaseerd op CSP's bereiken slechts quasi-polynomiale beveiliging ($\lambda^{O(\log \lambda)}$), vaak vanwege een "brute-force" barrière bij het decoderen.

• Het schema van Hair en Sahai bereikt een plausibele quasi-exponentiële beveiliging ($\exp(2^{\log^{\Omega(1)} \lambda})$).
• Dit is een aanzienlijke verbetering en komt dicht in de buurt van sub-exponentiële beveiliging, wat het een veel robuustere kandidaat maakt voor post-quantum cryptografie.

2. Constructie van een Decodable Expanding Code

Een cruciale tussenstap was de constructie van een uniforme foutcorrigerende code met de volgende eigenschappen:

• Een generatormatrix die expanderend en laag-dichtheid (LDGM) is.
• Het vermogen om efficiënt te decoderen (onderscheiden) van een vector met een corruptiegraad van $1 - o(1)$ en een verliesgraad (erasure) van $1 - o(1)$.
• Dit is de eerste expliciete constructie die dit bereikt; eerdere werken (zoals [OST18]) bewezen alleen het bestaan ervan, maar boden geen constructie. De auteurs gebruiken hiervoor een subcode van Reed-Muller codes en een specifieke probabilistische algoritme voor het genereren van de matrix.

3. Onderbouwing van Hardheid (Lower Bounds)

Om de geloofwaardigheid van hun aannames te versterken, leveren de auteurs een reeks ondergrenzen (lower bounds) die veel natuurlijke aanvallen uitsluiten:

• Low Complexity Embedding Attacks: Ze tonen aan dat de entropie van de willekeurige functies in LARP-CSP voldoende is om aanvallen te weerstaan die gebaseerd zijn op het vinden van lage-complexiteit circuits (zoals AC0[+]), zelfs als de aanvaller de factorgraf mag kiezen.
• Low Degree Polynomials: Ze bewijzen dat algoritmen die gebaseerd zijn op polynomen van een lage graad (tot $n^{0.99}$) het probleem niet kunnen oplossen. Dit dekt een breed scala aan combinatorische algoritmen.
• Polynomial Calculus Refutations: Ze tonen aan dat het onmogelijk is om een korte bewijsvoering (refutatie) te vinden in het polynomial calculus proof systeem, zelfs als de aanvaller de beste embedding van het alfabet naar een veld mag kiezen.

4. Significatie en Impact

• Nieuwe Basis voor Cryptografie: Het werk biedt een alternatieve route voor PKE die niet afhankelijk is van getaltheorie of lattices, maar juist van de gemiddelde-case hardheid van CSP's. Dit verrijkt het "win-win" perspectief: of we krijgen een veilige cryptosysteem, of we doorbreken een fundamenteel wiskundig vermoeden over de hardheid van CSP's.
• Post-Quantum Veiligheid: Omdat de onderliggende problemen (LARP-CSP en kXOR) niet bekend zijn om kwetsbaar te zijn voor quantumalgoritmen (zoals Shor's algoritme), biedt dit een sterke kandidaat voor post-quantum cryptografie.
• Theoretische Doorbraak: De introductie van het gebruik van label extended factor graphs voor het planten van trapdoors opent een nieuw onderzoeksveld binnen de complexe theorie en cryptografie.
• Coding Theory: De constructie van de decodable expanding code is op zich al een significante bijdrage aan de coderingstheorie, met toepassingen die verder gaan dan alleen cryptografie.

Conclusie

Hair en Sahai presenteren een baanbrekend PKE-schema dat werkt onder extreem hoge corruptiecondities. Door een slimme combinatie van een nieuwe hardheidsvermoen (LARP-CSP), een innovatieve methode voor het planten van trapdoors via expanderende grafen, en een nieuwe constructie van foutcorrigerende codes, bereiken ze een beveiligingsniveau dat aanzienlijk hoger is dan eerdere pogingen op dit gebied. Het werk levert zowel een praktisch cryptografisch protocol als een diepgaande theoretische analyse van de hardheid van CSP's.