Bandwidth-Hard Functions: Reductions and Lower Bounds
Bandwidth-Hard Functions: Reductions and Lower Bounds
复制标题
带宽困难函数：缩减和下界
DOI：
10.1145/3243734.3243773
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Zhou, Samson
中科院分区：
文献类型：
--
作者：
Blocki, Jeremiah;Ren, Ling;Zhou, Samson
记忆体硬函数（Memory Hard Functions, MHFs）是为了解决通用cpu与专用集成电路（Application Specific Integrated Circuits, asic）计算速度日益不平衡的问题而提出的。mhf已经得到了广泛的应用，包括密码散列、密钥扩展和工作量证明。已经提出了几个度量来量化函数的“记忆硬度”。累积内存复杂度（CMC）（或平摊面积×时间复杂度）试图量化获取/构建硬件以评估功能的成本-在标准化评估功能所需的时间之后。相比之下，带宽硬度试图量化在硬件上评估该函数的平摊能量成本——而这在很大程度上又由缓存丢失的数量决定。理想情况下，一个好的MHF既需要带宽，又具有较高的累积内存复杂度。虽然主要候选候选候选的累积内存复杂性已经被很好地理解，但对于许多突出的候选候选候选的带宽硬度知之甚少。我们的贡献如下：首先，我们提供了第一个约简证明，在并行随机oracle模型中，与数据无关的内存硬函数（iMHF）的带宽硬度由与该iMHF相关的有向无环图（DAG）的红蓝铺层代价描述。其次，我们证明了设计具有高CMC/带宽硬度的MHF的目标是一致的。特别是，我们证明了任何具有高CMC的功能也具有相对较高的能量成本。这个结果导致并行随机oracle模型中脚本的能量开销的第一个无条件下界。第三，我们分析了几个突出的候选iMHF的带宽硬度，如Argon2i，密码哈希竞赛的获胜者，aATSample和DRSample -第一个具有基本渐近最优CMC的实用iMHF。我们显示Argon2i， aATSample和DRSample在适当的缓存大小下最大带宽硬。最后，我们证明了寻找具有最小能量成本的红蓝卵石的问题是np困难的。
Memory Hard Functions (MHFs) have been proposed as an answer to the growing inequality between the computational speed of general purpose CPUs and Application Specific Integrated Circuits (ASICs). MHFs have seen widespread applications including password hashing, key stretching and proofs of work. Several metrics have been proposed to quantify the "memory hardness" of a function. Cumulative memory complexity (CMC) (or amortized Area × Time complexity ) attempts to quantify the cost to acquire/build the hardware to evaluate the function - after normalizing the time it takes to evaluate the function. By contrast, bandwidth hardness attempts to quantify the amortized energy costs of evaluating this function on hardware - which in turn is largely dominated by the number of cache misses. Ideally, a good MHF would be both bandwidth hard and have high cumulative memory complexity. While the cumulative memory complexity of leading MHF candidates is well understood, little is known about the bandwidth hardness of many prominent MHF candidates. Our contributions are as follows: First, we provide the first reduction proving that, in the parallel random oracle model, the bandwidth hardness of a Data-Independent Memory Hard Function (iMHF) is described by the red-blue pebbling cost of the directed acyclic graph (DAG) associated with that iMHF. Second, we show that the goals of designing an MHF with high CMC/bandwidth hardness are well aligned. In particular, we prove that any function with high CMC also has relatively high energy costs. This result leads to the first unconditional lower bound on the energy cost of scrypt in the parallel random oracle model. Third, we analyze the bandwidth hardness of several prominent iMHF candidates such as Argon2i, winner of the password hashing competition, aATSample and DRSample - the first practical iMHF with essentially asymptotically optimal CMC. We show Argon2i, aATSample and DRSample are maximally bandwidth hard under appropriate cache size. Finally, we show that the problem of finding a red-blue pebbling with minimum energy cost is NP-hard.
登录
查看更多内容
数据独立的内存硬功能：新的攻击和更强大的结构
DOI：
10.1007/978-3-030-26951-7_20
发表时间：
2019
期刊：
Crypto
影响因子：
--
作者：
Blocki, J;Harsha, B;Kang, S;Lee, S;Xing, L;Zhou, S.
通讯作者：
Zhou, S.
关于深度减少和格栅
DOI：
10.1109/sfcs.1983.38
发表时间：
1983
期刊：
24th Annual Symposium on Foundations of Computer Science (sfcs 1983)
影响因子：
--
作者：
G. Schnitger
通讯作者：
G. Schnitger
黑白卵石的累积空间和分辨率
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：
--
发表时间：
2018
期刊：
Financial Cryptography and Data Security (FC 2018
影响因子：
--
作者：
Jeremiah Blocki, Samson Zhou
通讯作者：
Jeremiah Blocki, Samson Zhou