Lernen mit (signierten) Fehlern

$\underline{\bf Background}$

Im Jahr 2005 führte Regev [1] das Problem des Lernens mit Fehlern (Learning with Errors, LWE) ein, eine Verallgemeinerung des Problems der Lernparität mit Fehlern. Die Annahme der Härte dieses Problems für bestimmte Parameterauswahl liegt nun den Sicherheitsnachweisen für eine Vielzahl von Post-Quanten-Kryptosystemen auf dem Gebiet der gitterbasierten Kryptographie zugrunde. Die "kanonischen" Versionen von LWE werden unten beschrieben.

Vorbereitungen:

Sei die additive Gruppe von Reals Modulo 1, dh nehme Werte in . Für positive ganze Zahlen und , ein "Geheimnis" Vektor , eine Wahrscheinlichkeitsverteilung auf , lassen ist die Verteilung auf die durch einheitliche Auswahl von bei erhalten wird zufällig, einen Fehlerterm und$\mathbb{T} = \mathbb{R}/\mathbb{Z}$$[0, 1)$$n$$2 \le q \le poly(n)$${\bf s} \in \mathbb{Z}_q^n$$\phi$$\mathbb{R}$$A_{{\bf s}, \phi}$$\mathbb{Z}_q^n \times \mathbb{T}$${\bf a} \in \mathbb{Z}_q^n$$x \leftarrow \phi$$({\bf a}, b' = \langle{\bf a}, s\rangle/q + x) \in \mathbb{Z}_q^n \times \mathbb{T}$.

Sei $A_{{\bf s}, \overline{\phi}}$ die "Diskretisierung" von $A_{{\bf s}, \phi}$ . Das heißt, wir ziehen zuerst eine Stichprobe $({\bf a}, b')$ aus $A_{{\bf s}, \phi}$ und geben dann $({\bf a}, b) = ({\bf a}, \lfloor b'\cdot q\rceil) \in \mathbb{Z}_q^n \times \mathbb{Z}_q$ . Hier bezeichnet $\lfloor\circ\rceil$ die Rundung $\circ$ auf den nächsten Integralwert, sodass wir $({\bf a}, b)$ als $({\bf a}, b= \langle {\bf a}, {\bf s} \rangle + \lfloor q\cdot x\rceil)$ .

In der kanonischen Einstellung nehmen wir die Fehlerverteilung als Gaußsch an. Für jedes ist die Dichtefunktion einer eindimensionalen Gaußschen Wahrscheinlichkeitsverteilung über gegeben durch . Wir schreiben als Abkürzung für die Diskretisierung vonα > 0 R D α ( x ) = e - π ( x / α ) 2 / α A s , α A s , D $\phi$$\alpha > 0$$\mathbb{R}$$D_{\alpha}(x)=e^{-\pi(x/\alpha)^2}/\alpha$$A_{{\bf s}, \alpha}$$A_{{\bf s}, D_\alpha}$

LWE Definition:

In der Suchversion wir gegeben Proben von , die wir als "verrauschten" linearen Gleichungen anzeigen können (Anmerkung: ): N = p o l y ( n ) A s , α a i , s ∈ Z n q , b i ∈ Z$LWE_{n, q, \alpha}$$N = poly(n)$$A_{{\bf s}, \alpha}$${\bf a}_i, {\bf s} \in \mathbb{Z}_q^n, b_i \in \mathbb{Z}_q$

⋮ ⟨ a N , s ⟩ ≈ & khgr; b

$$\langle{\bf a}_1, {\bf s}\rangle \approx_\chi b_1\mod q$$ $$\vdots$$ $$\langle{\bf a}_N, {\bf s}\rangle \approx_\chi b_N\mod q$$

wobei der Fehler in jeder Gleichung unabhängig von einem (zentrierten) diskreten Gaußschen mit der Breite . Unser Ziel ist es, wiederherzustellen . (Beachten Sie, dass wir dies ohne Fehler mit der Gaußschen Eliminierung lösen können, aber bei Vorhandensein dieses Fehlers schlägt die Gaußsche Eliminierung dramatisch fehl.)$\alpha q$${\bf s}$

In der Entscheidungsversion wir Zugriff auf ein Orakel , das bei Abfrage Stichproben zurückgibt . Es wird uns versprochen, dass die Stichproben entweder alle von oder von der Gleichverteilung . Unser Ziel ist es zu unterscheiden, was der Fall ist.O s ( a , b ) A s , α U ( Z n q ) × U ( Z q$DLWE_{n, q, \alpha}$$\mathcal{O}_{\bf s}$$({\bf a}, b)$$A_{{\bf s}, \alpha}$$U(\mathbb{Z}_q^n)\times U(\mathbb{Z}_q)$

Es wird angenommen, dass beide Probleme wenn .α q > 2 $hard$$\alpha q > 2\sqrt n$

Verbindung zur Komplexitätstheorie:

Es ist bekannt (siehe [1], [2] für Details), dass LWE der Lösung eines BDD-Problems (Bounded Distance Decoding) auf dem Doppelgitter einer GapSVP-Instanz entspricht. Ein Polynomzeitalgorithmus für LWE würde einen Polynomzeitalgorithmus implizieren, um bestimmte Gitterprobleme wie SIVP und SVP innerhalb von zu approximieren, wobei ein kleiner Polynomfaktor ist (z. B. ).1/αn$\tilde O(n/\alpha)$$1/\alpha$$n^2$

Aktuelle algorithmische Grenzen

Wenn für streng kleiner als 1/2 ist, geben Arora und Ge [3] einen subexponentiellen Zeitalgorithmus für LWE an. Die Idee ist, dass nach bekannten Eigenschaften des Gaußschen Zeichnungsfehlers diese kleinen Begriffe in eine "strukturierte Rausch" -Einstellung passen, außer mit exponentiell geringer Wahrscheinlichkeit. Intuitiv erhalten wir in dieser Einstellung jedes Mal, wenn wir 1 Probe erhalten hätten, einen Block von Proben mit dem Versprechen, dass nicht mehr als ein konstanter Bruch Fehler enthält. Sie verwenden diese Beobachtung, um das Problem zu "linearisieren" und über den Fehlerraum aufzuzählen. ϵ $\alpha q \le n^\epsilon$$\epsilon$$m$

$\underline{\bf Question}$

Angenommen, wir erhalten stattdessen Zugriff auf ein Orakel . Bei der Abfrage fragt zuerst , um eine Stichprobe zu erhalten . Wenn aus , gibt eine Stichprobe zurück wobei die "Richtung" (oder bewertetes "Vorzeichen") des Fehlerterms darstellt . Wenn zufällig gezeichnet wurde, kehrt zurück O + $\mathcal{O}_{\bf s}^+$$\mathcal{O}_{\bf s}^+$ ( a ,b)( a ,b) A s , $\mathcal{O}_{\bf s}$$({\bf a}, b)$$({\bf a}, b)$$A_{{\bf s}, \alpha}$ ( a ,$\mathcal{O}_{\bf s}^+$ d ± ( a , b ) O. + s ( a , b , d ) ← $({\bf a}, b, d) \in \mathbb{Z}_q^n \times \mathbb{Z}_q \times \mathbb{Z}_2$$d$$\pm$$({\bf a}, b)$$\mathcal{O}_{\bf s}^+$d $({\bf a}, b, d) \leftarrow U(\mathbb{Z}_q^n)\times U(\mathbb{Z}_q)\times U(\mathbb{Z}_2)$ . (Alternativ könnten wir den Fall betrachten, in dem das Bit kontrovers gewählt wird, wenn gleichmäßig zufällig gezeichnet wird.)$d$$b$

Sei wie zuvor, außer dass jetzt für eine ausreichend große Konstante , sagen wir. (Dies soll sicherstellen, dass der absolute Fehler in jeder Gleichung nicht beeinflusst wird.) Definieren Sie die LWSE-Probleme (Learning with Signed Error) und wie zuvor, außer dass Jetzt haben wir den zusätzlichen Rat für jedes Vorzeichen jedes Fehlerbegriffs.& agr; q > c $n, q, \alpha$ cLWSE n , q , α DL$\alpha q > c\sqrt n$$c$$LWSE_{n, q, \alpha}$$DLWSE_{n, q, \alpha}$

Sind beide Versionen von LWSE wesentlich einfacher als ihre LWE-Kollegen?

Z.B

1. Gibt es einen subexponentiellen Zeitalgorithmus für LWSE?

2. Was ist mit einem Polynom-Zeit-Algorithmus, der beispielsweise auf linearer Programmierung basiert?

Zusätzlich zu der obigen Diskussion ist meine Motivation ein Interesse an der Erforschung algorithmischer Optionen für LWE (von denen wir derzeit relativ wenige zur Auswahl haben). Insbesondere hängt die einzige bekannte Einschränkung, die gute Algorithmen für das Problem bereitstellt, mit der Größe der Fehlerterme zusammen. Hier bleibt die Größe gleich, aber der Fehlerbereich in jeder Gleichung ist jetzt in gewisser Weise "monoton". (Ein letzter Kommentar: Mir ist diese Formulierung des in der Literatur auftretenden Problems nicht bekannt; sie scheint originell zu sein.)

Verweise:

[1] Regev, Oded. "Über Gitter, Lernen mit Fehlern, zufälligen linearen Codes und Kryptographie" in JACM 2009 (ursprünglich bei STOC 2005) ( PDF )

[2] Regev, Oded. "Das Problem des Lernens mit Fehlern", eingeladene Umfrage auf der CCC 2010 ( PDF )

[3] Arora, Sanjeev und Ge, Rong. "Neue Algorithmen zum Lernen bei Fehlern" auf der ICALP 2011 ( PDF )

(Wow! Nach drei Jahren ist das jetzt leicht zu beantworten. Komisch, wie das geht! - Daniel)

Dieses Problem des "Lernens mit (signierten) Fehlern" ( LWSE ), wie es oben von mir (vor drei Jahren) erfunden und angegeben wurde, reduziert sich trivial aus dem Problem des erweiterten Lernens mit Fehlern ( eLWE ), das erstmals in der Arbeit Bi-Deniable Public eingeführt wurde -Tastenverschlüsselung von O'Neill, Peikert und Waters auf der CRYPTO 2011.

Das eLWE- Problem wird analog zum "Standard" -LWE (dh [ Regev2005 ]) definiert, außer dass dem (effizienten) Unterscheidungsmerkmal der Verteilungen zusätzlich "Hinweise" auf den Fehlervektor der LWE-Probe in Form von ( möglicherweise verrauschte) innere Produkte mit einem beliebigen Vektor . (In Anwendungen ist häufig der Entschlüsselungsschlüsselvektor eines Kryptosystems.)→ z → $\vec{x}$$\vec{z}$$\vec{z}$

Formal wird das wie folgt beschrieben:$\mathsf{eLWE}_{n,m,q,\chi,\beta}$

---

Für eine ganze Zahl und eine Fehlerverteilung über besteht das Problem des erweiterten Lernens mit Fehlern darin, zwischen den folgenden Verteilungspaaren zu unterscheiden: Dabei ist und und wobeiχ = χ ( n ) Z q { A , → b = A$q = q(n) \ge 2$$\chi = \chi(n)$$\mathbb{Z}_q$

$$\{\mathbf{A}, \vec{b} = \mathbf{A}^T\vec{s}+\vec{x}, \vec{z}, \langle\vec{z}, \vec{x}\rangle + x' \},$$ A ← Z n × m q , → s ← Z n q , → u ← Z m q , → x , → z ← χ m , x ' ← D β q D α $$\{\mathbf{A}, \vec{u}, \vec{z}, \langle\vec{z}, \vec{x}\rangle + x' \},$$ $\mathbf{A}\leftarrow \mathbb{Z}_q^{n\times m}, \vec{s}\leftarrow\mathbb{Z}_q^n, \vec{u}\leftarrow\mathbb{Z}_q^m, \vec{x}, \vec{z}\leftarrow\chi^m,$$x'\leftarrow\mathcal{D}_{\beta q}$$\mathcal{D}_\alpha$ist die (eindimensionale) diskrete Gaußsche Verteilung mit der Breite .$\alpha$

---

Es ist leicht zu erkennen, dass eLWE "den Geist" von LWSE einfängt , obwohl eine formale Reduzierung mit nicht allzu viel zusätzlichem Aufwand gezeigt werden kann.

In den Arbeiten werden wichtige Folgeideen zum Verständnis des Extended-LWE-Problems entwickelt:

• Rundschreiben- und KDM-Sicherheit für identitätsbasierte Verschlüsselung durch Alperin-Sheriff und Peikert
• Klassische Härte des Lernens mit Fehlern von Brakerski, Langlois, Peikert, Regev und Stehle

Abhängig davon, ob Ihr geheimer Schlüssel in oder binär ist (und von der Art der verschiedenen anderen Parameteroptionen), können Sie die Reduzierungen des ersten oder zweiten Papiers verwenden, um letztendlich quantitativ / klassisch von reduzieren mit Approximationsfaktor zu LWSE .G a p S V P α α≥Ω( n 1,5$\mathbb{Z}_q$$\mathsf{GapSVP}_\alpha$$\alpha \ge \Omega(n^{1.5})$