Gitterproblem

Im Informatik, Gitterprobleme sind eine Klasse von Optimierung Probleme im Zusammenhang mit mathematischen Objekten genannt Gitter. Die mutmaßliche Unverdierbarkeit solcher Probleme ist von zentraler Bedeutung für die Konstruktion von sicherem Kryptosysteme auf Gitterbasis: Gitterprobleme sind ein Beispiel für Np-harte Probleme, die gezeigt wurden Durchschnittlicher Fall hartBereitstellung eines Testfalls für die Sicherheit von kryptografischen Algorithmen. Darüber hinaus können einige Gitterprobleme, die hartnäckig sind, als Grundlage für extrem sichere kryptografische Schemata verwendet werden. Die Verwendung von Härte der schlimmsten Fall in solchen Schemata macht sie zu den wenigen Schemata, die sogar gegeneinander sicher sind Quantencomputer. Für Anwendungen in solchen Kryptosysteme, Gitter über Vektorraum (häufig ${\ displaystyle \ mathbb {q} ^{n}}$) oder Kostenlose Module (häufig ${\ displaystyle \ mathbb {z} ^{n}}$) werden allgemein berücksichtigt.

Nehmen wir für alle nachstehenden Probleme an, dass wir angegeben werden (zusätzlich zu anderen spezifischeren Eingaben) a Basis Für den Vektorraum V und ein Norm N. Die normalerweise berücksichtigte Norm ist die euklidische Norm L². Andere Normen (wie z. L^p) werden auch in einer Vielzahl von Ergebnissen berücksichtigt und zeigen sich.^[1] Lassen ${\ displayStyle \ lambda (l)}}$ bezeichnen die Länge des kürzesten Vektors ungleich Null im Gitter L, das ist,

$oder$

Kürzestes Vektorproblem (SVP)

Dies ist eine Darstellung des kürzesten Vektorproblems (Basisvektoren im blauen, kürzesten Vektor in Rot).

Im SVP, a Basis von a Vektorraum V und ein Norm N (häufig L²) werden für ein Gitter gegeben L und man muss den kürzesten Vektor ungleich Null finden V, gemessen von N, in L. Mit anderen Worten, der Algorithmus sollte einen Vektor ungleich Null ausgeben v so dass ${\ displayStyle n (v) = \ lambda (l)}$.

In der γ-Anerkennung Version SVP_γMan muss höchstens einen Gittervektor ungleich Null finden ${\ displaystyle \ gamma \ cdot \ lambda (l)}$ für gegeben ${\ displayStyle \ gamma \ Geq 1}$.

Härte Ergebnisse

Die genaue Version des Problems ist nur bekannt als Np-harte für randomisierte Reduktionen.^[2][3]

Im Gegensatz dazu das entsprechende Problem in Bezug auf die einheitliche Norm Es ist bekannt, dass es ist Np-harte.^[4]

Algorithmen für die euklidische Norm

Um die genaue Version des SVP unter der euklidischen Norm zu lösen, sind verschiedene Ansätze bekannt, die in zwei Klassen aufgeteilt werden können: Algorithmen, die eine Überexponentialzeit erfordern${\ displayStyle 2^{\ Omega (n)}}$) und ${\ displayStyle \ operatorname {poly} (n)}$ Speicher und Algorithmen, die sowohl exponentielle Zeit als auch Platz erfordern (Platz${\ displayStyle 2^{\ theta (n)}}$) in der Gitterdimension. Die frühere Klasse von Algorithmen umfasst vor allem die Gitteraufzählung^[5][6][7] und zufällige Stichprobenreduktion,^[8][9] Während letztere Gittersiebvern beinhaltet,^[10][11][12] Berechnung der Voronoi -Zelle des Gitters,^[13][14] und diskrete Gaußsche Probenahme.^[15] Ein offenes Problem ist, ob Algorithmen zur Lösung von exakten SVP in einzelnen Exponentialzeiten (${\ displayStyle 2^{o (n)}}$) und das polynomiale Gedächtnis in der Gitterdimension erfordert.^[16]

Um die γ-Anerkennung Version SVP zu lösen_γ zum ${\ displayStyle \ gamma> 1}$ Für die euklidische Norm basieren die bekanntesten Ansätze auf der Verwendung Reduzierung der Gitterbasis. Für große ${\ displayStyle \ gamma = 2^{\ Omega (n)}}$, das Lenstra -Genstra -Lovász (LLL) -Algorithmus Kann eine Lösung in der Zeitpolynom in der Gitterdimension finden. Für kleinere Werte ${\ displayStyle \ gamma}$, der Blockkorkine-Zolotarev-Algorithmus (BKZ)^[17][18][19] wird üblich ${\ displayStyle \ Beta}$) bestimmt die zeitliche Komplexität und die Ausgangsqualität: für große Approximationsfaktoren ${\ displayStyle \ gamma}$, eine kleine Blockgröße ${\ displayStyle \ Beta}$ reicht aus, und der Algorithmus endet schnell. Für kleine ${\ displayStyle \ gamma}$, größer ${\ displayStyle \ Beta}$ sind benötigt, um ausreichend kurze Gittervektoren zu finden, und der Algorithmus dauert länger, um eine Lösung zu finden. Der BKZ -Algorithmus verwendet intern einen exakten SVP ${\ displayStyle \ Beta}$), und seine Gesamtkomplexität hängt eng mit den Kosten dieser SVP -Aufrufe in der Dimension zusammen ${\ displayStyle \ Beta}$.

Gapsvp

Das Problem gapsvp_β besteht darin, zwischen den Fällen von SVP zu unterscheiden, in denen die Länge des kürzesten Vektors höchstens ist ${\ displayStyle 1}$ oder größer als ${\ displayStyle \ Beta}$, wo ${\ displayStyle \ Beta}$ Kann eine feste Funktion der Dimension des Gitters sein ${\ displayStyle n}$. Angesichts einer Grundlage für das Gitter muss der Algorithmus entscheiden, ob ${\ displaystyle \ lambda (l) \ leq 1}$ oder ${\ displayStyle \ lambda (l)> \ Beta}$. Wie andere Probleme versprechenDer Algorithmus darf in allen anderen Fällen irren.

Eine weitere Version des Problems ist GAPSVP_{ζ, γ} für einige Funktionen ${\ displaystyle \ zeta, \ gamma}$. Der Eingang zum Algorithmus ist eine Basis ${\ displayStyle B}$ und eine Nummer ${\ displayStyle d}$. Es ist sicher, dass alle Vektoren in der Gram -Schmidt -Orthogonalisierung sind mindestens 1 von Länge, und das ${\ displayStyle \ lambda (l (b)) \ ​​leq \ zeta (n)}$ und das ${\ displayStyle 1 \ leq d \ leq \ zeta (n)/\ gamma (n)}$ wo ${\ displayStyle n}$ ist die Dimension. Der Algorithmus muss akzeptieren, wenn ${\ displayStyle \ lambda (l (b)) \ ​​leq d}$, und ablehnen, wenn ${\ displayStyle \ lambda (l (b)) \ ​​Geq \ gamma (n) .d}$. Für große ${\ displayStyle \ zeta}$ (d.h. ${\ displayStyle \ zeta (n)> 2^{n/2}}$) Das Problem entspricht GAPSVP_γ Weil^[20] eine Vorverarbeitung mit dem mit dem durchgeführten LLL -Algorithmus macht den zweiten Zustand (und damit, ${\ displayStyle \ zeta}$) überflüssig.

Nächstes Vektorproblem (CVP)

Dies ist eine Darstellung des engsten Vektorproblems (Basisvektoren im blauen, externen Vektor in grünem, nächstem Vektor in Rot).

In CVP eine Grundlage eines Vektorraums V und ein metrisch M (häufig L²) werden für ein Gitter gegeben Lsowie ein Vektor v in V aber nicht unbedingt in L. Es ist erwünscht, den Vektor in zu finden L am nächsten v (gemessen von M). In dem ${\ displayStyle \ gamma}$-Apploximation Version CVP_γMan muss höchstens einen Gittervektor finden ${\ displayStyle \ gamma}$.

Beziehung zu SVP

Das nächstgelegene Vektorproblem ist eine Verallgemeinerung des kürzesten Vektorproblems. Es ist leicht zu zeigen, dass eine gegebene Orakel für CVP_γ (definiert unten), kann man SVP lösen_γ indem Sie einige Fragen zum Orakel machen.^[21] Die naive Methode, um den kürzesten Vektor zu finden, indem Sie den CVP aufrufen_γ Oracle, um den nächsten Vektor zu 0 zu finden, funktioniert nicht, da 0 selbst ein Gittervektor ist und der Algorithmus möglicherweise 0 ausgeben kann.

Die Reduzierung von SVP_γ zu CVP_γ ist wie folgt: Angenommen, die Eingabe zum SVP_γ ist die Grundlage für Gitter ${\ displaystyle b = [b_ {1}, b_ {2}, \ ldots, b_ {n}]}$. Betrachten Sie die Grundlage ${\ displaystyle b^{i} = [b_ {1}, \ ldots, 2b_ {i}, \ ldots, b_ {n}]}$ und lass ${\ displaystyle x_ {i}}$ Sei der von CVP zurückgegebene Vektor_γ(Bⁱ, b_i). Die Behauptung ist, dass der kürzeste Vektor im Satz ${\ displaystyle \ {x_ {i} -b_ {i} \}}$ ist der kürzeste Vektor im gegebenen Gitter.

Härte Ergebnisse

Goldreich et al. zeigten, dass jede Härte von SVP die gleiche Härte für CVP impliziert.^[22] Verwendung PCP Werkzeug, Arora et al. zeigten, dass CVP innerhalb des Faktors schwer annähern ist ${\ displayStyle 2 ^{\ log ^{1- \ epsilon} (n)}}$ wenn nicht $oder$.^[23] Dinur et al. verstärkte dies durch ein NP-Hartness-Ergebnis mit ${\ displayStyle \ epsilon = (\ log \ log n)^{c}}$ zum ${\ displayStyle c <1/2}$.^[24]

Kugel decodieren

Algorithmen für CVP, insbesondere die Fincke- und Pohst -Variante,^[6] wurden für die Datenerkennung in mehreren Eingängen mehrerer Ausgänge verwendet (Mimo) drahtlose Kommunikationssysteme (für codierte und unkodierte Signale).^[25][13] In diesem Zusammenhang heißt es Kugel decodieren Aufgrund des Radius, der intern in vielen CVP -Lösungen verwendet wird.^[26]

Es wurde im Bereich der Ganzzahl-Unklarheit auf Auflösung von Carrier-Phase-GNSS (GPS) angewendet.^[27] Es wird genannt Lambda -Methode in diesem Bereich. Im selben Bereich wird das allgemeine CVP -Problem als bezeichnet als Ganzzahl am wenigsten Quadrate.

Gapcvp

Dieses Problem ähnelt dem GAPSVP -Problem. Für gapsvp_βDie Eingabe besteht aus Gitterbasis und einem Vektor ${\ displayStyle v}$ und der Algorithmus muss beantworten, ob einer der folgenden Aussagen gilt:

• Es gibt einen Gittervektor, so dass der Abstand zwischen ihm und ${\ displayStyle v}$ ist höchstens 1.
• Jeder Gittervektor ist in einer Entfernung größer als ${\ displayStyle \ Beta}$ Weg von ${\ displayStyle v}$.

Die entgegengesetzte Bedingung ist, dass sich der engste Gittervektor in einiger Entfernung befindet ${\ displayStyle 1 <\ lambda (l) \ leq \ Beta}$, daher der Name LückeCVP.

Bekannte Ergebnisse

Das Problem ist trivial in Np für jeden Annäherungsfaktor.

Schnorr1987 zeigten, dass deterministische Polynomzeitalgorithmen das Problem für lösen können ${\ displayStyle \ Beta = 2^{o (n (\ log \ log n)^{2}/\ log n)}}$.^[28] Ajtai et al. zeigten, dass probabilistische Algorithmen einen etwas besseren Annäherungsfaktor von erreichen können ${\ displayStyle \ Beta = 2^{o (n \ log \ log n/\ log n)}}$.^[10]

1993 zeigte Banaszczyk, dass GAPCVP_n ist in ${\ displaystyle {\ mathsf {np \ cap conp}}}$.^[29] Im Jahr 2000 zeigten Goldreich und Goldschwasser das ${\ displayStyle \ Beta = {\ sqrt {n/\ log n}}}$ setzt das Problem sowohl in NP als auch in Backstein.^[30] Im Jahr 2005 zeigten Aharonov und Regev das für einige Konstante ${\ displayStyle c}$das Problem mit ${\ displayStyle \ Beta = C {\ sqrt {n}}}$ ist in ${\ displaystyle {\ mathsf {np \ cap conp}}}$.^[31]

Für Untergrenzen haben Dinur et al. zeigte 1998, dass das Problem np-hard ist ${\ displayStyle \ Beta = n^{o (1/\ log {\ log {n}})}}}$.^[32]

Kürzester unabhängiges Vektorenproblem (SIVP)

Mit einem Gitter der Dimension nDer Algorithmus muss ausgegeben werden n linear unabhängig ${\ displayStyle v_ {1}, v_ {2}, \ ldots, v_ {n}}$ so dass ${\ displaystyle \ max \ | v_ {i} \ | \ leq \ max _ {b} \ | b_ {i} \ |}$ wo die rechte Seite alle Basen berücksichtigt ${\ displaystyle b = \ {b_ {1}, \ ldots, b_ {n} \ \}}$ des Gitters.

In dem ${\ displayStyle \ gamma}$-Nachselbe Version, angesichts eines Gitters L mit Dimension n, finden n linear unabhängig Vektoren ${\ displayStyle v_ {1}, v_ {2}, \ ldots, v_ {n}}$ von Länge ${\ displaystyle \ max \ | v_ {i} \ | \ leq \ gamma \ lambda _ {n} (l)}$, wo ${\ displayStyle \ lambda _ {n} (l)}$ ist der ${\ displayStyle n}$'T. aufeinanderfolgende Minimum von ${\ displayStyle l}$.

Begrenzte Entfernungsdecodierung

Dieses Problem ähnelt CVP. Bei einem Vektor so, dass sein Abstand vom Gitter höchstens ist ${\ displayStyle \ lambda (l)/2}$Der Algorithmus muss den engsten Gittervektor ausgeben.

Abdeckung des Radius -Problems

Bei einer Grundlage für das Gitter muss der Algorithmus die größte Entfernung (oder in einigen Versionen, seine Annäherung) von jedem Vektor zum Gitter finden.

Kürzeste Basisproblem

Viele Probleme werden einfacher, wenn die Eingabebasis aus kurzen Vektoren besteht. Ein Algorithmus, der das kürzeste Basisproblem (SBP) löst ${\ displayStyle B}$, Ausgabe eine äquivalente Basis ${\ displayStyle B '}$ so dass die Länge des längsten Vektors in ${\ displayStyle B '}$ ist so kurz wie möglich.

Die Approximation Version SBP_γ Das Problem besteht darin, eine Basis zu finden, deren längster Vektor höchstens ist ${\ displayStyle \ gamma}$ Zeiten länger als der längste Vektor in kürzester Basis.

Verwendung in Kryptographie

Durchschnittlicher Fall Die Härte von Problemen bildet eine Grundlage für den Beweis für die Sicherheit für die meisten kryptografischen Systeme. Experimentelle Erkenntnisse deuten jedoch darauf hin, dass die meisten NP-HART-Probleme diese Eigenschaft fehlen: Sie sind wahrscheinlich nur am schlimmsten Fall. Viele Gitterprobleme wurden vermutet oder erwiesen sich als durchschnittlicher Fall, was sie zu einer attraktiven Klasse von Problemen machte, um kryptografische Systeme zu stützen. Darüber hinaus wurden schlimmste Härte einiger Gitterprobleme verwendet, um sichere kryptografische Schemata zu schaffen. Die Verwendung von Härte der schlimmsten Fall in solchen Schemata macht sie zu den wenigen Schemata, die sogar gegeneinander sicher sind Quantencomputer.

Die oben genannten Gitterprobleme sind leicht zu lösen, wenn der Algorithmus eine "gute" Grundlage bietet. Gitterreduktion Algorithmen zielen, die eine Grundlage für ein Gitter gegeben haben, um eine neue Basis aus relativ kurzer Zeit auszugeben, fast senkrecht Vektoren. Das Lenstra -Genstra -Lovász -Gitterbasis -Reduktionalgorithmus (LLL) war ein früh effizienter Algorithmus für dieses Problem, das in der Polynomzeit eine fast reduzierte Gitterbasis ausführen könnte.^[33] Dieser Algorithmus und seine weiteren Verfeinerungen wurden verwendet, um mehrere kryptografische Systeme zu brechen und seinen Status als sehr wichtiges Instrument in der Kryptanalyse festzustellen. Der Erfolg von LLL bei experimentellen Daten führte zu der Überzeugung, dass die Gitterreduktion in der Praxis ein leichtes Problem darstellen könnte. Dieser Glaube wurde jedoch in den späten neunziger Jahren in Frage gestellt, wobei mehrere neue Ergebnisse zur Härte von Gitterproblemen erzielt wurden Ajtai.^[2]

In seinen Samenpapieren zeigte Ajtai, dass das SVP-Problem NP-HART war und einige Verbindungen zwischen der schlimmsten Komplexität und entdeckte Durchschnittsfallkomplexität von einigen Gitterproblemen.^[2][3] Auf diesen Ergebnissen aufbauen, ajtai und Dwork erschuf ein öffentlicher Kryptosystem deren Sicherheit nachgewiesen werden könnte, nur die schlimmste Fallhärte einer bestimmten Version von SVP,^[34] Daher ist es das erste Ergebnis, das die Härte der Worst-Case-Härte verwendet hat, um sichere Systeme zu erstellen.^[35]

Siehe auch

• Lernen mit Fehlern
• Kurzes Ganzzahl -Lösungsproblem

Verweise

Weitere Lektüre

• Agrell, E.; Eriksson, T.; Vardy, A.; Zeger, K. (2002). "Nächste Punktsuche in Gitter". IEEE trans. Inf. Theorie. 48 (8): 2201–2214. doi:10.1109/tit.2002.800499.
• Micciancio, Daniele (2001). "Das kürzeste Vektorproblem ist {np} -Hard, um sich innerhalb einer Konstante zu nähern.". Siam Journal über Computing. 30 (6): 2008–2035. Citeseerx 10.1.1.93.6646. doi:10.1137/s0097539700373039. S2CID 42794945.
• Nguyen, Phong Q.; Stern, Jacques (2000). "Gitterreduzierung in Kryptologie: Ein Update". Verfahren des 4. Internationalen Symposiums über algorithmische Zahlentheorie. Springer-Verlag. S. 85–112. ISBN 978-3-540-67695-9.