Moderately hard functions: Definition, instantiations, and applications

J.F. Alwen, B. Tackmann, in:, Y. Kalai, L. Reyzin (Eds.), Springer, 2017, pp. 493–526.


Conference Paper | Published | English

Scopus indexed
Author
Alwen, Joel FIST Austria; Tackmann, Björn
Editor
Kalai, Yael; Reyzin, Leonid
Department
Series Title
LNCS
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.
Publishing Year
Date Published
2017-11-05
Volume
10677
Page
493 - 526
Conference
TCC: Theory of Cryptography
Conference Location
Baltimore, MD, United States
Conference Date
2017-11-12 – 2017-11-15
IST-REx-ID
609

Cite this

Alwen JF, Tackmann B. Moderately hard functions: Definition, instantiations, and applications. In: Kalai Y, Reyzin L, eds. Vol 10677. Springer; 2017:493-526. doi:10.1007/978-3-319-70500-2_17
Alwen, J. F., & Tackmann, B. (2017). Moderately hard functions: Definition, instantiations, and applications. In Y. Kalai & L. Reyzin (Eds.) (Vol. 10677, pp. 493–526). Presented at the TCC: Theory of Cryptography, Baltimore, MD, United States: Springer. https://doi.org/10.1007/978-3-319-70500-2_17
Alwen, Joel F, and Björn Tackmann. “Moderately Hard Functions: Definition, Instantiations, and Applications.” edited by Yael Kalai and Leonid Reyzin, 10677:493–526. Springer, 2017. https://doi.org/10.1007/978-3-319-70500-2_17.
J. F. Alwen and B. Tackmann, “Moderately hard functions: Definition, instantiations, and applications,” presented at the TCC: Theory of Cryptography, Baltimore, MD, United States, 2017, vol. 10677, pp. 493–526.
Alwen JF, Tackmann B. 2017. Moderately hard functions: Definition, instantiations, and applications. TCC: Theory of Cryptography, LNCS, vol. 10677. 493–526.
Alwen, Joel F., and Björn Tackmann. Moderately Hard Functions: Definition, Instantiations, and Applications. Edited by Yael Kalai and Leonid Reyzin, vol. 10677, Springer, 2017, pp. 493–526, doi:10.1007/978-3-319-70500-2_17.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar
ISBN Search