Memory-hard function: Difference between revisions

Revision as of 23:34, 15 October 2020

Revision as of 23:45, 15 October 2020

Line 1:

{{Multiple issues|{{refimproveMore citations needed|date=December 2019}}{{original research|date=December 2019}}}}

In [[cryptography]], a '''memory -hard function''' (MHF) is a function that costs significant amount of [[Randomrandom-access memory|memory]] to evaluate. It is different from a [[memory -bound function]]s,; the latter incurs cost by slowing down computation through memory latency. MHFs find their use as a form of [[Proofproof of work|proof-of-work]].

== Memory hard measure ==

Line 8:

Another viable measure is 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>

Yet another measure is the 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> This category of functions are also dubbed "Bandwidthbandwidth-hard functions".

== Motivation ==

There is a reason why MHFs cost a lot of memory instead of, say, CPU cycles. [[Bitcoin]] used repeated evaluation of [[SHA-2|SHA]] function as proof of work, but it turned out that modern general -purpose processors, i.e. off-the-shelf [[Centralcentral processing unit|CPUs]], are very inefficient when tasked to compute a fixed function over and over. Miners adopted [[Applicationapplication-specific integrated circuit|application-specific integrated circuits]],s (ASICs,) and achieved 10^16 speedup. While this is fine for what bitcoinBitcoin is good for, we want a more "egalitarian" hardness measure. In other words, we want everyone to be equally inefficient in computing the function even if they have an ASIC. Because if some people can evaluate the function efficiently and some can't, then in order to make the function relatively hard for the short-cut takers, we will make the function too hard for a regular user. If everyone is inefficient, then everyone can evaluate a moderately-hard function.

Over time, it has been recognized that memory cost remains fairly equal across the board. Hence MHF.

Line 17:

== Variants ==

Based on their evaluation patterns, MHFs can be put into two camps: data-dependent (dMHF) and data-independent (iMHF). dMHFs are that which sometimes you don't know which pieces of information you would still need for later calculations, and iMHFs are ones that there's no such ambiguity. <!-- this is probably a very confusing explanation, need to change! --> Examples of dMHFs are [[scrypt]], and [[argon2Argon2]]d. Examples of iMHFs are [[argon2Argon2]]i, and [[Catenacatena (cryptography)|catena]]. Many of these MHFs are developed to be used as [[key derivation function|password hashing function]]s exactly because of their memory hardness.

dMHFs have the glaring problem that they are prone to [[side -channel attacksattack]]s like cache timing. People tend towardstoward iMHFs for this reason, especially when you are doingfor password hashing. However, iMHFs are mathematically proven to have weaker memory hardness properties than dMHFs.

== Construction ==

== 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===

===bit-reversal-graph===

== References ==

<references />

== References ==

{{Reflist}}

[[Category:Cryptography]]