înregistrare Logare
Puncte:2
C.S. avatar Crypto

Rezolvarea $\mathsf{SVP}_{\gamma}$ în cel mai rău caz

drapel in
C.S.

Ce înseamnă să rezolvi $\mathsf{SVP}_{\gamma}$ in cel mai rau caz?

Înseamnă că problema poate fi rezolvată pentru orice zăbrele pe care o alegem?

52
0 + 0
lwe
Puncte:3
avatar Crypto
drapel in
Stanley

Rezolvarea $\text{SVP}$ în cel mai rău caz înseamnă rezolvarea unei „mai grele” instanțe de $\text{SVP}$. Acest lucru nu este ceea ce ne dorim pentru criptografie, deoarece vrem ca problemele să fie greu de rezolvat in medie (caz mediu). Probleme fundamentale precum $\text{SIS}$ și $\text{LWE}$ sunt probleme medii, în funcție de duritatea problemelor din cel mai rău caz, cum ar fi $\text{SVP}$, adică dacă $\text{SVP}$ atunci este greu în cel mai rău caz $\text{LWE/SIS}$ sunt grele în medie.

Recomand să citești „M. Ajitai. Generarea de instanțe dure de probleme de zăbrele' pentru mai multe informații despre aceasta.

0 + 0
Don Freecs avatar
drapel sz
Don Freecs
poti explica mai multe, de ce cazul mediu este favorabil in criptografie??
0
Răspunde
Mark avatar
drapel ng
Mark
@DonFreecs este doar ceea ce apare.Când eșantionați aleatoriu cheile, de multe ori eșantionați (implicit) aleatoriu o instanță a unei probleme de bază, așa că „spărgerea” lucrurilor devine o problemă de caz obișnuit. Acestea fiind spuse, *exact ce* distribuție pentru a eșantiona poate fi uneori greu de determinat. Cea mai gravă reducere a cazurilor pe care oamenii le discută aici ajută la identificarea distribuției LWE ca fiind cea „corectă”.
1
Răspunde
Puncte:1
Don Freecs avatar Crypto
drapel sz
Don Freecs

din câte știu eu, rezolvarea unei probleme în cel mai rău caz duritatea înseamnă rezolvarea problemei pentru orice instanță dată (deci pentru orice distribuție de instanțe) pe de altă parte, rezolvarea unei probleme în caz mediu înseamnă rezolvarea acestei probleme pentru o distribuție dată...

"Corecteaza-ma te rog, ma insel"

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.