înregistrare Logare
Puncte:4
a196884 avatar Crypto

Criptografie bazată pe probleme #P-complete

drapel cn
a196884

Există exemple de schemă criptografică bazată pe (o formă de caz mediu a) o problemă #P-completă?

156
0 + 0
ckamath avatar
drapel ag
ckamath
Nu știm cum să ne bazăm criptografia (de exemplu, funcții unidirecționale) chiar și pe completitatea NP (și există bariere cunoscute în acest sens), cu atât mai puțin pe completitatea #P.
0
Răspunde
ckamath avatar
drapel ag
ckamath
De asemenea, #P are o reducere a cazului de la cel mai rău caz la mediu (deci se poate la fel de bine presupune că duritatea medie a cazului).
0
Răspunde
Puncte:2
ckamath avatar Crypto
drapel ag
ckamath

Nu știm cum să ne bazăm nici măcar pe criptografie $\mathbf{NP}$-completitudine darămite $\#\mathbf{P}$-completitudine. Mai mult decât atât, există bariere cunoscute pentru bazarea criptografiei $\mathbf{NP}$-completitudine: [AGGM,BT], precum și [Capitolul 7, B].

Acestea fiind spuse, atunci cineva este dispus să facă ipoteze suplimentare $\#\mathbf{P}$-duritatea poate fi utilă: de exemplu, în [CHK+], se arată că în model aleator-oracol, duritatea de $\#SAT$ (care este complet pentru $\#\mathbf{P}$) poate da distribuții dure ale lui Nash, problema calculului Echilibru Nash (de exemplu, jocuri cu doi jucători).

[AGGM]: Akavia, Goldreich, Goldwasser și Moshkovitz, Pe baza funcțiilor unidirecționale pe duritatea NP, STOC 2006

[B]: Brzuszka, Pe bazele schimbului de chei, teză de doctorat, 2013

[BT]: Bogdanov și Trevisan, Reduceri de la cel mai rău caz la mediu pentru problemele NP, FOCS 2003

[CHK+]: Choudhuri et al, Găsirea unui echilibru Nash nu este mai ușor decât spargerea Fiat-Shamir, STOC 2019

0 + 0
a196884 avatar
drapel cn
a196884
Mulțumesc - răspuns util! În special al doilea paragraf - am avut în vedere ceva de genul unui echivalent #P-complet al de ex. această întrebare https://crypto.stackexchange.com/questions/55724/hardness-of-sis-and-its-reduction-to-an-np-complete-problem. Duritatea lui Nash este exact genul de exemplu pe care îl căutam.
0
Răspunde
Puncte:0
Habib avatar Crypto
drapel es
Habib

Actualizare: următorul răspuns nu acoperă întrebarea inițială. Este rezultatul confuziei p-complet cu #p-complet.

Primul algoritm criptografic cu cheie publică s-a bazat pe o problemă p-complete. Astăzi este cunoscut ca Merkle Puzzle. În linii mari, complexitatea schimbului de chei pentru părțile care primesc și trimite este $\mathcal{O}(n)$ în timp ce complexitatea unui atac de succes este $\mathcal{O}(n^2)$.

Deși în criptografia modernă nu mai este considerată sigură, ideea lui Merkle a schimbat totul în criptografie.

0 + 0
a196884 avatar
drapel cn
a196884
Interesant! Dar nu cred că acel exemplu este în #P.
0
Răspunde
Habib avatar
drapel es
Habib
Aceasta a fost cu siguranță greșeala mea. P-complet și #p-complet confuz.
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.