STRICT MEMORY HARD HASHING FUNCTIONS (PRELIMINARY V0.3, 01-19-14)

Abstract. We introduce the concept of strict memory hard functions. Strict memory hard functions are an extension of memory hard functions such that a slight reduction in the memory available for computation, compared to a predefined optimal memory size, makes the function evaluation exponentially slower or infeasible. The main application of strict memory hard functions is to prove a certain amount of memory is used during a certain time interval or in a certain computation. This in turn can be used to attest that areas of mem-ory of devices do not contain hidden data. Other applications are password hashing and proof of work. We present SeqMemoHash and RandMemoHash, two sequential memory hard functions under the random oracle model. 1