Sustained Space Complexity
Sustained Space Complexity
复制标题
持续的空间复杂性
DOI：
10.1007/978-3-319-78375-8_4
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Pietrzak, Krzysztof
中科院分区：
文献类型：
--
作者：
Alwen, Joël;Blocki, Jeremiah;Pietrzak, Krzysztof
内存硬函数（MHF）是一类求值成本主要由内存成本决定的函数。mhf是平等的，在专用硬件（如fpga或asic）上评估它们并不比在现成硬件（如x86 cpu）上评估便宜多少。mhf具有有趣的加密应用程序，最值得注意的是密码散列和保护区块链。Alwen和Serbinenko [STOC ' 15]将函数的累积内存复杂度（cmc）定义为计算该函数所需的内存量的总和（在所有时间步长上）。他们主张一个好的MHF必须有高cmc。与以前的概念不同，cmc考虑到专用硬件可能会利用摊销和并行性。尽管如此，cmc仍被批评为不够充分，因为它未能捕捉到可能的时间-记忆权衡；由于内存成本不是线性扩展的，具有相同CMC的功能的实际硬件成本仍然可能相差很大。在这项工作中，我们解决了这个问题，并引入了持续内存复杂性的概念，这要求任何评估函数的算法都必须在许多步骤中使用大量内存。我们构建的函数（在并行随机oracle模型中），其持续内存复杂度几乎是最优的：我们的函数可以使用nsteps和内存来评估，在每一步中对（固定输入长度）随机oracle进行一次查询，而任何可以对随机oracle进行任意多个并行查询的算法，仍然需要内存来执行步骤。正如之前对各种概念（包括cmc）所做的那样，我们将构造具有高持续内存复杂性的mhf的任务简化为证明dag上的下界。我们的主要技术贡献是在节点上构建了一组dag，这些dag具有恒定度和高“持续空间复杂性”，这意味着任何并行的黑砾策略都需要至少几个步骤。在此过程中，我们构建了一个具有最大度的最大“深度鲁棒性”dag家族，改进了Mahmoody等人[ITCS ' 13]具有最大度的构建。
Memory-hard functions (MHF) are functions whose evaluation cost is dominated by memory cost. MHFs are egalitarian, in the sense that evaluating them on dedicated hardware (like FPGAs or ASICs) is not much cheaper than on off-the-shelf hardware (like x86 CPUs). MHFs have interesting cryptographic applications, most notably to password hashing and securing blockchains.Alwen and Serbinenko [STOC’15] define the cumulative memory complexity (cmc) of a function as the sum (over all time-steps) of the amount of memory required to compute the function. They advocate that a good MHF must have high cmc. Unlike previous notions, cmc takes into account that dedicated hardware might exploit amortization and parallelism. Still, cmc has been critizised as insufficient, as it fails to capture possible time-memory trade-offs; as memory cost doesn’t scale linearly, functions with the same cmc could still have very different actual hardware cost.In this work we address this problem, and introduce the notion of sustained-memory complexity, which requires that any algorithm evaluating the function must use a large amount of memory for many steps. We construct functions (in the parallel random oracle model) whose sustained-memory complexity is almost optimal: our function can be evaluated usingnsteps andmemory, in each step making one query to the (fixed-input length) random oracle, while any algorithm that can make arbitrary many parallel queries to the random oracle, still needsmemory forsteps.As has been done for various notions (including cmc) before, we reduce the task of constructing an MHFs with high sustained-memory complexity to proving pebbling lower bounds on DAGs. Our main technical contribution is the construction is a family of DAGs onnnodes with constant indegree with high “sustained-space complexity”, meaning that any parallel black-pebbling strategy requirespebbles for at leaststeps.Along the way we construct a family of maximally “depth-robust” DAGs with maximum indegree, improving upon the construction of Mahmoody et al. [ITCS’13] which had maximum indegree.
登录
查看更多内容
DOI：
--
发表时间：
2017
期刊：
Theory of Cryptography Conference
影响因子：
--
作者：
J. Alwen;Björn Tackmann
通讯作者：
Björn Tackmann
黑白卵石的累积空间和分辨率
DOI：
10.4230/lipics.itcs.2017.38
发表时间：
2017
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
J. Alwen;Susanna F. de Rezende;Jakob Nordström;Marc Vinyals
通讯作者：
Marc Vinyals
抗 ASIC 的带宽硬函数
DOI：
--
发表时间：
2017
期刊：
Theory of Cryptography Conference
影响因子：
--
作者：
Ling Ren;S. Devadas
通讯作者：
S. Devadas
对时间存储权衡的观察
DOI：
--
发表时间：
1973
期刊：
Journal of computer and system sciences (Print)
影响因子：
--
作者：
S. Cook
通讯作者：
S. Cook
高效计算数据独立的内存硬函数
DOI：
--
发表时间：
2016
期刊：
Annual International Cryptology Conference
影响因子：
--
作者：
J. Alwen;Jeremiah Blocki
通讯作者：
Jeremiah Blocki