nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Sustained Space Complexity

verfasst von : Joël Alwen, Jeremiah Blocki, Krzysztof Pietrzak

Erschienen in: Advances in Cryptology – EUROCRYPT 2018

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Memory-hard functions (MHF) are functions whose evaluation cost is dominated by memory cost. MHFs are egalitarian, in the sense that evaluating them on dedicated hardware (like FPGAs or ASICs) is not much cheaper than on off-the-shelf hardware (like x86 CPUs). MHFs have interesting cryptographic applications, most notably to password hashing and securing blockchains.

Alwen and Serbinenko [STOC’15] define the cumulative memory complexity (cmc) of a function as the sum (over all time-steps) of the amount of memory required to compute the function. They advocate that a good MHF must have high cmc. Unlike previous notions, cmc takes into account that dedicated hardware might exploit amortization and parallelism. Still, cmc has been critizised as insufficient, as it fails to capture possible time-memory trade-offs; as memory cost doesn’t scale linearly, functions with the same cmc could still have very different actual hardware cost.

In this work we address this problem, and introduce the notion of sustained-memory complexity, which requires that any algorithm evaluating the function must use a large amount of memory for many steps. We construct functions (in the parallel random oracle model) whose sustained-memory complexity is almost optimal: our function can be evaluated using n steps and \(O(n/\log (n))\) memory, in each step making one query to the (fixed-input length) random oracle, while any algorithm that can make arbitrary many parallel queries to the random oracle, still needs \(\varOmega (n/\log (n))\) memory for \(\varOmega (n)\) steps.

As has been done for various notions (including cmc) before, we reduce the task of constructing an MHFs with high sustained-memory complexity to proving pebbling lower bounds on DAGs. Our main technical contribution is the construction is a family of DAGs on n nodes with constant indegree with high “sustained-space complexity”, meaning that any parallel black-pebbling strategy requires \(\varOmega (n/\log (n))\) pebbles for at least \(\varOmega (n)\) steps.

Along the way we construct a family of maximally “depth-robust” DAGs with maximum indegree \(O(\log n)\), improving upon the construction of Mahmoody et al. [ITCS’13] which had maximum indegree \(O\left( \log ^2 n \cdot {{\mathsf {polylog}}} (\log n)\right) \).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Ouroboros Praos: An Adaptively-Secure, Semi-synchronous Proof-of-Stake Blockchain

Nächstes Kapitel Multi-Collision Resistant Hash Functions and Their Applications

Nur mit Berechtigung zugänglich

Recall that the naïve algorithm is sequential, so S must be in O(T) as in time T the algorithm cannot even touch more than O(T) memory.

We typically want a DAG G with \({\mathsf {indeg}} (G)=2\) because the compression function H which is used to label the graph typically maps 2w bit inputs to w bit outputs. In this case the labeling function would only be valid for graphs with maximum indegree two. If we used tricks such as Merkle-Damgard to build a new compression function G mapping \(\delta w\) bit inputs to w bit outputs then each pebbling step actually corresponds to \(\left( \delta -1\right) \) calls to the compression function H which means that each black pebbling step actually takes time \(\left( \delta -1\right) \) on a sequential computer with a single-core. As a consequence, by considering graphs of degree \(\delta \), we pay an additional factor \((\delta -1)\) in the gap between the naive and adversarial evaluation of the MHF.

Furthermore, even if we restrict our attention to pebblings which finish in time O(n) we still have \(\varPi _{ss}\left( G_n,f(n)\right) \le g(n)\) whenever \(f(n)g(n) \in \omega \left( \frac{n^2 \log \log n}{\log n}\right) \) and \({\mathsf {indeg}} (G_n)\in O(1)\). In particular, Alwen and Blocki [AB16] showed that for any \(G_n\) with \({\mathsf {indeg}} (G_n)\in O(1)\) then there is a pebbling \(P = (P_0,\ldots ,P_n) \in \varPi ^{\parallel }_{G_n}\) with \(\varPi ^{\parallel }_{cc}(P) \in O\left( \frac{n^2 \log \log n}{\log n}\right) \). By contrast, the generic pebbling [HPV77] of any DAG with \({\mathsf {indeg}} \in O(1)\) in space \(O\left( n/\log n\right) \) can take exponentially long.

Effectively this does for SMHFs what [AT17] did for MHFs.

To see this observe that if \(G_n^\epsilon \) is a \(\delta \)-local expander then \(G_n^\epsilon [\{1,\ldots ,i\}]\) is also a \(\delta \)-local expander. Therefore, Lemmas 5 and 6 imply that \(G_n^\epsilon [\{1,\ldots ,i\}]\) is (ai, bi)-depth robust for any \(a+b \le 1-\epsilon \). Since, \(H_i\) is a subgraph of \(G_n^\epsilon [\{1,\ldots ,i\}]\) it must be that \(H_i\) is \(\left( a\left| Good_i \right| ,\left( 1-a\right) \left| Good_i\right| -\epsilon i\right) \)-depth robust. Otherwise, we have a set \(S \subseteq V(H_i)\) of size \(a\left| Good_i \right| \) such that \({\mathsf {depth}} (H_i-S) < \left( 1-a\right) \left| Good_i \right| -\epsilon i\) which implies that \({\mathsf {depth}} (G_n^\epsilon [\{1,\ldots ,i\}] - S) \le i-|Good_i| + {\mathsf {depth}} (Good_i-S) < i -a|Good_i|-\epsilon i\) contradicting the depth-robustness of \(G_n^\epsilon [\{1,\ldots ,i\}]\).

[AB16]

Alwen, J., Blocki, J.: Efficiently computing data-independent memory-hard functions. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 241–271. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_9CrossRef

[AB17]

Alwen, J., Blocki, J.: Towards practical attacks on Argon2i and balloon hashing. In: Proceedings of the 2nd IEEE European Symposium on Security and Privacy (EuroS&P 2017), pp. 142–157. IEEE (2017). http://eprint.iacr.org/2016/759

[ABH17]

Alwen, J., Blocki, J., Harsha, B.: Practical graphs for optimal side-channel resistant memory-hard functions. In: ACM CCS 2017, pp. 1001–1017. ACM Press (2017)

[ABP17]

Alwen, J., Blocki, J., Pietrzak, K.: Depth-robust graphs and their cumulative memory complexity. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10212, pp. 3–32. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56617-7_1CrossRef

[ABP18]

Alwen, J., Blocki, J., Pietrzak, K.: Sustained space complexity. Cryptology ePrint Archive, Report 2018/147 (2018). https://eprint.iacr.org/2018/147

[ABW03]

Abadi, M., Burrows, M., Wobber, T.: Moderately hard, memory-bound functions. In: Proceedings of the Network and Distributed System Security Symposium, NDSS 2003, San Diego, California, USA (2003)

[ACP+17]

Alwen, J., Chen, B., Pietrzak, K., Reyzin, L., Tessaro, S.: Scrypt is maximally memory-hard. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10212, pp. 33–62. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56617-7_2CrossRef

[AdRNV17]

Alwen, J., de Rezende, S.F., Nordström, J., Vinyals, M.: Cumulative space in black-white pebbling and resolution. In: 8th Innovations in Theoretical Computer Science (ITCS) Conference, Berkeley, 9–11 January 2017

[AS15]

Alwen, J., Serbinenko, V.: High parallel complexity graphs and memory-hard functions. In: Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC 2015 (2015). http://eprint.iacr.org/2014/238

[AT17]

Alwen, J., Tackmann, B.: Moderately hard functions: definition, instantiations, and applications. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10677, pp. 493–526. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_17CrossRef

[BDK16]

Biryukov, A., Dinu, D., Khovratovich, D.: Argon2: new generation of memory-hard functions for password hashing and other applications. In: 2016 IEEE European Symposium on Security and Privacy (EuroS&P), pp. 292–302. IEEE (2016)

[BHZ18]

Blocki, J., Harsha, B., Zhou, S.: On the economics of offline password cracking. IEEE Secur. Priv. (2018, to appear)

[Can01]

Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 42nd Annual Symposium on Foundations of Computer Science, Las Vegas, Nevada, pp. 136–145. IEEE, October 2001

[Coo73]

Cook, S.A.: An observation on time-storage trade off. In: Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, STOC 1973, pp. 29–33. ACM, New York (1973)

[Cox16]

Cox, B.: Re: [Cfrg] Balloon-Hashing or Argon2i. CFRG Mailinglist, August 2016. https://www.ietf.org/mail-archive/web/cfrg/current/msg08426.html

[CP18]

Cohen, B., Pietrzak, K.: Simple proofs of sequential work. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part II. LNCS, vol. 10821, pp. 451–467. Springer, Cham (2018)

[CS76]

Cook, S., Sethi, R.: Storage requirements for deterministic polynomialtime recognizable languages. J. Comput. Syst. Sci. 13(1), 25–37 (1976)CrossRefMATH

[DGN03]

Dwork, C., Goldberg, A., Naor, M.: On memory-bound functions for fighting spam. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 426–444. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_25CrossRef

[EGS75]

Erdös, P., Graham, R.L., Szemerédi, E.: On sparse graphs with dense long paths. Technical report, Stanford, CA, USA (1975)

[GG81]

Gabber, O., Galil, Z.: Explicit constructions of linear-sized superconcentrators. J. Comput. Syst. Sci. 22(3), 407–420 (1981)MathSciNetCrossRefMATH

[HP70]

Hewitt, C.E., Paterson, M.S.: Record of the project MAC conference on concurrent systems and parallel computation. In: Comparative Schematology, pp. 119–127. ACM, New York (1970)

[HPV77]

Hopcroft, J., Paul, W., Valiant, L.: On time versus space. J. ACM 24(2), 332–337 (1977)MathSciNetCrossRefMATH

[Kal00]

Kaliski, B.: PKCS# 5: password-based cryptography specification version 2.0 (2000)

[MMV13]

Mahmoody, M., Moran, T., Vadhan, S.P.: Publicly verifiable proofs of sequential work. In: Kleinberg, R.D. (ed.) Innovations in Theoretical Computer Science, ITCS 2013, Berkeley, CA, USA, 9–12 January 2013, pp. 373–388. ACM (2013)

[MRH04]

Maurer, U., Renner, R., Holenstein, C.: Indifferentiability, impossibility results on reductions, and applications to the random Oracle methodology. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 21–39. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24638-1_2CrossRef

[Per09]

Percival, C.: Stronger key derivation via sequential memory-hard functions. In: BSDCan 2009 (2009)

[PHC]

Password hashing competition. https://password-hashing.net/

[PJ12]

Percival, C., Josefsson, S.: The scrypt password-based key derivation function (2012)

[PTC76]

Paul, W.J., Tarjan, R.E., Celoni, J.R.: Space bounds for a game on graphs. In: Proceedings of the Eighth Annual ACM Symposium on Theory of Computing, STOC 1976, pp. 149–160. ACM, New York (1976)

[RD16]

Ren, L., Devadas, S.: Proof of space from stacked expanders. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9985, pp. 262–285. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53641-4_11CrossRef

[RD17]

Ren, L., Devadas, S.: Bandwidth hard functions for ASIC resistance. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10677, pp. 466–492. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_16CrossRef

Titel: Sustained Space Complexity
verfasst von: Joël Alwen
Jeremiah Blocki
Krzysztof Pietrzak
Verlag: Springer International Publishing
Buch: Advances in Cryptology – EUROCRYPT 2018
Print ISBN: 978-3-319-78374-1

Electronic ISBN: 978-3-319-78375-8

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-78375-8_4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"