De ce presupunem că f este o funcție polinomială sau polinom în timp? Care este intuiția din spatele acestui lucru?
Am încredere că sunteți deja familiarizați cu de ce folosim timpul polinomial ca linie de bază pentru esențial toată criptografia (verificați comentariile lui Kelalaka). Pe scurt, există nenumărate motive pentru care credem că acesta este un model rezonabil de solid pentru ceea ce numim intuitiv „calcul eficient”.Aici, în contextul MPC, nu este diferit: dorim să ne putem concentra pe calcule care sunt eficiente pentru a fi efectuate.
asta restricționează tipurile de funcții pe care le putem replica cu ajutorul protocoalelor, nu-i așa? De ce presupunem că aceasta este singura familie de funcții pe care protocoalele o pot imita? Această familie de funcții restrânge problema și la funcțiile polinomiale? Poate această presupunere
Nu sunt familiarizat cu formularea exactă din aceste lucrări, dar de obicei, ori de câte ori vă referiți la funcții cu intrare/ieșire nemărginită, atunci vă gândiți cu adevărat la acestea care sunt încă calculabile în timp polinomial în ceea ce privește lungimea de intrare. Încă o dată, acest lucru se datorează faptului că modelăm participanții la protocol ca mașini polinomiale în timp și ne-am dori ca ei să poată termina calculul.
în plus, există noțiuni de securitate care se bazează pe presupunerea că adversarul este delimitat din punct de vedere computațional. De exemplu, există protocoale a căror securitate se bazează pe incapacitatea unui adversar de a factoriza un număr mare. Acest lucru este posibil, desigur, având suficient timp de calcul pentru a încerca toți factorii primi posibili, dar un adversar în timp polinomial nu este capabil să facă acest lucru.
Cu toate acestea, există și alte noțiuni în contextul calculului multipartit securizat în care într-adevăr putem tolera adversarii care rulează în timp superpolinom. Protocoale cu perfect și statistic securitate (care primesc termenul umbrelă de securitatea teoretică a informațiilor) sunt concepute astfel încât niciun adversar, indiferent de numărul de resurse de calcul sau de timpul de rulare, nu poate sparge securitatea protocolului.
Având în vedere acest lucru, în principiu, am putea permite tuturor părților (nu doar adversarului) să alerge în timp superpolinom, dar atunci întrebarea devine ce se câștigă cu adevărat făcând acest lucru. Practic, nu mă pot gândi la funcții nepolinomiale semnificative pe care am dori să le calculăm.
