Lattice maths.pdf

# Inleiding tot rooster-gebaseerde cryptografie en historische context Dit onderwerp duikt in de oorsprong en de historische ontwikkeling van cryptografische systemen die gebaseerd zijn op roosters, en belicht belangrijke mijlpalen en sleutelfiguren die deze evolutie hebben gevormd [1](#page=1) [2](#page=2). ### 1.1 De oorsprong van rooster-gebaseerde cryptografie De basis voor rooster-gebaseerde cryptografie werd gelegd door de introductie van cryptografische constructies waarvan de veiligheid kon worden teruggebracht tot de moeilijkheid van bekende roosterproblemen [2](#page=2). #### 1.1.1 Belangrijke mijlpalen en sleutelfiguren * In 1996 introduceerde Miklós Ajtai de eerste rooster-gebaseerde cryptografische constructie [2](#page=2). * Cynthia Dwork toonde aan dat het 'short integer solutions' (SIS) probleem, een gemiddeld-geval roosterprobleem, minstens zo moeilijk is als een ergste-geval roosterprobleem. Ze gebruikte dit om een cryptografische hashfunctie te construeren waarvan de veiligheid gelijkstond aan de computationele moeilijkheid van SIS [2](#page=2). * In 1998 introduceerden Jeffrey Hoffstein, Jill Pipher en Joseph H. Silverman een rooster-gebaseerd publieke-sleutel encryptieschema, bekend als NTRU [2](#page=2). * Oded Regev introduceerde in 2005 het eerste publieke-sleutel encryptieschema gebaseerd op roosters, waarvan de veiligheid bewezen kon worden onder ergste-geval hardheidsaannames, samen met het 'learning with errors' (LWE) probleem. Dit was een significante stap voorwaarts, omdat het een directe koppeling legde tussen de veiligheid van het cryptografische schema en de hardheid van een onderliggend roosterprobleem [2](#page=2). * Vanaf 2005 is er veel vervolgonderzoek gedaan om Regev's veiligheidsbewijs te verbeteren en de efficiëntie van het oorspronkelijke schema te verhogen [2](#page=2). * In 2009 introduceerde Craig Gentry het eerste volledig homomorfe encryptieschema, dat eveneens gebaseerd was op een roosterprobleem. Dit was een baanbrekende ontwikkeling die de mogelijkheid bood om berekeningen uit te voeren op versleutelde data zonder deze eerst te hoeven ontsleutelen [2](#page=2). * Het 'Ring Learning With Errors' (RLWE) probleem, geïntroduceerd door Lyubashevsky, Peikert en Regev in 2010, is een uitbreiding van LWE die leidt tot kleinere sleutelgroottes. Dit was een belangrijke verbetering voor de praktische toepasbaarheid van rooster-gebaseerde cryptografie [2](#page=2). > **Tip:** Het begrijpen van de historische ontwikkeling is cruciaal om de motivatie achter de huidige rooster-gebaseerde cryptografische technieken te doorgronden, met name de nadruk op worst-case hardness aannames en efficiëntieverbeteringen [2](#page=2). --- # Definitie en problemen gerelateerd aan roosters Dit gedeelte introduceert de definitie van roosters via basisvectoren en bespreekt fundamentele problemen zoals het kortste vectorprobleem (SVP) en het dichtstbijzijnde vectorprobleem (CVP). ### 2.1 Wat is een rooster? Een rooster wordt gedefinieerd door een set basisvectoren. In een tweedimensionaal rooster zijn dit twee basisvectoren, maar dit kan worden uitgebreid naar $n$ vectoren voor een $n$-dimensionaal rooster. De aard van deze basisvectoren, of ze nu orthogonaal of "zeer niet-orthogonaal" zijn, heeft invloed op de moeilijkheid van gerelateerde problemen [3](#page=3). Een rooster kan worden beschouwd als een discrete $n$-dimensionale ruimte. Het is "discreet" omdat er altijd een minimale afstand is tussen willekeurig welke twee elementen in het rooster. De elementen van een rooster worden gevormd door alle mogelijke gehele lineaire combinaties van de basisvectoren. Lineaire combinaties van basisvectoren kunnen, onder bepaalde voorwaarden, nieuwe basissen van hetzelfde rooster vormen [3](#page=3). ### 2.2 Fundamentele problemen gerelateerd aan roosters Er zijn fundamentele problemen die geassocieerd worden met roosters, met name in de context van cryptografie: #### 2.2.1 Kortste vectorprobleem (SVP) Het kortste vectorprobleem (SVP) vraagt om het vinden van een niet-nul vector binnen een bepaald rooster, die de minimale lengte heeft ten opzichte van alle andere niet-nul vectoren in dat rooster [3](#page=3). **Definitie:** Gegeven een rooster gedefinieerd door een basis, vind een niet-nul vector in het rooster met minimale lengte [3](#page=3). #### 2.2.2 Dichtstbijzijnde vectorprobleem (CVP) Het dichtstbijzijnde vectorprobleem (CVP) is een generalisatie van het SVP. Hierbij wordt niet alleen het rooster gegeven via een basis, maar ook een doelvector. De taak is om een vector in het rooster te vinden die het dichtst bij deze doelvector ligt [3](#page=3). **Definitie:** Gegeven een rooster gedefinieerd door een basis en een doelvector, vind de vector in het rooster die het dichtst bij de doelvector ligt [3](#page=3). #### 2.2.3 Bounded distance decoding (BDD) Het bounded distance decoding (BDD) probleem is een specifieke variant van CVP. Bij BDD wordt gegarandeerd dat de doelvector zich op een afstand van maximaal $d$ bevindt van het rooster, waarbij $d$ een bekende waarde is [4](#page=4). **Definitie:** Gegeven een rooster gedefinieerd door een basis, een doelvector, en een bekende afstand $d$, vind de vector in het rooster die het dichtst bij de doelvector ligt, met de garantie dat deze afstand maximaal $d$ is [4](#page=4). ### 2.3 Moeilijkheid en relevantie in cryptografie Hoewel deze problemen op het oog eenvoudig lijken met kleine, tweedimensionale voorbeelden en goed-geordende basissen, worden ze extreem moeilijk in hoog-dimensionale ruimtes (honderden tot duizenden dimensies) met niet-orthogonale basissen. Deze moeilijkheid maakt roosterproblemen aantrekkelijk voor cryptografische toepassingen, aangezien ze vermoedelijk quantumresistent zijn. Dit betekent dat de quantum Shor-algoritme, dat andere cryptografische systemen kan breken, niet effectief is tegen roostergebaseerde cryptografie [4](#page=4). > **Tip:** In de context van cryptografie wordt een "goede" (quasi-orthogonale) basis vaak gebruikt voor de private sleutel, terwijl een "slechte" (gerandomiseerde) basis de publieke sleutel vormt [4](#page=4). > > **Tip:** In tegenstelling tot sommige andere cryptografische systemen die afhankelijk zijn van gemiddelde-gevallen complexiteit, vereisen roosterproblemen expliciete generatie van moeilijke probleeminstanties vanwege de sterke invloed van de basiskeuze op de moeilijkheid [4](#page=4). Een bekende methode om roosterproblemen op te lossen is het LLL-algoritme [4](#page=4). --- # Lattice-gebaseerde cryptografische constructies Dit onderwerp verkent specifieke cryptografische constructies die gebaseerd zijn op harde problemen in rooster-gebaseerde cryptografie, met name het Short Integer Solution (SIS) en Learning With Errors (LWE) problemen, en hun equivalentie met roosterproblemen [5](#page=5) [6](#page=6) [7](#page=7). ### 3.1 Short Integer Solution (SIS) probleem Het SIS-probleem is een fundamenteel concept binnen rooster-gebaseerde cryptografie. Het probleem stelt dat men zoekt naar een korte vector $s$, welke een oplossing is voor de lineaire vergelijking $A \cdot s = 0$. Hierbij is $A$ een matrix bestaande uit $n$ $m$-dimensionale vectoren, en $s$ is een $m$-dimensionale vector waarvan de elementen klein zijn (typisch 0, 1, of -1). Hoewel het probleem op het eerste gezicht mogelijk niet direct gerelateerd lijkt aan roosters, is het equivalent aan roosterproblemen [5](#page=5). ### 3.2 Learning With Errors (LWE) probleem Het LWE-probleem is een variant die wordt gebruikt om harde roosterproblemen te vertalen naar cryptosystemen. Het kernidee van LWE betreft het oplossen van lineaire vergelijkingen met ruis of fouten [6](#page=6). #### 3.2.1 Definitie en structuur Gegeven is een $n \times m$-dimensionale matrix $A$ en een geheime vector $x$ (het private key). Een reeks metingen wordt verkregen door $A$ te vermenigvuldigen met $x$ en vervolgens een kleine foutvector $e$ toe te voegen, alles modulo een bepaalde waarde (bijvoorbeeld 13 in het gegeven voorbeeld). Formeel kunnen de metingen worden weergegeven als [6](#page=6): $$ A \cdot x + e \approx y \pmod{q} $$ waar $y$ de gemeten vector is en $q$ de modulus. Het probleem bestaat erin om $x$ en $e$ te reconstrueren uit de gegeven matrix $A$ en de gemeten vector $y$ [6](#page=6). > **Tip:** Het oplossen van deze vergelijkingen zonder de foutvector $e$ is een eenvoudig probleem dat kan worden opgelost met standaard lineaire algebra technieken zoals Gauss-eliminatie. De moeilijkheid van LWE ligt juist in de aanwezigheid van de onbekende fouten [6](#page=6). #### 3.2.2 Relatie tot roosterproblemen Het LWE-probleem is bewezen equivalent te zijn aan bepaalde roosterproblemen, met name Closest Vector Problem (CVP) en in het bijzonder Bounded Distance Decoding (BDD). Deze equivalentie is van cruciaal belang omdat roosterproblemen al lange tijd grondig zijn bestudeerd, wat een solide theoretische basis biedt voor de veiligheid van LWE-gebaseerde cryptografie [6](#page=6). #### 3.2.3 Voorbeeld Stel dat we de volgende vergelijkingen hebben, waarbij de modulus $q=13$ is [6](#page=6): $$ \begin{array}{l} 4x_1 + 1x_2 + 11x_3 + 10x_4 \approx 4 \pmod{13} \\ 5x_1 + 5x_2 + 9x_3 + 5x_4 \approx 7 \pmod{13} \\ 3x_1 + 9x_2 + 0x_3 + 10x_4 \approx 2 \pmod{13} \\ 1x_1 + 3x_2 + 3x_3 + 2x_4 \approx 11 \pmod{13} \\ 12x_1 + 7x_2 + 3x_3 + 4x_4 \approx 5 \pmod{13} \\ 6x_1 + 5x_2 + 11x_3 + 4x_4 \approx 12 \pmod{13} \\ 3x_1 + 3x_2 + 5x_3 + 0x_4 \approx 8 \pmod{13} \end{array} $$ Hierbij is de geheime sleutel bijvoorbeeld $x = (6,9,11,11)$ en de foutvector is onbekend. Om de waarden in de gemeten vector $y$ te berekenen, worden de rijen van de matrix $A$ vermenigvuldigd met de geheime sleutel $x$ en wordt de fout toegevoegd. Bijvoorbeeld, voor het eerste element in de eerste kolom [6](#page=6): $4 \times 6 + 1 \times 9 + 11 \times 11 + 10 \times 11 \pmod{13} = 4$ [7](#page=7). En voor het tweede element in de eerste kolom: $5 \times 6 + 5 \times 9 + 9 \times 11 + 5 \times 11 \pmod{13} = 7$ [7](#page=7). #### 3.2.4 RLWE (Ring Learning With Errors) Hoewel er een formele bewijs is voor de equivalentie tussen LWE en roosterproblemen, geldt dit niet voor Ring LWE (RLWE) met alle roosterproblemen. RLWE is een geoptimaliseerde variant van LWE die gebruikmaakt van ringstructuren om de sleutelgrootte te reduceren. De dimensie $n$ van het probleem kan erg groot zijn, typisch in de orde van 500 tot 1000, wat resulteert in sleutelgroottes van de orde $n^2$ [6](#page=6) [7](#page=7). > **Tip:** De theoretische equivalentie tussen LWE en roosterproblemen is de hoeksteen van de veiligheid van veel moderne cryptografische systemen, omdat de weerstand tegen aanvallen van deze systemen direct kan worden afgeleid uit de moeilijkheid van deze roosterproblemen [6](#page=6). --- ## Veelgemaakte fouten om te vermijden - Bestudeer alle onderwerpen grondig voor examens - Let op formules en belangrijke definities - Oefen met de voorbeelden in elke sectie - Memoriseer niet zonder de onderliggende concepten te begrijpen

| Term | Definition | |------|------------| | Rooster (Lattice) | Een rooster is een discrete n-dimensionale ruimte verkregen door gehele combinaties van basisvectoren. Het concept wordt vaak gedefinieerd door een set basisvectoren die de structuur van het rooster bepalen. | | Basisvectoren | De fundamentele vectoren die, wanneer gecombineerd met gehele getallen, alle punten binnen een rooster kunnen genereren. De kwaliteit van de basisvectoren (bijvoorbeeld orthogonaliteit) heeft invloed op de complexiteit van roosterproblemen. | | Kortste Vector Probleem (SVP) | Het probleem om binnen een gegeven rooster, gedefinieerd door zijn basisvectoren, een niet-nul vector te vinden met de kleinst mogelijke lengte. Dit is een fundamenteel probleem in de rooster-gebaseerde cryptografie. | | Dichtstbijzijnde Vector Probleem (CVP) | Een generalisatie van het SVP waarbij, gegeven een rooster en een doelvector, de taak is om een vector in het rooster te vinden die het dichtst bij de doelvector ligt. | | Bounded Distance Decoding (BDD) | Een variant van het CVP waarbij gegarandeerd is dat de doelvector zich binnen een bekende afstand 'd' van het rooster bevindt. Dit probleem is nauw verwant aan CVP en wordt gebruikt in sommige cryptografische constructies. | | Short Integer Solution (SIS) | Een rooster-gebaseerd probleem waarbij gezocht wordt naar een korte oplossing 's' (een vector met kleine gehele waarden zoals 0, 1, -1) voor de vergelijking $A \ast s = 0$, waarbij 'A' een matrix van vectoren is. | | Learning With Errors (LWE) | Een cryptografisch probleem dat draait om het oplossen van stelsels van lineaire vergelijkingen met toegevoegde 'ruis' of 'foutvectoren'. De moeilijkheid van LWE is bewezen equivalent aan die van bepaalde roosterproblemen, wat het aantrekkelijk maakt voor cryptografie. | | Ring Learning With Errors (RLWE) | Een uitbreiding van het LWE-probleem die gebruik maakt van ringen in plaats van algemene lineaire algebra. RLWE leidt vaak tot kleinere sleutelgroottes in cryptografische schema's. | | Quantum-resistent | Een eigenschap van cryptografische algoritmen of problemen die bestand zijn tegen aanvallen met kwantumcomputers. Rooster-gebaseerde cryptografische problemen worden beschouwd als quantum-resistent. | | Kwantum Shor Algoritme | Een bekend algoritme voor kwantumcomputers dat efficiënt bepaalde wiskundige problemen kan oplossen, zoals priemfactorisatie en discrete logaritmen. Dit algoritme is niet effectief tegen rooster-gebaseerde cryptografische problemen. |