Avantaj (criptologie)

În criptologie, noțiunea de avantaj măsoară capacitatea unui adversar de a distinge între un obiect criptografic real și un model idealizat (sau mai general, între două situații). În esență, avantajul este o măsură a modului în care „mai bine decât întâmplarea” face adversarul în acest exercițiu. Noțiunea a fost introdusă în 1982 de criptologii Shafi Goldwasser și Silvio Micali pentru a defini formal securitatea semantică a criptării cheii publice.

Avantajul depinde de jocul de securitate luat în considerare, de puterile adversarului (în general formalizat prin intermediul oracolelor), de clasa adversarilor studiați și, eventual, de alți parametri. În general, încercăm să dovedim că beneficiul este o funcție semnificativă a setării de securitate , care asigură faptul că obiectul criptografic real și modelul său idealizat nu pot fi distinse de un atacator.

Mai multe tehnici clasice de a face posibilă obținerea unui legat pe avantajul într - un anumit joc, cum ar fi argumente hibride sau coeficienți H .

Definiție

Luați în considerare o clasă de adversari. Pentru toate , observăm adversarul cu acces la oracole . ${\ mathcal A}$ ${\ displaystyle A \ in {\ mathcal {A}}}$ ${\ displaystyle A ^ {O_ {1}, O_ {2}, \ dotsc}}$ ${\ displaystyle O_ {1}, O_ {2}, \ dotsc}$

În plus, adversarului i se oferă acces fie la (un oracol al) adevăratei funcții criptografice de interes, fie la (un oracol al) versiunii idealizate a acestuia. Obiectivul adversarului este să facă distincția între aceste două situații și să returneze 1 în primul caz și 0 în al doilea. Apoi definim avantajul:

LAdv(LA)=maxLA∈LA|Relatii cu publicul[LAO1,...(F)=1]-Relatii cu publicul[LAO1,...(Feud)=1]|{\ displaystyle {\ mathsf {Adv}} ({\ mathcal {A}}) = \ max _ {A \ în {\ mathcal {A}}} \ left | \ Pr \ left [A ^ {O_ {1} , \ dotsc} (F) = 1 \ right] - \ Pr \ left [A ^ {O_ {1}, \ dotsc} (F _ {\ mathrm {id}}) = 1 \ right] \ right |}

{\ displaystyle {\ mathsf {Adv}} ({\ mathcal {A}}) = \ max _ {A \ în {\ mathcal {A}}} \ left | \ Pr \ left [A ^ {O_ {1} , \ dotsc} (F) = 1 \ right] - \ Pr \ left [A ^ {O_ {1}, \ dotsc} (F _ {\ mathrm {id}}) = 1 \ right] \ right |}

unde (resp. ) este funcția reală (resp. ideală) considerată. Alternativ, putem defini avantajul în termeni de distribuții (sau jocuri):

F

{\ displaystyle F _ {\ mathrm {id}}}

LAdv(LA)=maxLA∈LA|Relatii cu publiculX∼D[LAO1,...(X)=1]-Relatii cu publiculX∼D′[LAO1,...(X)=1]|{\ displaystyle {\ mathsf {Adv}} ({\ mathcal {A}}) = \ max _ {A \ în {\ mathcal {A}}} \ left | \ Pr _ {x \ sim D} \ left [ A ^ {O_ {1}, \ dotsc} (x) = 1 \ right] - \ Pr _ {x \ sim D '} \ left [A ^ {O_ {1}, \ dotsc} (x) = 1 \ dreapta] \ dreapta |}

{\ displaystyle {\ mathsf {Adv}} ({\ mathcal {A}}) = \ max _ {A \ în {\ mathcal {A}}} \ left | \ Pr _ {x \ sim D} \ left [ A ^ {O_ {1}, \ dotsc} (x) = 1 \ right] - \ Pr _ {x \ sim D '} \ left [A ^ {O_ {1}, \ dotsc} (x) = 1 \ dreapta] \ dreapta |}

unde de data aceasta măsurăm capacitatea adversarului de a distinge între o variabilă distribuită conform unei legi D și o variabilă distribuită conform unei legi D ' .

Definiția poate fi ajustată prin specificarea oracolelor sau a condițiilor de succes, pentru a se specializa în diferite obiecte pseudo-aleatorii ( PRNG , PRF , PRP ...), oferind conceptele de securitate corespunzătoare ( securitate semantică etc.). În cazul general, beneficiul depinde de numărul de cereri adresate oracolelor . ${\ displaystyle q_ {1}, q_ {2}, \ dotsc}$

Exemple

Extragere părtinitoare

Luați în considerare o monedă , asimilată unei variabile aleatorii conform unei legi a probabilității Bernoulli p . Modelul ideal corespunzător este o variabilă aleatorie a probabilității 1/2, iar avantajul contradictoriu în acest context este atunci . Cu alte cuvinte, deoarece nu este neglijabil , un adversar va putea amplifica decalajul repetând experimentul și distingând dacă are de-a face cu o piesă reală sau ideală. ${\ displaystyle {\ mathsf {Adv}} ({\ mathcal {A}}) = | p-1/2 |}$ ${\ displaystyle p-1/2}$

Argument hibrid

Într-un argument hibrid , definim o secvență de jocuri în care înlocuim treptat un obiect real cu un model idealizat. Atunci când avantajul dintre două astfel de jocuri este neglijabil, este posibil, astfel, încetul cu încetul, să reducem securitatea unui sistem real complex la cea a unui sistem ideal.

Funcție pseudo-aleatorie

Considerăm o familie de funcții F luând ca intrare o cheie k și o valoare x și returnând un șir y de dimensiune fixă. Modelul ideal luat în considerare este cel al unei funcții aleatorii g , iar adversarul trebuie să facă distincția între funcția aleatorie și o funcție a cărei cheie a fost trasă uniform la întâmplare între toate tastele posibile. Aceasta corespunde avantajului: $f \ în F$

LAdvPRF(LA)=|Relatii cu publiculk∼K,X∼X[LA(f(k,X))=1]-Relatii cu publiculX∈X[LA(g(X))=1]|{\ displaystyle {\ mathsf {Adv}} _ {\ mathrm {PRF}} ({\ mathcal {A}}) = \ left | \ Pr _ {k \ sim K, x \ sim X} [{\ mathcal { A}} (f (k, x)) = 1] - \ Pr _ {x \ în X} [{\ mathcal {A}} (g (x)) = 1] \ right |}

{\ displaystyle {\ mathsf {Adv}} _ {\ mathrm {PRF}} ({\ mathcal {A}}) = \ left | \ Pr _ {k \ sim K, x \ sim X} [{\ mathcal { A}} (f (k, x)) = 1] - \ Pr _ {x \ în X} [{\ mathcal {A}} (g (x)) = 1] \ right |}

când acest avantaj este neglijabil , spunem că funcțiile F sunt pseudo-aleatorii .

Note și referințe

Note

Ca regulă generală, considerăm mașinile probabilistice Turing , eventual dotate cu un lanț de referință , care sunt cele mai relevante modele din criptologie.
În mod natural, rolul lui 1 și 0 este simetric aici, iar alegerea funcției care corespunde cu 1 nu influențează definiția.

Referințe

(în) Phillip Rogaway , „On the Role Definitions in Cryptography and Beyond” , în Advances in Computer Science - ASIAN 2004. Procesul decizional la nivel superior , Springer Berlin Heidelberg,2004( ISBN 9783540240877 , DOI 10.1007 / 978-3-540-30502-6_2 , citit online ) , p. 13–32
(în) Shafi Goldwasser și Silvio Micali , „ Criptare probabilistică și cum să joci mintea pokerului păstrând secret toate informațiile părtinitoare ” , STOC '82 Procesul celui de-al paisprezecelea simpozion anual ACM este Theory of Computing , ACM,5 mai 1982, p. 365–377 ( ISBN 0897910702 , DOI 10.1145 / 800070.802212 , citit online , accesat la 28 august 2018 )
(în) David Wu, „ Introducere în criptografie ” pe crypto.stanford.edu
(în) Mihir Bellare, „ Criptografie modernă ” pe cseweb.ucsd.edu (accesat la 28 august 2018 )
(în) Jonathan Katz și Yehuda Lindell, Introducere în criptografia modernă: principii și protocoale , Chapman & Hall / CRC,2008, 552 p. ( ISBN 978-1-58488-551-1 și 1584885513 , OCLC 137325053 , citit online )
(în) Mihir Bellare, „ Funcții pseudo-aleatorii ” pe cseweb.ucsd.edu