Moderately hard functions: Definition, instantiations, and applications Conference Paper

Author(s): Alwen, Joël; Tackmann, Björn
Title: Moderately hard functions: Definition, instantiations, and applications
Title Series: LNCS
Affiliation IST Austria
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.
Conference Title: TCC: Theory of Cryptography
Volume: 10677
Conference Dates: November 12 - 15, 2017
Conference Location: Baltimore, MD, USA
Publisher: Springer  
Date Published: 2017-01-01
Start Page: 493
End Page: 526
DOI: 10.1007/978-3-319-70500-2_17
Open access: yes (repository)
IST Austria Authors
  1. Joel Alwen
    13 Alwen
Related IST Austria Work