Nu. Nu numai că nu există o generic mod de a construi un criptosistem bazat pe problema de decizie, nu există o singură problemă de decizie cunoscută care:
- este NP-Complet și
- putem construi criptografie din
„Orice criptografie” poate părea oarecum vagă, dar poate fi specifică destul de ușor --- majoritatea primitivelor cu cheie simetrică (Funcții unidirecționale, Funcții/Generatoare pseudorandom și funcții imprevizibile) sunt cunoscute ca fiind echivalent, în sensul că dacă ai unul (să zicem un OWF), le poți construi cu ușurință pe celelalte și invers.
De ce nu a existat criptografie construită din această presupunere? Un motiv de bază este „teorema trivială” care:
Dacă există un securizat (OWF/PRG/PRF/UF), atunci $P\neq NP$
Acest lucru se datorează faptului că pentru orice noțiune rezonabilă de „securitate”, problema spargerii unui OWF/PRG/PRF/UF este:
- Cu ușurință în NP („ghiciți” cheia secretă, apoi indiferent de noțiunea de securitate, se trivializează)
- Nu în P (altfel un adversar eficient l-ar putea sparge, deci nu ar fi „sigur”).
Dincolo de asta, există întrebarea (conexă) a
Cum pot folosi cunoștințele despre o anumită problemă dificilă pentru a construi criptografie?
Răspunsul este oarecum complex. Dacă puteți construi o primitivă criptografică standard (un PRG/PRF/OWF/UF sau o trapdoor OWF), atunci lucrurile devin foarte ușor foarte repede.
Dincolo de asta, aș sublinia că, dacă puteți construi „primitive standard” care sunt „omomorfe”, lucrurile devin, de asemenea, destul de simple.
Dar povestea generală este încă în curs de elaborare --- criptarea bazată pe rețea a fost propusă pentru prima dată acum 25 de ani, dar a durat până acum aproximativ un deceniu pentru ca semnăturile bazate pe zăbrele să fie dezvoltate.
Aceasta înseamnă că a ști cum să dezvolte criptarea (cu cheie publică) nu a condus la semnături „gratuit” (în ciuda faptului că PKE era un „primitiv mai greu de construit” într-un anumit sens formal).
S-au înregistrat unele progrese în înțelegerea ce construcții generice se obțin din construcția anumitor primitive (așa face lucrarea pe care am legat-o), dar totul este destul de recent.
