Abstract
Memory-hard functions (MHFs) are moderately-hard functions which enforce evaluation costs both in terms of time and memory (often, in form of a trade-off). They are used e.g. for password protection, password-based key-derivation, and within cryptocurrencies, and have received a considerable amount of theoretical scrutiny over the last few years. However, analyses see MHFs as modes of operation of some underlying hash function \(\mathcal {H}\), modeled as a monolithic random oracle. This is however a very strong assumption, as such hash functions are built from much simpler primitives, following somewhat ad-hoc design paradigms.
This paper initiates the study of how to securely instantiate \(\mathcal {H}\) within MHF designs using common cryptographic primitives like block ciphers, compression functions, and permutations. Security here will be in a model in which the adversary has parallel access to an idealized version of the underlying primitive. We will provide provably memory-hard constructions from all the aforementioned primitives. Our results are generic, in that we will rely on hard-to-pebble graphs designed in prior works to obtain our constructions.
One particular challenge we encounter is that \(\mathcal {H}\) is usually required to have large outputs (to increase memory hardness without changing the description size of MHFs), whereas the underlying primitives generally have small output sizes.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We will use the more fine-grained metric of cumulative memory complexity (CMC), but for now the product of time and memory will suffice for an informal understanding.
- 2.
Actually for certain graphs, we prove that the efficiency gap can be reduced to the optimal bound O(1), by giving a more memory-efficient sequential algorithm.
- 3.
Our first result in fact only requires a lower bound on \({\mathsf {cc}} ({\mathbb {G}})\). It is an interesting open question to provide a wide-block labeling function which only relies on a lower bound for \({\mathsf {cc}} ({\mathbb {G}})\), rather than the (stronger) depth-robustness requirement.
- 4.
We assume the compression function allows both \({L} \)- and \(2{L} \)-bit inputs, though most compression functions do not allow this by design. This could however be easily achieved by reserving one bit of the input to implement domain separation, and then padding short inputs.
- 5.
We assume the compression function allows both \({L} \)- and \(2{L} \)-bit inputs, though most compression functions do not allow this by design. This could however be easily achieved by reserving one bit of the input to implement domain separation, and then padding short inputs.
- 6.
\({{\mathsf {Tm}}} ({{\mathsf {A}}})\) (and \({{\mathsf {Spc}}} ({{\mathsf {A}}})\)) measure worst-case sequential efficiency by providing upper bounds on time/memory.
- 7.
Recall that the total number of output labels/ideal primitive queries that the algorithm makes is at most \({{\mathsf {q}}} \).
- 8.
\({\mathsf {pred}} (v) = \emptyset \) for \(v\in {\mathsf {src}} ({\mathbb {G}})\).
- 9.
First-predecessor-distinctness holds as each non-source node v can pick her previous node in the subpath (that traverses all of the vertices) as their first predecessor; predecessors-distinctness holds as otherwise a cycle would exist.
- 10.
See Remark 3 for definition of predecessors-distinct graphs.
- 11.
\({\mathbb {G}} \) can have multiple source/sink nodes.
- 12.
\({{\mathbb {CF}}} \) denotes the compression function, \({{\mathbb {IC}}} \) denotes the ideal cipher, and \({{\mathbb {RP}}} \) denotes the random permutation.
- 13.
We assume an implicit order for the calls in the same round.
- 14.
Note that the existence of a correct call for v in round \({i} \) does not imply \(v \in {\mathsf {P}} _{{i}}\), because v may not have a critical call in the future.
- 15.
If \({{\mathbb {IP}}} ={{\mathbb {IC}}}/{{\mathbb {RP}}} \), this also implies that \(\{{\mathsf {aftlab}} (v)\}_{v\in {\mathbb {V}}}\) are distinct.
- 16.
By non-colliding, we mean \({\mathbf {x}} = ({x} _{1},\dots ,{x} _{{n_{s}}})\) where \({x} _{i}\ne {x} _{j}\) for every \(i\ne j\).
- 17.
Note that we don’t need an indicator (e.g., \({h} _{j} = \bot \)) to tell if \({h} _{j}\) is empty or not, as we can know it from the sequence \(Q_{{i}}\). This enables us to have a shorter \(H_{{i}}\).
- 18.
We assume that the encoding of the hint is unambiguous.
- 19.
Recall that there is an implicit chronological order for the calls.
- 20.
\({v} _{ |{\mathsf {P}} _{{i}}|}\) is picked first, then \({v} _{|{\mathsf {P}} _{{i}}|-1}\),..., and finally \({v} _{1}\).
- 21.
Recall that in \({{{\mathsf {A}}} ({\sigma } _{{i}})} \), there was no correct call for v before the round of the first critical call for v.
- 22.
\({\mathbb {G}} \) has a single source/sink vertex.
- 23.
The last \({K}-1\) edges make sure that the \({K} \) nodes at column 1 have distinct sets of predecessors (Sect. 2.3).
- 24.
We assume an implicit order for nodes in \({\mathbb {G}} _{1}\) and \({\mathbb {G}} _{2}\).
- 25.
See Remark 3 for definition of first-predecessor-distinctness.
- 26.
Note that \({\beta } _{{\mathsf {fix}}}\)-pebbling reducibility holds for multi-sources graphs.
- 27.
A \({d} \)-path is a path with \({d} \) vertices.
- 28.
Note that \({\mathsf {copy}} (v_1) -{S_{\mathsf {ext}}} \) is non-empty because \( |{\mathsf {copy}} (v_1) \cap {S_{\mathsf {ext}}} | \le |{\mathsf {nodes}} (v_1) \cap {S_{\mathsf {ext}}} |< \frac{{K}}{4}< {K} = |{\mathsf {copy}} (v_1)|\,. \) The first inequality holds as \({\mathsf {copy}} (v_1) \subseteq {\mathsf {nodes}} (v_1)\), the second inequality holds because \(v_1 \notin S\).
- 29.
See Remark 3 for definition of first-predecessor-distinctness.
- 30.
\({\mathbb {G}} \) has single source/sink.
- 31.
A random permutation can be viewed as an ideal cipher with a fixed key.
References
Alwen, J., Blocki, J.: Efficiently computing data-independent memory-hard functions. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part II. LNCS, vol. 9815, pp. 241–271. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_9
Alwen, J., Blocki, J., Harsha, B.: Practical graphs for optimal side-channel resistant memory-hard functions. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.), ACM CCS 17, pp. 1001–1017. ACM Press, October/November 2017
Alwen, J., Blocki, J., Pietrzak, K.: Depth-robust graphs and their cumulative memory complexity. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Part III. LNCS, vol. 10212, pp. 3–32. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56617-7_1
Alwen, J., Blocki, J., Pietrzak, K.: Sustained space complexity. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part II. LNCS, vol. 10821, pp. 99–130. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_4
Alwen, J., Chen, B., Kamath, C., Kolmogorov, V., Pietrzak, K., Tessaro, S.: On the complexity of scrypt and proofs of space in the parallel random oracle model. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016, Part II. LNCS, vol. 9666, pp. 358–387. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_13
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, Part III. LNCS, vol. 10212, pp. 33–62. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56617-7_2
Alwen, J., Serbinenko, V.: High parallel complexity graphs and memory-hard functions. In: Servedio, R.A. Rubinfeld, R. (eds.), 47th ACM STOC, pp. 595–603. ACM Press, June 2015
Alwen, J., Tackmann, B.: Moderately hard functions: definition, instantiations, and applications. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017, Part I. LNCS, vol. 10677, pp. 493–526. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_17
Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Ashby, V. (ed.), ACM CCS 93, pp. 62–73. ACM Press, November 1993
Biryukov, A., Dinu, D., Khovratovich, D.: Argon2 password hash. Version 1.3 (2016). https://www.cryptolux.org/images/0/0d/Argon2.pdf
Blocki, J., Harsha, B., Kang, S., Lee, S., Xing, L., Zhou, S.: Data-independent memory hard functions: new attacks and stronger constructions. Cryptology ePrint Archive, Report 2018/944 (2018). http://eprint.iacr.org/2018/944
Blocki, J., Zhou, S.: On the depth-robustness and cumulative pebbling cost of Argon2i. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017, Part I. LNCS, vol. 10677, pp. 445–465. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_15
Boneh, D., Corrigan-Gibbs, H., Schechter, S.: Balloon hashing: a memory-hard function providing provable protection against sequential attacks. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Part I. LNCS, vol. 10031, pp. 220–248. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_8
Dryja, T., Liu, Q.C., Park, S.: Static-memory-hard functions, and modeling the cost of space vs. time. In: Beimel, A., Dziembowski, S. (eds.) TCC 2018, Part I. LNCS, vol. 11239, pp. 33–66. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03807-6_2
Dwork, C., Naor, M., Wee, H.: Pebbling and proofs of work. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 37–54. Springer, Heidelberg (2005). https://doi.org/10.1007/11535218_3
Dziembowski, S., Kazana, T., Wichs, D.: One-time computable self-erasing functions. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 125–143. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19571-6_9
Forler, C., Lucks, S., Wenzel, J.: Catena: a memory-consuming password scrambler. IACR Cryptology ePrint Archive 2013/525 (2013)
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_2
Percival, C.: Stronger key derivation via sequential memory-hard functions. In: BSDCan 2009 (2009)
Percival, C., Josefsson, S.: The scrypt password-based key derivation function (2012)
Ren, L., Devadas, S.: Bandwidth hard functions for ASIC resistance. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017, Part I. LNCS, vol. 10677, pp. 466–492. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_16
Ristenpart, T., Shacham, H., Shrimpton, T.: Careful with composition: limitations of the indifferentiability framework. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 487–506. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20465-4_27
Acknowledgments
The authors were partially supported by NSF grants CNS-1553758 (CAREER), CNS-1719146, CNS-1528178, and IIS-1528041, and by a Sloan Research Fellowship.
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
A Compression Arguments
A Compression Arguments
Lemma 9
([16]). Fix an algorithm \({{\mathsf {A}}} \), let \({\mathcal {B}} \) be a sequence of random bits. \({{\mathsf {A}}} \) on input a hint \({h} \in {\mathcal {H}} \) adaptively queries specific bits of \({\mathcal {B}} \) and outputs \({p} \) indices of \({\mathcal {B}} \) that were not queried before, along with guesses for each of the bits. The probability (over the choice of \({\mathcal {B}} \) and randomness of \({{\mathsf {A}}} \)) that there exists an \({h} \in {\mathcal {H}} \) where \({{\mathsf {A}}} ({h})\) guesses all bits correctly is at most \(|{\mathcal {H}} |/2^{{p}}\).
Lemma 10
Fix \({L} \in {\mathbb {N}} \) and an algorithm \({{\mathsf {A}}} \) that can make no more than \({{\mathsf {q}}} =2^{{L}-2}\) oracle queries. Let \({{\mathsf {ic}}} \) be an ideal cipher uniformly chosen from the set \({{\mathbb {IC}}} \) with domain \({\mathcal {K}} \times {\{0,1\}} ^{{L}}\) and image \({\{0,1\}} ^{{L}}\).Footnote 31 \({{\mathsf {A}}} \) on input a hint \({h} \in {\mathcal {H}} \) adaptively makes forward/inverse queries to \({{\mathsf {ic}}} \), and outputs \({p} \le 2^{{L}-2}\) ideal primitive entries (as well as guesses for each of the entry values) that were not queried before. The probability (over the choice of \({{\mathsf {ic}}} \) and randomness of \({{\mathsf {A}}} \)) that there exists an \({h} \in {\mathcal {H}} \) where \({{\mathsf {A}}} ({h})\) guesses all permutation entries correctly is at most \(|{\mathcal {H}} |/2^{{p} ({L}-1)}\).
Proof
The proof is deferred to full version. \(\square \)
Rights and permissions
Copyright information
© 2019 International Association for Cryptologic Research
About this paper
Cite this paper
Chen, B., Tessaro, S. (2019). Memory-Hard Functions from Cryptographic Primitives. In: Boldyreva, A., Micciancio, D. (eds) Advances in Cryptology – CRYPTO 2019. CRYPTO 2019. Lecture Notes in Computer Science(), vol 11693. Springer, Cham. https://doi.org/10.1007/978-3-030-26951-7_19
Download citation
DOI: https://doi.org/10.1007/978-3-030-26951-7_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-26950-0
Online ISBN: 978-3-030-26951-7
eBook Packages: Computer ScienceComputer Science (R0)
