Nauka z (podpisanymi) błędami

$\underline{\bf Background}$

W 2005 r. Regev [1] wprowadził problem uczenia się z błędami (LWE), uogólnienie problemu parzystości uczenia się z błędem. Założenie o twardości tego problemu dla niektórych wyborów parametrów leży obecnie u podstaw dowodów bezpieczeństwa dla wielu kryptosystemów post kwantowych w dziedzinie kryptografii opartej na sieci. „Kanoniczne” wersje LWE opisano poniżej.

Czynności wstępne:

Niech będzie addytywną grupą reals modulo 1, tzn. Przyjmującą wartości w . Dla dodatnich liczb całkowitych i , wektor „tajny” , rozkład prawdopodobieństwa na , niech to dystrybucja w uzyskana przez wybranie jednolicie w losowo, rysując wyrażenie błędu i wyprowadzając$\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}$.

Niech będzie „dyskretyzacją” . Oznacza to, że najpierw pobieramy próbkę z a następnie wyprowadzamy . Tutaj oznacza zaokrąglenie do najbliższej wartości całkowitej, dzięki czemu możemy zobaczyć jako .$A_{{\bf s}, \overline{\phi}}$$A_{{\bf s}, \phi}$$({\bf a}, b')$$A_{{\bf s}, \phi}$$({\bf a}, b) = ({\bf a}, \lfloor b'\cdot q\rceil) \in \mathbb{Z}_q^n \times \mathbb{Z}_q$$\lfloor\circ\rceil$$\circ$$({\bf a}, b)$$({\bf a}, b= \langle {\bf a}, {\bf s} \rangle + \lfloor q\cdot x\rceil)$

W ustawieniu kanonicznym bierzemy rozkład błędów za Gaussa. Dla dowolnego funkcję gęstości 1-wymiarowego rozkładu prawdopodobieństwa Gaussa nad podano jako . Piszemy jako skrót do dyskretyzacji$\phi$$\alpha > 0$$\mathbb{R}$$D_{\alpha}(x)=e^{-\pi(x/\alpha)^2}/\alpha$$A_{{\bf s}, \alpha}$$A_{{\bf s}, D_\alpha}$

Definicja LWE:

W wersji wyszukiwania otrzymujemy próbki z , które możemy postrzegać jako „zaszumione” równania liniowe (Uwaga: ):$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$

$$\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$$

gdzie błąd w każdym równaniu jest niezależnie rysowany z (wyśrodkowanego) dyskretnego Gaussa o szerokości . Naszym celem jest odzyskanie . (Zauważ, że bezbłędnie możemy to rozwiązać za pomocą eliminacji Gaussa, ale w przypadku tego błędu eliminacja Gaussa dramatycznie się nie udaje.)$\alpha q$${\bf s}$

W wersji decyzyjnej mamy dostęp do wyroczni która zwraca próbki po zapytaniu. Obiecujemy, że wszystkie próbki pochodzą albo z albo z jednolitego rozkładu . Naszym celem jest rozróżnienie, co się dzieje.$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)$

Uważa się, że oba problemy są gdy .$hard$$\alpha q > 2\sqrt n$

Związek z teorią złożoności:

Wiadomo (patrz [1], [2] w celu uzyskania szczegółów), że LWE odpowiada rozwiązaniu problemu dekodowania ograniczonej odległości (BDD) na podwójnej sieci instancji GapSVP. Algorytm wielomianu czasu dla LWE sugerowałby wielomianowy algorytm czasu do przybliżenia pewnych problemów z siecią, takich jak SIVP i SVP w gdzie jest małym czynnikiem wielomianowym (powiedzmy, ).$\tilde O(n/\alpha)$$1/\alpha$$n^2$

Aktualne limity algorytmiczne

Kiedy dla ściśle mniej niż 1/2, Arora i Ge [3] podają algorytm czasu podwykładniczego dla LWE. Chodzi o to, że z dobrze znanych właściwości Gaussa, rysując terminy błędów, to małe mieści się w ustawieniu „szumu strukturalnego” z wyjątkiem wykładniczo niskiego prawdopodobieństwa. Intuicyjnie w tym ustawieniu, za każdym razem, gdy otrzymalibyśmy 1 próbkę, otrzymujemy blok próbek z obietnicą, że nie więcej niż jakaś stała część zawiera błąd. Wykorzystują tę obserwację do „linearyzacji” problemu i wyliczenia w przestrzeni błędów.$\alpha q \le n^\epsilon$$\epsilon$$m$

$\underline{\bf Question}$

Załóżmy, że zamiast tego mamy dostęp do wyroczni . Po zapytaniu pierwsze zapytania celu uzyskania próbki . Jeśli zostało sporządzone z , to zwraca próbkę gdzie oznacza „kierunek” (lub -wartościowy „znak”) terminu błędu . Jeśli zostało narysowane losowo, to zwraca$\mathcal{O}_{\bf s}^+$$\mathcal{O}_{\bf s}^+$$\mathcal{O}_{\bf s}$$({\bf a}, b)$$({\bf a}, b)$$A_{{\bf s}, \alpha}$$\mathcal{O}_{\bf s}^+$$({\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}^+$$({\bf a}, b, d) \leftarrow U(\mathbb{Z}_q^n)\times U(\mathbb{Z}_q)\times U(\mathbb{Z}_2)$ . (Alternatywnie, moglibyśmy rozważyć przypadek, w którym bit jest wybierany przeciwnie, gdy jest losowane równomiernie losowo.)$d$$b$

Niech będzie jak poprzednio, z tym wyjątkiem, że teraz dla wystarczająco dużej stałej , powiedzmy. (Ma to na celu zapewnienie, że błąd bezwzględny w każdym równaniu pozostaje nienaruszony.) Zdefiniuj problemy z uczeniem się z błędem podpisania (LWSE) i jak poprzednio, z tym wyjątkiem, że teraz mamy dodatkową poradę dotyczącą znaku każdego terminu błędu.$n, q, \alpha$$\alpha q > c\sqrt n$$c$$LWSE_{n, q, \alpha}$$DLWSE_{n, q, \alpha}$

Czy którakolwiek wersja LWSE jest znacznie łatwiejsza niż ich odpowiedniki LWE?

Na przykład

1. Czy istnieje algorytm czasu podwykładniczego dla LWSE?

2. Co z algorytmem wielomianowym opartym na powiedzmy na programowaniu liniowym?

Oprócz powyższej dyskusji moją motywacją jest zainteresowanie badaniem opcji algorytmicznych dla LWE (z których obecnie mamy stosunkowo niewiele do wyboru). W szczególności jedyne znane ograniczenie zapewniające dobre algorytmy związane z problemem związane jest z wielkością terminów błędu. Tutaj wielkość pozostaje taka sama, ale zakres błędu w każdym równaniu jest teraz w pewnym sensie „monotoniczny”. (Ostatni komentarz: nie jestem świadomy tego sformułowania problemu pojawiającego się w literaturze; wydaje się być oryginalny).

Bibliografia:

[1] Regev, Oded. „O kratach, uczenie się na błędach, losowych kodach liniowych i kryptografii” w JACM 2009 (pierwotnie na STOC 2005) ( PDF )

[2] Regev, Oded. „The Learning with Errors Problem”, zaproszona ankieta na CCC 2010 ( PDF )

[3] Arora, Sanjeev i Ge, Rong. „Nowe algorytmy uczenia się w obecności błędów” na ICALP 2011 ( PDF )

(wow! po trzech latach minęło, teraz łatwo jest na nie odpowiedzieć. zabawne, jak to idzie! - Daniel)

Ten problem „Uczenie się z (podpisanymi) błędami” ( LWSE ), jak to wymyśliłem i stwierdziłem powyżej (trzy lata temu), trywialnie redukuje problem rozszerzonego uczenia się z błędami ( eLWE ) po raz pierwszy wprowadzony w pracy Bi-Deniable Public - Kluczowe szyfrowanie autorstwa O'Neilla, Peikerta i Watersa na CRYPTO 2011.

ELWE problemem jest zdefiniowany w sposób analogiczny do „standardowej” LWE (tj [ Regev2005 ]), z wyjątkiem rozkładu (wydajne) Wyróżnikiem dodatkowo otrzymali «wskazówki» On Error wektora w próbce lwe$\vec{x}$, w postaci (możliwie hałaśliwych) produktów wewnętrznych z dowolnym wektorem $\vec{z}$. (W aplikacjach$\vec{z}$ jest często wektorem klucza deszyfrującego w niektórych kryptosystemach).

Formalnie $\mathsf{eLWE}_{n,m,q,\chi,\beta}$ problem opisano w następujący sposób:

---

Dla liczby całkowitej $q = q(n) \ge 2$oraz rozkład błędów $\chi = \chi(n)$ nad $\mathbb{Z}_q$, problem rozszerzonej nauki z błędami polega na rozróżnieniu następujących par dystrybucji:

$$\{\mathbf{A}, \vec{b} = \mathbf{A}^T\vec{s}+\vec{x}, \vec{z}, \langle\vec{z}, \vec{x}\rangle + x' \},$$ $$\{\mathbf{A}, \vec{u}, \vec{z}, \langle\vec{z}, \vec{x}\rangle + x' \},$$ gdzie $\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,$ i $x'\leftarrow\mathcal{D}_{\beta q}$, i gdzie $\mathcal{D}_\alpha$ to (1-wymiarowy) dyskretny rozkład Gaussa z szerokością $\alpha$.

---

Łatwo zauważyć, że eLWE wychwytuje „ducha” LWSE , chociaż formalną redukcję można wykazać przy niezbyt dużym wysiłku.

W pracach opracowano główne pomysły dotyczące zrozumienia problemu Extended-LWE:

• Bezpieczeństwo cykliczne i KDM dla szyfrowania opartego na tożsamości przez Alperin-Sheriff i Peikert
• Klasyczna trudność uczenia się na błędach autorstwa Brakerskiego, Langloisa, Peikert, Regev i Stehle

W zależności od tego, czy mieszka twój tajny klucz $\mathbb{Z}_q$ lub jest binarny (i charakter różnych innych parametrów), możesz użyć redukcji pierwszego lub drugiego papieru, aby ostatecznie kwantowo / klasycznie zmniejszyć od $\mathsf{GapSVP}_\alpha$ ze współczynnikiem przybliżenia $\alpha \ge \Omega(n^{1.5})$do LWSE .