Bandwidth Hard Functions for ASIC Resistance

Ling Ren, Srinivas Devadas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Cryptographic hash functions have wide applications including password hashing, pricing functions for spam and denial-of-service countermeasures and proof of work in cryptocurrencies. Recent progress on ASIC (Application Specific Integrated Circuit) hash engines raise concerns about the security of the above applications. This leads to a growing interest in ASIC resistant hash function and ASIC resistant proof of work schemes, i.e., those that do not give ASICs a huge advantage. The standard approach towards ASIC resistance today is through memory hard functions or memory hard proof of work schemes. However, we observe that the memory hardness approach is an incomplete solution. It only attempts to provide resistance to an ASIC’s area advantage but overlooks the more important energy advantage. In this paper, we propose the notion of bandwidth hard functions to reduce an ASIC’s energy advantage. CPUs cannot compete with ASICs for energy efficiency in computation, but we can rely on memory accesses to reduce an ASIC’s energy advantage because energy costs of memory accesses are comparable for ASICs and CPUs. We propose a model for hardware energy cost that has sound foundations in practice. We then analyze the bandwidth hardness property of ASIC resistant candidates. We find scrypt, Catena-BRG and Balloon are bandwidth hard with suitable parameters. Lastly, we observe that a capacity hard function is not necessarily bandwidth hard, with a stacked double butterfly graph being a counterexample.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 15th International Conference, TCC 2017, Proceedings
EditorsYael Kalai, Leonid Reyzin
PublisherSpringer
Pages466-492
Number of pages27
ISBN (Print)9783319704999
DOIs
StatePublished - Jan 1 2017
Externally publishedYes
Event15th International Conference on Theory of Cryptography, TCC 2017 - Baltimore, United States
Duration: Nov 12 2017Nov 15 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10677 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other15th International Conference on Theory of Cryptography, TCC 2017
Country/TerritoryUnited States
CityBaltimore
Period11/12/1711/15/17

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Bandwidth Hard Functions for ASIC Resistance'. Together they form a unique fingerprint.

Cite this