Exposé de Leonid Reyzin lors du colloque Paris Crypto Day organisé par le département informatique de l'ENS.
The key derivation function scrypt (Percival, 2009) is defined as the result of n steps, where each step consists of selecting one or two previously computed values (the selection depends on the values themselves) and hashing them. It is conjectured that this function is memory-hard.
We show that indeed scrypt is maximally memory-hard in the parallel random oracle model. Specifically, we show that the product of memory and time used during the computation of scrypt must be Theta(n^2). Moreover, even if the amount of memory used fluctuates during the computation, we show that the sum of memory usage over time (a.k.a. “cumulative memory complexity” introduced by Alwen and Serbinenko in 2015) is Theta(n^2). This suggests that computation of multiple instances of scrypt in cannot be improved via amortization. Our result holds even if the adversary is allowed to make an unlimited number of parallel random oracle queries at each step.
Previous work (Alwen, Chen, Kamath, Kolmogorov, Pietrzak, Tessaro 2016) showed a lowerbounds of Omega( n^2 / log^2 n) on the memory complexity of scrypt in more restricted models, where the adversary was assumed to store only random oracle outputs or specific functions of them. Our result improves the bound quantitatively by eliminating the log^2 n factor and qualitatively by allowing arbitrary storage by the adversary.
Joint work with Joel Alwen, Jeremiah Blocki, and Krzysztof Pietrzak.
Catégories: Paris Crypto Day
Mot-clés : sécurité, Code, cryptographie, cryptage, clé, système informatique
Voir aussi
|
|
Université de Boston
Professeur d'informatique
Plus sur cet auteur
Voir la fiche de l'auteur
Cursus :
Leonid Reyzin est professeur et chercheur en informatique au Collège des Arts et des Sciences de l'Université de Boston. Son principal domaine de recherche est la cryptographie. Il est membre du groupe de sécurité BU.
Cliquer ICI pour fermerDernière mise à jour : 03/11/2016
Tous droits réservés
@ 2011 ENS