Multe dintre acestea sunt abordate în articol.În această setare, „adversarul” este un algoritm care poate evalua $f_n$ folosind mai puține resurse decât am sperat.
$S$ = complexitatea spatiului/memoriei adversarului. În această linie de lucru, $f_n$ este o funcție care face apeluri către un oracol aleatoriu $H : \{0,1\}^k \la \{0,1\}^k$, și $S$ este utilizarea spațiului (în cel mai rău caz) de către adversar, măsurată în $k$-bit „blocuri”.
$T$ = complexitatea temporală a adversarului. De obicei, măsurat în numărul de apeluri către $H$. În unele modele, adversarului i se permite să facă apeluri paralele către $H$ gratuit, deci $T$ este numărul de „runde succesive” de apeluri către $H$.
$n$ = parametrul de duritate reglabil al funcției memory-hard. Mai mare $n$ crește efortul necesar pentru evaluarea funcției $f_n$ (și, în mod ideal, efortul se scalează pătratic în $n$). Partidele sincere ar trebui să aleagă pe cea mai mare $n$ astfel încât ei sunt dispuși să depună efortul de a evalua $f_n$.
Cât de bună este această definiție? ... Deci, cred că această definiție nu este suficient de strânsă pentru a ne arăta care KDF cu memorie este neapărat mai bun?
E adevărat că $n^2/1000$ este mult diferit de 1000$ n^2$, dar această definiție ar fi mulțumită cu funcțiile dure de memorie cu oricare dintre aceste niveluri de dificultate.
La momentul redactării acestei lucrări, cele mai multe funcții candidate de memorie dure erau asimptotic mult mai rău decât $\Theta(n^2)$.
Deci această definiție este destul de eficientă pentru a exclude mulți candidați răi.
Odată ce ai mulți candidați care satisfac asta asimptotic definiție, atunci puteți începe să vă faceți griji cu privire la factorii constanți.
O definiție mai bună a durității memoriei?
Da, această definiție ia în considerare doar cel mai rău utilizarea spațiului carcasei $S$.
Presupune $f_n$ este o funcție care într-adevăr necesită $n$ unități de memorie de evaluat - nu există nicio modalitate de a evalua $f_n$ fără să țină $n$ unități de memorie la un moment dat.
Acest lucru nu exclude posibilitatea ca $n$ unitățile de memorie sunt necesare doar pentru o fereastră de timp foarte scurtă.
Cu alte cuvinte, ar putea exista un algoritm pentru $f_n$ a cărui diagramă de utilizare a memoriei de-a lungul timpului arată astfel:
(imagini preluate de la Diapozitivele lui Leo Reyzin pe scrypt)
Dacă acest algoritm are maxim utilizarea spațiului $n$ și, de asemenea, utilizări $n$ timp, complexitatea sa ST este $\Omega(n^2)$.
Complexitatea ST este ca zona dreptunghiului albastru al casetei de delimitare din această imagine.
Dar această măsură a durității memoriei ascunde o anumită problemă.
Să presupunem că un adversar dorește să evalueze $f_n$ pe multe intrări diferite și programează în mod inteligent acele evaluări astfel:
Această strategie poate fi folosită pentru a evalua exemplul $f_n$ pe $n$ diferite intrări folosind numai $O(n)$ timp și $O(n)$ Memorie totala!
Deci, „costul ST” total pentru a evalua funcția $n$ ori este $O(n^2)$, ceea ce înseamnă că amortizat costul pe instanță este doar $O(n)$.
O modalitate mai bună de a clasifica duritatea memoriei unei funcții ar fi măsurarea zona de sub curbă mai degrabă decât zona casetei de delimitare.
Acesta este într-adevăr ceea ce se propune în lucrările ulterioare, unde metrica duritate-memorie este numită „complexitate cumulativă a memoriei”.
