Persistența semantică

Un criptosistem sigur din punct de vedere semantic în criptografie este un criptosistem care nu permite nicio scurgere de informații semnificative despre textul simplu original din textul cifrat . Să luăm orice algoritm probabilistic din clasa PP , a cărui intrare în primul caz este textul cifrat al unui mesaj aleator și lungimea acestui mesaj, iar în al doilea caz doar lungimea mesajului. Dacă diferența dintre probabilitățile de obținere a unor informații fiabile despre mesajul original în primul și al doilea caz este neglijabilă, atunci criptosistemul care a produs această criptare este considerat semantic sigur. [1] În ceea ce privește complexitatea computațională , acest concept este analog cu un cifr Shannon absolut sigur . Un cifru perfect securizat implică faptul că nicio informație despre mesajul original nu poate fi obținută deloc, în timp ce securitatea semantică înseamnă că nicio informație despre mesajul original găsit în textul cifrat nu poate fi folosită pentru a decripta orice fragment al mesajului. [2] [3] :378–381 $m$

Istorie

Conceptul de putere semantică a fost introdus în criptografie de Goldwasser și Micali în 1982. [1] Cu toate acestea, definiția propusă inițial de ei nu a oferit o estimare a puterii criptosistemelor reale. Mai târziu, Goldwasser și Micali au arătat că securitatea semantică este echivalentă cu indistinguirea textului cifrat pentru atacurile cu text simplu . [4] Această definiție a puterii semantice este mai comună, deoarece ajută la evaluarea puterii criptosistemelor utilizate.

Criptografia simetrică

În cazul criptosistemelor simetrice , adversarul nu ar trebui să poată afla nicio informație despre textul simplu din textul cifrat. Aceasta înseamnă că adversarul, având două texte clare și două texte cifrate corespondente, nu poate determina exact ce text cifrat corespunde cărui text simplu.

Criptografia cu cheie publică

Se spune că un criptosistem cu cheie publică este sigur din punct de vedere semantic dacă un adversar, aflat în posesia textului cifrat și a cheii publice, nu poate obține nicio informație semnificativă despre textul simplu original. Securitatea semantică ia în considerare doar cazurile de atacuri criptopasive, de exemplu, atunci când un criptoanalist poate observa doar textele cifrate transmise și pot genera propriile texte cifrate folosind cheia publică. Spre deosebire de alte noțiuni de securitate, securitatea semantică nu ia în considerare atacurile de criptare alese , în care criptoanalistul este capabil să decripteze unele texte criptate alese, iar multe scheme de criptare puternice din punct de vedere semantic sunt considerate slabe împotriva acestor tipuri de atacuri. Prin urmare, puterea semantică nu poate fi considerată o condiție suficientă pentru puterea unei scheme de criptare de uz general.

Indistinguirea textului cifrat pentru atacurile bazate pe textul simplu ales este de obicei determinată de următorul experiment: [5]

Se generează o pereche de chei aleatoare . $(pk,sk)$
Un adversar, legat de timp polinomial, primește o cheie publică pe care o poate folosi pentru a genera orice număr de texte cifrate (în limitele de timp polinomiale). $pk$
Adversarul generează două mesaje de aceeași lungime și le trimite expeditorului împreună cu cheia publică. $m_{0}$ $m_1$
Expeditorul selectează unul dintre mesaje la întâmplare, îl criptează cu cheia publică primită și trimite textul cifrat rezultat adversarului. $c$

Criptosistemul luat în considerare are proprietatea de indistingere a textului cifrat (și, prin urmare, este rezistent din punct de vedere semantic la atacurile cu text simplu) dacă adversarul nu poate determina care dintre cele două mesaje a fost ales de expeditor cu o probabilitate semnificativ mai mare decât (probabilitatea de ghicire aleatorie) . $1/2$

Deoarece adversarul deține cheia publică, o schemă sigură semantic, prin definiție, trebuie să fie probabilistică, adică să aibă o componentă aleatorie. În caz contrar, adversarul poate, folosind cheia publică , să calculeze pur și simplu textele cifrate ale mesajelor și să le compare cu textul cifrat returnat și să determine cu succes alegerea expeditorului. $pk$ $m_{0}$ $m_1$ $c$

Exemple de algoritmi siguri din punct de vedere semantic sunt criptosistemul Goldwasser-Micali , schema ElGamal și criptosistemul Peye . Aceste scheme sunt considerate a fi dovedit sigure , deoarece în fiecare caz demonstrarea securității semantice poate fi redusă la o problemă matematică insolubilă. Algoritmii fragili din punct de vedere semantic, cum ar fi RSA , pot fi securizați din punct de vedere semantic folosind scheme de umplutură (de exemplu , OAEP ).

Note

↑ 1 2 S. Goldwasser și S. Micali , Probabilistic encryption & how to play mental poker keeping secret all partial information Arhivat la 31 martie 2020 la Wayback Machine , Annual ACM Symposium on Theory of Computing, 1982.
↑ Shannon, Claude. Teoria comunicării sistemelor de secretizare // Bell System Technical Journal : jurnal. - 1949. - Vol. 28 , nr. 4 . - P. 656-715 . - doi : 10.1002/j.1538-7305.1949.tb00928.x .
↑ Goldreich, Oded. Fundamentele Criptografiei: Volumul 2, Aplicații de bază. Vol. 2. Cambridge University Press, 2004.
↑ S. Goldwasser și S. Micali , Probabilistic encryption . Journal of Computer and System Sciences, 28:270-299, 1984.
↑ Katz, Jonathan; Lindell, Yehuda. Introducere în criptografia modernă : principii și protocoale . — Chapman și Hall/CRC, 2007. Arhivat 8 martie 2017 la Wayback Machine