înregistrare Logare
Puncte:2
Myath avatar Crypto

Recuperare trapă din eșantionarea preimagine pe bază de rețea

drapel in
Myath

[GPV] și [MP] (referințele de mai jos) oferă construcții ale funcției de trapă definită de $$ f_{\mathbf A} (\mathbf x) = \mathbf A \mathbf x, $$ Unde $\mathbf A \in \mathbb Z_q^{n \times m}$ este uniform aleatoriu, iar domeniul este $\{ \mathbf x \in \mathbb Z^m \mid \lVert x \rVert \le \beta\}$. Având în vedere oricare $\mathbf y \in \mathbb Z_q^n$, trapa secretă permite calcularea unei imagini prealabile $\mathbf x$ de $\mathbf y$, adică $\mathbf A \mathbf x = \mathbf y$ și $\lVert \mathbf x \rVert \le \beta$.

Trapa din [GPV] este un set de rang complet $\mathbf S \in \mathbb Z^{m \times m}$ astfel încât $\mathbf A \mathbf S = 0$. Trapa din [MP] este $\mathbf R$ astfel încât $\mathbf A \begin{bmatrix} \mathbf R \ \mathbf I \end{bmatrix} = \mathbf G$, Unde $\mathbf G$ este o matrice specială de gadgeturi publice. În orice caz, fiecare trapă are asociată o cantitate $s$ care descrie calitatea acestuia. Pentru $\mathbf S$, $s =$ norma max a coloanelor lui Gram-Schmidt $\tilde{\mathbf S}$ de $\mathbf S$. Pentru $\mathbf R$, $s = $ cea mai mare valoare singulară a $\mathbf R$.

Având în vedere oricare $\mathbf y$, o trapă de calitate $s$ permite eșantionarea din distribuția Gaussiană discretă peste $\{\mathbf{x} \mid \mathbf A\mathbf x = \mathbf y\}$ de latime $\sigma \ge s\cdot\omega(\sqrt{\log m})$, care dă $\lVert x \rVert \le \sigma\sqrt m$ (cu o probabilitate copleșitoare).

Întrebarea mea este despre invers. Să presupunem că avem un oracol pentru eșantionarea preimagine gaussiană care oferă soluții pentru $\mathbf A \mathbf x = \mathbf y$ cu $\lVert x \rVert \le \beta$ pentru alese în mod arbitrar $\mathbf y$. Putem recupera un fel de trapă pentru $\mathbf A$ care ne permite să calculăm o preimagine $\mathbf x'$ de o întâmplare $\mathbf y'$ asta nu este interogat oracolului, cu o probabilitate deloc neglijabilă?

O încercare evidentă este de a căuta $\mathbf A \mathbf x = \mathbf 0$ pentru a încerca să recupereze un set „scurt” de rang complet $\mathbf S$ astfel încât $\mathbf A \mathbf S = \mathbf 0$. Dar asta $\mathbf S$ nu pare suficient de scurt pentru a calcula soluții de lungime $\le \beta$. Putem încerca reducerea latice. Dar nu știu care este reducerea rețelei de ultimă generație pentru această problemă care încearcă să obțină o bază mai scurtă dintr-o bază deja scurtă.

  1. [GPV] https://eprint.iacr.org/2007/432
  2. [MP] https://eprint.iacr.org/2011/501
67
0 + 0
Puncte:2
Chris Peikert avatar Crypto
drapel in
Chris Peikert

Ideea pe care o descrieți (aproape) funcționează, dar după cum ați observat, „calitatea” trapei rezultate este ceva mai proastă decât ceea ce se pare că avem nevoie pentru a genera preimagini de normă. $\leq \beta$. Cu toate acestea, calitatea este suficient de bun pentru a genera preimagini de normă, să zicem, $\leq \beta \sqrt{m}$. Acest lucru poate fi suficient pentru aplicații dacă parametrii sunt configurați corect.

De exemplu, această idee este elaborată în mod formal și folosită pentru „delegarea” trapelor în hârtia CHKPâ10 „arbori bonsai” și, de asemenea, în [MP] pentru stilul său de trapă.

Nu se știe dacă ceea ce ați întrebat se poate face fără nicio pierdere de calitate, dar dacă da, ar fi foarte surprinzător; Cred că majoritatea experților nu s-ar aștepta să fie posibil.

Pentru ca reducerea rețelei să funcționeze în scopul declarat, ar dori să se reducă vectorii de normă dați $< \beta$ în vectori de normă $< \beta/ \sqrt{m}$ sau așa. Aceasta pare a fi o problemă foarte grea. Într-adevăr, chiar și doar înjumătăţirea lungimile unor vectori dați pare grea, din motivul intuitiv că am putea apoi să înjumătățim din nou și din nou, până când procedura a încetat să funcționeze, oferindu-ne un vector de rețea aproape cel mai scurt. De fapt, așa funcționează unii algoritmi (în timp exponențial) cu cel mai scurt vector, prin înjumătățire iterativă.

0 + 0
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.