Oregon State University



Event Details

Memory-Hard Functions

Thursday, January 12, 2017 4:00 PM - 5:00 PM

Joel Alwen, IST Austria

This talk provides a high-level overview of the new area of Memory-Hard Functions (MHF).

Roughly speaking, an MHF has the properties that:

  • Computing the MHF on any input, using a general purpose (sequential) CPU requires a moderate amount of memory and time.
  • Yet the MHF cannot be *repeatedly* computed in *parallel* with significantly less memory and time amortized per instance. In particular, using a dedicated application specific integrated circuit (ASIC) to mount a brute-force attack still requires a moderate amount of amortized (memory x time) per instance.

MHFs were initially used in the domain of information security to build password-hashing and key-derivation functions with the property that dictionary attacks become much less cost-effective to implement in hardware. More recently, they have also been used in distributed proofs-of-work for cryptocurrencies (e.g. Ethereum, Litecoin, etc.). In contrast to computational hardness based currencies (such as bitcoin) memory-hardness based ones are more egalitarian in that the mining power per dollar spent is more equitable across computational devices. In particular, specialized mining rigs used by a small number of power users have a smaller advantage over the general purpose CPUs/GPUs used by more casual users. Finally, very recently techniques for building MHFs have found new applications in the domain of proof complexity.

In this talk we will cover:

  • An overview of how MHFs are being used in in the domain of security and cryptography.
  • The two main flavours of MHFs and some instances from practice.
  • Recent advances attacks on MHFs used in practice.
  • Recent results on proving security for MHFs.
  • Connections to more fundamental problems in combinatorics and graph theory and relations to proof complexity.
  • Open questions & new directions.

Kelley Engineering Center (campus map)
Sch Elect Engr/Comp Sci
This event appears on the following calendars: