---
res:
bibo_abstract:
- Several cryptographic schemes and applications are based on functions that are
both reasonably efficient to compute and moderately hard to invert, including
client puzzles for Denial-of-Service protection, password protection via salted
hashes, or recent proof-of-work blockchain systems. Despite their wide use, a
definition of this concept has not yet been distilled and formalized explicitly.
Instead, either the applications are proven directly based on the assumptions
underlying the function, or some property of the function is proven, but the security
of the application is argued only informally. The goal of this work is to provide
a (universal) definition that decouples the efforts of designing new moderately
hard functions and of building protocols based on them, serving as an interface
between the two. On a technical level, beyond the mentioned definitions, we instantiate
the model for four different notions of hardness. We extend the work of Alwen
and Serbinenko (STOC 2015) by providing a general tool for proving security for
the first notion of memory-hard functions that allows for provably secure applications.
The tool allows us to recover all of the graph-theoretic techniques developed
for proving security under the older, non-composable, notion of security used
by Alwen and Serbinenko. As an application of our definition of moderately hard
functions, we prove the security of two different schemes for proofs of effort
(PoE). We also formalize and instantiate the concept of a non-interactive proof
of effort (niPoE), in which the proof is not bound to a particular communication
context but rather any bit-string chosen by the prover.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Joel F
foaf_name: Alwen, Joel F
foaf_surname: Alwen
foaf_workInfoHomepage: http://www.librecat.org/personId=2A8DFA8C-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Björn
foaf_name: Tackmann, Björn
foaf_surname: Tackmann
bibo_doi: 10.1007/978-3-319-70500-2_17
bibo_volume: 10677
dct_date: 2017^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/978-331970499-9
dct_language: eng
dct_publisher: Springer@
dct_title: 'Moderately hard functions: Definition, instantiations, and applications@'
...