Apprendre avec des erreurs (signées)

$\underline{\bf Background}$

En 2005, Regev [1] a introduit le problème d'apprentissage avec erreurs (LWE), une généralisation du problème de parité d'apprentissage avec erreur. L'hypothèse de la dureté de ce problème pour certains choix de paramètres sous-tend désormais les preuves de sécurité pour une multitude de cryptosystèmes post-quantiques dans le domaine de la cryptographie sur réseau. Les versions "canoniques" de LWE sont décrites ci-dessous.

Préliminaires:

Soit le groupe additif de réels modulo 1, c'est-à-dire prenant des valeurs dans . Pour les entiers positifs et , un vecteur "secret" , une distribution de probabilité on , soit soit la distribution sur obtenue en choisissant uniformément à aléatoire, dessinant un terme d'erreur et sortie$\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}$.

Soit la "discrétisation" de . Autrement dit, nous dessinons d'abord un échantillon partir de puis nous sortons . Ici, indique l'arrondi à la valeur intégrale la plus proche, afin que nous puissions voir comme .$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)$

Dans le cadre canonique, nous considérons que la distribution d'erreur est gaussienne. Pour tout , la fonction de densité d'une distribution de probabilité gaussienne à 1 dimension sur est donnée par . Nous écrivons comme raccourci pour la discrétisation de$\phi$$\alpha > 0$$\mathbb{R}$$D_{\alpha}(x)=e^{-\pi(x/\alpha)^2}/\alpha$$A_{{\bf s}, \alpha}$$A_{{\bf s}, D_\alpha}$

Définition LWE:

Dans la version de recherche nous recevons échantillons de , que nous pouvons voir comme des équations linéaires "bruyantes" (Remarque: ):$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$

où l'erreur dans chaque équation est tirée indépendamment d'une gaussienne discrète (centrée) de largeur . Notre objectif est de récupérer . (Notez que, sans erreur, nous pouvons résoudre ce problème avec l'élimination gaussienne, mais en présence de cette erreur, l'élimination gaussienne échoue de façon spectaculaire.)$\alpha q$${\bf s}$

Dans la version de décision , nous avons accès à un oracle qui renvoie des échantillons lorsqu'il est interrogé. On nous promet que les échantillons proviennent tous de ou de la distribution uniforme . Notre objectif est de distinguer ce qui est le cas.$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)$

On pense que les deux problèmes sont lorsque .$hard$$\alpha q > 2\sqrt n$

Lien avec la théorie de la complexité:

Il est connu (voir [1], [2] pour plus de détails) que LWE correspond à la résolution d'un problème de BDD (Bounded Distance Decoding) sur le double réseau d'une instance GapSVP. Un algorithme de temps polynomial pour LWE impliquerait un algorithme de temps polynomial pour approximer certains problèmes de réseau tels que SIVP et SVP dans où est un petit facteur polynomial (disons, ).$\tilde O(n/\alpha)$$1/\alpha$$n^2$

Limites algorithmiques actuelles

Lorsque pour strictement inférieur à 1/2, Arora et Ge [3] donnent un algorithme de temps sous-exponentiel pour LWE. L'idée est que, à partir de propriétés bien connues de la gaussienne, en tirant des termes d'erreur, ce petit s'inscrit dans un cadre de "bruit structuré", sauf avec une probabilité exponentiellement faible. Intuitivement dans ce cadre, chaque fois que nous aurions reçu 1 échantillon, nous recevons un bloc de échantillons avec la promesse que pas plus d'une fraction constante ne contient d'erreur. Ils utilisent cette observation pour «linéariser» le problème et énumérer l'espace d'erreur.$\alpha q \le n^\epsilon$$\epsilon$$m$

$\underline{\bf Question}$

Supposons que nous ayons à la place un accès à un oracle . Lors d'une requête, premières requêtes pour obtenir un échantillon . Si été tiré de , alors renvoie un échantillon où représente la "direction" (ou "signe" évalué par ) du terme d'erreur . Si été tiré au hasard, alors renvoie$\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)$ . (Alternativement, nous pourrions considérer le cas où le bit est choisi de manière adversaire lorsque est tiré uniformément au hasard.)$d$$b$

Soit comme avant, sauf que maintenant pour une constante suffisamment grande , disons. (Ceci permet de garantir que l'erreur absolue dans chaque équation reste inchangée.) Définissez les problèmes d'apprentissage avec erreur signée (LWSE) et comme avant, sauf que nous avons maintenant le conseil supplémentaire pour le signe de chaque terme d'erreur.$n, q, \alpha$$\alpha q > c\sqrt n$$c$$LWSE_{n, q, \alpha}$$DLWSE_{n, q, \alpha}$

Les deux versions de LWSE sont-elles beaucoup plus faciles que leurs homologues LWE?

Par exemple

1. Existe-t-il un algorithme de temps sous-exponentiel pour LWSE?

2. Qu'en est-il d'un algorithme polynomial basé sur, disons, une programmation linéaire?

En plus de la discussion ci-dessus, ma motivation est un intérêt à explorer les options algorithmiques pour LWE (dont nous avons actuellement relativement peu de choix). En particulier, la seule restriction connue pour fournir de bons algorithmes pour le problème est liée à l' ampleur des termes d'erreur. Ici, l'ampleur reste la même, mais la plage d'erreur dans chaque équation est désormais "monotone" d'une certaine manière. (Un dernier commentaire: je ne connais pas cette formulation du problème apparaissant dans la littérature; elle semble originale.)

Références:

[1] Regev, Oded. «On Lattices, Learning with Errors, Random Linear Codes, and Cryptography», dans JACM 2009 (à l'origine au STOC 2005) ( PDF )

[2] Regev, Oded. «Le problème de l'apprentissage avec des erreurs», sondage invité au CCC 2010 ( PDF )

[3] Arora, Sanjeev et Ge, Rong. «Nouveaux algorithmes d'apprentissage en présence d'erreurs», à ICALP 2011 ( PDF )

(wow! après trois ans, cela est maintenant facile de répondre. drôle comment ça se passe! - Daniel)

Ce problème "Apprentissage avec des erreurs (signées)" ( LWSE ), tel qu'inventé et déclaré ci-dessus par moi (il y a trois ans), se réduit de manière triviale au problème d' apprentissage étendu avec erreurs ( eLWE ) introduit pour la première fois dans l'ouvrage Bi-Deniable Public -Cryptage des clés par O'Neill, Peikert et Waters au CRYPTO 2011.

Le problème eLWE est défini de manière analogue à la LWE "standard" (c'est-à-dire [ Regev2005 ]), sauf que le distinguant (efficace) des distributions reçoit en outre des "indices" sur le vecteur d'erreur de l'échantillon LWE , sous la forme de ( produits intérieurs éventuellement bruyants) avec un vecteur arbitraire . (Dans les applications, est souvent le vecteur de clé de déchiffrement de certains cryptosystèmes.)$\vec{x}$$\vec{z}$$\vec{z}$

Formellement, le est décrit comme suit:$\mathsf{eLWE}_{n,m,q,\chi,\beta}$

Pour un entier et une distribution d'erreur sur , le problème de l'apprentissage étendu avec erreurs consiste à distinguer les paires de distributions suivantes: où et , et où$q = q(n) \ge 2$$\chi = \chi(n)$$\mathbb{Z}_q$

Il est facile de voir qu'eLWE capture "l'esprit" de LWSE , bien qu'une réduction formelle puisse être montrée sans trop d'efforts supplémentaires.

Les principales idées de suivi pour comprendre le problème de l'EWL étendu sont développées dans les travaux:

• Sécurité circulaire et KDM pour le chiffrement basé sur l'identité par Alperin-Sheriff et Peikert
• Dureté classique de l'apprentissage avec erreurs de Brakerski, Langlois, Peikert, Regev et Stehle

Selon que votre clé secrète se trouve dans ou est binaire (et la nature de divers autres choix de paramètres), vous pouvez utiliser les réductions du premier ou du deuxième papier pour finalement réduire de manière quantique / classique de avec facteur d'approximation à LWSE .$\mathbb{Z}_q$$\mathsf{GapSVP}_\alpha$$\alpha \ge \Omega(n^{1.5})$