NP este ansamblul problemelor de decizie care sunt verificabil eficient. Având un exemplu $x$ a problemei de decizie, există o scurtă „dovadă” $w$ asta, dată fiind perechea $(x, w)$, se poate verifica eficient asta $x$ este adevarat.
conNP este ansamblul problemelor de decizie care sunt refutabil eficient. Având un exemplu $x$ a problemei de decizie, există o scurtă „dis-proof” $w$ asta, dată fiind perechea $(x, w)$, se poate verifica eficient asta $x$ este fals.
Pentru toate schemele de criptare cunoscute cu chei publice, cheile publice formează un set NP.
Ce inseamna asta?
Dată o cheie publică $pk$, există câteva informații suplimentare $sk$ (cheia secretă) astfel încât să se poată verifica eficient asta $pk$ este o cheie publică în raport cu cheia secretă $sk$.
De exemplu
pentru RSA, $N = pq$. Având în vedere unele $N'$ care poate lua sau nu această formă, putem verifica eficient prin intermediul martorului $(p, q)$.
pentru ipotezele de tip DLOG, având în vedere unele $(g, g^s)$, putem verifica în mod similar în mod eficient că $g^s$ ia această formă prin intermediul martorului $s$
pentru schemele bazate pe zăbrele/cod, având în vedere unele $(A, As + e)$, putem verifica eficient asta $(Ca + e)$ ia această formă prin intermediul martorului $(s, e)$.
Toate acestea înseamnă că, având în vedere cheia secretă a unor PKE, este de obicei destul de ușor să verificați că cheia publică este structurată corect (și nu doar un element aleatoriu).
Acum, o cheie publică ar fi într-un set conp dacă, având în vedere niște "$pk$" acesta este nu o cheie publică (și în schimb este pur și simplu un „element aleatoriu”), se poate verifica eficient acest lucru.
De exemplu, pentru RSA, dacă cineva vă oferă $N$ acea nu poti fi scris ca $N = pq$, puteți verifica eficient acest lucru printr-o factorizare completă a $N = \prod_i p_i^{e_i}$. $((p_1, e_1),\dots,(p_k,e_k))$ de aceea serveste drept martor la $N$ nu fiind o cheie publică RSA, iar în acest sens cheile publice RSA sunt atât un set NP cât și un set coNP.
Pretenția acelei secțiuni a lucrării este că condiția prealabilă
criptarea este deterministă și setul de chei publice formează un set coNP.
este restrictiv. Eu personal consider prima parte a acestui lucru ca fiind mai restrictivă decât a doua.
De exemplu, mi se pare probabil că în toate cele trei exemple pe care le-am menționat mai sus, cheile publice formează un set conp.
În primele două exemple este evident, iar în al treilea cred că o reducere a bazei suficient de puternică ar putea/ar trebui să funcționeze ca martor, în special dacă $B$ este o bază suficient de scurtă pentru dualitatea de $\mathcal{L}(A)$, atunci $(BAs + Be)$ va fi un vector neobișnuit de scurt pentru o probă „adevărată LWE”, dar va fi uniform aleatoriu pentru o probă aleatoare, de ex. va fi martor coNP.
