Memory-hard function: Difference between revisions

Revision as of 05:30, 27 December 2022

Revision as of 04:17, 12 January 2023

Line 2:

{{Multiple issues|{{More citations needed|date=December 2019}}{{original research|date=December 2019}}{{tone|date=January 2021}}}}

In [[cryptography]], a '''memory-hard function''' (MHF) is a function that costs a significant amount of [[random-access memory|memory]] to evaluate. It differs from a [[memory-bound function]], which incurs cost by slowing down computation through memory latency. Use MHFs incan itemsbe suchused as [[proof of work]].

== Memory hard measure ==

There are different ways to measure the memory hardness of a function, and a commonly seen measure is Cumulative Memory Complexity (CMC). In a parallel model, CMC is the sum of the memory required to compute a function over every time step of the computation.<ref>(AS15) Alwen, Serbineko, [https://eprint.iacr.org/2014/238.pdf ''High Parallel Complexity Graphs and Memory-Hard Functions''], 2015</ref><ref>{{cite arXiv |last1=Alwen |first1=Joel |last2=Blocki |first2=Jeremiah |last3=Pietrzak |first3=Krzysztof |date=2017-07-07 |title=Sustained Space Complexity |class=cs.CR |eprint=1705.05313 }}</ref>

Other viable measures are integrating memory against physical time.<ref>(MO16) Moran, Orlov, [https://eprint.iacr.org/2016/035.pdf ''Simple Proofs of Space-Time and Rational Proofs of Storage''], 2016</ref>, and measuring memory [[bandwidth (computing)|bandwidth]] consumption on a memory bus.<ref>(BR18) Blocki, Ren, [https://eprint.iacr.org/2018/221.pdf ''Bandwidth-Hard Functions: Reductions and Lower Bounds''], 2018</ref> Refer to functionsFunctions requiring high memory bandwidth are sometimes referred to as "bandwidth-hard functions."<ref>{{Cite web |last=Blocki |first=Jeremiah |last2=Liu |first2=Peiyuan |last3=Ren |first3=Ling |last4=Zhou |first4=Samson |date=2022 |title=Bandwidth-Hard Functions: Reductions and Lower Bounds |url=https://eprint.iacr.org/2018/221.pdf |url-status=live |archive-url=https://web.archive.org/web/20230112040047/https://eprint.iacr.org/2018/221.pdf |archive-date=2023-01-11 |access-date=2023-01-11 |website=[[Cryptology ePrint Archive]]}}</ref>

== Motivation ==

Line 19:

A notable problem of dMHFs is that they are prone to [[side-channel attack]]s like cache timing. People tend toward iMHFs for this reason, especially for password hashing. However, iMHFs are mathematically proven to have weaker memory hardness properties than dMHFs.<ref>Alwen, J., Blocki, J. (2016). [https://doi.org/10.1007/978-3-662-53008-5_9''Efficiently Computing Data-Independent Memory-Hard Functions.'']</ref>

==Construction==

===depth-robust graph===

For iMHFs in the parallel random oracle model (pROM), it is a known fact that the cumulative pebbling complexity is lower-bounded and upper-bounded by the depth-robustness of a graph.

===scrypt===

===bit-reversal-graph===

==References==