Publications for: Moderately Hard ComputationPub 1: Sustained Space ComplexityPub 2: On the Memory-Hardness of Data-Independent Password-Hashing FunctionsReturn to Wickr Research Program: Moderately Hard Computation sc-shortcode-cleaner-clean-content-end–>Information processing tasks require various digital resources including storage, network bandwidth and/or computation. In the physical world, we often measure the value of resources in terms of their monetary cost. For example, a kWh might cost 10¢, a particular CPU might cost $283 per unit, and 16GB of a certain DRAM module might cost $324. Understanding the cost of required resources helps us evaluate the utility of performing a particular task.

Wickr’s first research program is designed to accomplish the following goal:
Develop an egalitarian and moderately hard to evaluate cryptographic hash function.
By “egalitarian” we mean that the cost per evaluation of the hash function should vary as little as possible across real world computational devices. In particular, we want to minimize the cost advantage per evaluation of a custom built device (e.g. using an ASIC) over a general purpose off-the-shelf PC. To ensure that honest parties can still evaluate the hash function we ask that the cost not be too high. But to prevent an adversary from evaluating the hash function too often (or at least too rapidly) we still require a moderate cost per fresh evaluation. More practically, we would like the cost to be scalable (e.g. to accommodate for changing technology and different cost/benefit ratios). Therefor, we want the hash function to come equipped with an explicit (set of) parameter(s) with which to scale (different aspects of) the cost. Concretely, one parameter could regulate the amount of memory required to evaluate the function while another regulates the amount of computation required.

Applications: An important meta-use for such a moderately hard hash function is to meter out access to a given resource or capability. Here are some specific practical examples:

For each of these use cases, we see that honest parties too must perform the moderately hard task. This has at least two consequences motivating the goals for this research program as laid out above. First, the cost of performing the task should not be prohibitively large (e.g., password hashing might take about .5 second for a login server or 2 seconds for password-based file/disk encryption). Second, the cost should be egalitarian to ensure that the adversary does not gain any significant advantage by investing in special hardware.

The Path Forward: We break down the task of building and evaluating a suitable moderately hard hash function into can be, achieving via the following pair of steps.

  1. Develop a new way to measure the resources required to perform a computational task (e.g. memory, computation, network, etc.) that accurately reflect its monetary cost of performing the task on a general purpose and on task-specific hardware. Moreover, the cost predicted by the measure should be as close as possible on the different types of devices, nor should it be possible to achieving significantly lower amortized cost at scale.To get a feel for the challenge here it is instructive to look at how we normally measure computational resources, why that measure fails at the above stated goal and how that failure has resulted in undesirable trends in practice.Some (by no means exhaustive) highlights in the ongoing effort to developing more egalitarian complexity measures can be found in . Broadly speaking, these works aim to leverage the observation that costs associated with memory tend to be much more egalitarian than purely computational ones.
  2. Define a concrete, practical, moderately hard hash function. That is, a parametrized cryptographic hash function for which the new complexity measure scales smoothly in the functions parameters. To ensure an accurate cost estimate we need that the only computational resources required (in significant quantities) to evaluate the function are those accounted for by the complexity measure. Finally, to prevent adversaries gaining amortized cost advantages at scale the function must also be amortization-free. That is no significant reduction in the resources required per evaluation of the function can be achieved even, say, on related inputs and/or on parallel hardware.Some new (practical) moderately hard functions were proposed in . Other candidates can be found in the list of entrants to the Password Hashing Competition as well as buried inside various proof-of-work based consensus protocols for cryptocurrencies (e.g. .

In a sense, the goal is to build a hash function that represents one (moderately large) unit of computation measured in monetary cost per evaluation.

Alex Biryukov, Daniel Dinu, Dmitry Khovratovich: Argon2: New Generation of Memory-Hard Functions for Password Hashing and Other Applications. EuroS&P 2016: 292-302Joël Alwen, Vladimir Serbinenko: High Parallel Complexity Graphs and Memory-Hard Functions. STOC 2015: 595-603Joël Alwen, Jeremiah Blocki, Krzysztof Pietrzak: Sustained Space Complexity. EUROCRYPT (2) 2018: 99-130Dan Boneh, Henry Corrigan-Gibbs, Stuart E. Schechter: Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks. ASIACRYPT (1) 2016: 220-248Christian Forler, Stefan Lucks, Jakob Wenzel: Memory-Demanding Password Scrambling. ASIACRYPT 2014: 289-305Cynthia Dwork, Andrew V. Goldberg, Moni Naor: On Memory-Bound Functions for Fighting Spam. CRYPTO 2003: 426-444.Thaddeus Dryja, Quanquan C. Liu, Sunoo Park: Static-Memory-Hard Functions, and Modeling the Cost of Space vs. Time. TCC (1) 2018: 33-66Cynthia Dwork, Moni Naor, Hoeteck Wee: Pebbling and Proofs of Work. CRYPTO 2005: 37-54Joël Alwen, Jeremiah Blocki, Benjamin Harsha: Practical Graphs for Optimal Side-Channel Resistant Memory-Hard Functions. CCS 2017: 1001-1017Colin Percival, Simon Josefsson: The scrypt Password-Based Key Derivation Function. RFC 7914: 1-16 (2016)Ling Ren, Srinivas Devadas: Proof of Space from Stacked Expanders. TCC (B1) 2016: 262-285Bandwidth Hard Functions for ASIC Resistance. TCC (1) 2017: 466-492