Moderately Hard Functions: Definition, Instantiations, and Applications
Moderately Hard Functions: Definition, Instantiations, and Applications
复制标题
中等难度函数：定义、实例化和应用
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Björn Tackmann
中科院分区：
文献类型：
--
作者：
J. Alwen;Björn Tackmann
几种加密方案和应用程序是基于功能，这些功能既可以有效地计算和中等程度地倒转，包括拒绝服务保护的客户难题，通过萨尔特（Salted Hashes）进行密码保护或最近的工作证明区块链系统。尽管它们广泛使用，但对此概念的定义尚未得到明确的蒸馏和形式化。取而代之的是，要么根据功能基础的假设直接证明应用程序，要么证明了该函数的某些属性，但是该应用程序的安全性仅在非正式地进行了争论。这项工作的目的是提供（通用）定义，该定义将设计新的中等硬功能和基于它们的构建协议的努力，作为两者之间的接口。
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.