înregistrare Logare
Puncte:3
jacobi_matrix avatar Crypto

PPT-uri uniforme și neuniforme

drapel in
jacobi_matrix

În timp ce citea hârtie

Am dat peste cazul în care era necesar să precizez dacă autorii presupuneau atacatori uniformi sau neuniformi. Din câte știu eu, PPT-uri neuniforme sunt practic o secvență de PPT-uri, deci $\mathcal{A}=\{\mathcal{A}_1,\mathcal{A}_2,\dots,\mathcal{A}_n\}$, și la intrare $x$ de mărime $|x| = \lambda$, $\mathcal{A}_\lambda$ se numește. De ce este acest model „mai puternic” decât cel uniform? Nu s-a putut ataca anunțul $\mathcal{A}$ doar încorporați toți ceilalți atacatori în propria sa descriere și invocați-o pe cea potrivită? Există probleme pe care știm să le rezolvăm în modelul uniform, dar nu (dacă nu cu garanții mai slabe) în modelul neuniform?

79
1 + 0
Puncte:1
Mark avatar Crypto
drapel ng
Mark

Luați în considerare o enumerare unară a tuturor mașinilor Turing, de ex. o mașină $M$ este reprezentat de $1^{\lambda_M}$ pentru un număr întreg unic $\lambda_M$. Problema opririi este incalculabilă, chiar și în această reprezentare „rară”. Dar este calculabil neuniform, ca fiecare mașină Turing $M$ fie se oprește, fie nu se oprește și putem „codifica” decizia în fiecare mașină de turnat $A_{\lambda_M}$.

Dacă am putea „genera uniform“ $A_i$'s, adică generează-le eficient doar din descrierea $i$, ai avea dreptate. În exemplul de mai sus, nu poți, deoarece nu știi dacă fiecare mașină Turing $M$ se oprește.

0 + 5
drapel us
Mikero
O altă modalitate de a vedea că algoritmii neuniformi pot face lucruri pe care algoritmii uniformi nu le pot face: există nenumărați mulți algoritmi neuniformi, dar numarabil mulți algoritmi uniformi.
1
Răspunde
jacobi_matrix avatar
drapel in
jacobi_matrix
Vă mulțumesc pentru răspunsuri. Mă întrebam dacă știm probleme practice care devin mai ușoare în modelul neuniform. Reformulare, cum poate o schemă de criptare/angajament/semnătură... să ofere un anumit nivel de securitate atunci când presupunem adversari uniformi, dar niveluri mai scăzute de securitate împotriva adversarilor neuniformi, dacă putem construi un adversar uniform codificându-i pe ceilalți în el propria descriere (și încă au o dimensiune a descrierii polinomului)
0
Răspunde
Mark avatar
drapel ng
Mark
@jacobi_matrix Consultați secțiunea 4 din [o altă privire asupra etanșeității 2](https://eprint.iacr.org/2016/360.pdf) pentru o discuție despre ipotezele de duritate neuniforme. Este demn de menționat că o noțiune oarecum înrudită de atacuri de „preprocesare” (unde se primește sfaturi specifice unei instanțe) are o serie de exemple în care acestea ajută (și pot duce la atacuri practice), de exemplu [atacul logjam]( https://en.wikipedia.org/wiki/Logjam_(computer_security)), sau multe probleme în criptografia bazată pe zăbrele (deși majoritatea criptosistemelor cu zăbrele generează instanțe noi de fiecare dată, limitând pericolul de precomp
1
Răspunde
Mark avatar
drapel ng
Mark
@jacobi_matrix problema este că nu puteți construi un adversar uniform codificându-i pe ceilalți în descrierea sa, deoarece generarea unui $A_i$ arbitrar ar putea să nu fie calculată în mod eficient (sau chiar deloc calculabilă, de exemplu „Problema de oprire rară” algoritm neuniform dat în răspunsul meu). Mai mult decât atât, nu le poți „pastra” pe toate în adversarul uniform, deoarece adversarul uniform ar avea o descriere prea mare.
1
Răspunde
jacobi_matrix avatar
drapel in
jacobi_matrix
Perfect! Secțiunea pe care ați conectat-o ​​și exemplul de atac logjam au făcut treaba. Problema a fost că am crezut (în mod greșit, evident) că șirul de sfaturi trebuie să fie dimensiunea de intrare în sine (de exemplu, codificată în unară). Multumesc din nou .
0
Răspunde
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.