Memory-Tight Reductions
Memory-Tight Reductions
复制标题
内存紧张的减少
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Eike Kiltz
中科院分区：
文献类型：
--
作者：
Benedikt Auerbach;David Cash;Manuel Fersch;Eike Kiltz
密码约简通常旨在通过将对手\（\mathsf{A}\）转换为使用与\（\mathsf{A}\）基本相同的资源的算法来实现严密性。在这项工作中，我们开始研究的内存效率减少。我们认为，使用的工作记忆量（相对于初始对手）是一个相关的参数减少，减少内存效率低下，有时会产生不太有意义的安全保证。然后，我们指出几个常见的技术，减少内存效率低下，并提供了一个工具箱，减少内存使用。我们回顾常见的密码学假设和它们对内存使用的敏感性。最后，我们证明了一个不可能的结果表明，一些假设之间的减少必须是无可争议的内存或时间效率低下。这最后一个结果来自于与数据流算法的连接，其中无条件内存下限是已知的。
Cryptographic reductions typically aim to be tight by transforming an adversary \(\mathsf{A}\) into an algorithm that uses essentially the same resources as \(\mathsf{A}\). In this work we initiate the study of memory efficiency in reductions. We argue that the amount of working memory used (relative to the initial adversary) is a relevant parameter in reductions, and that reductions that are inefficient with memory will sometimes yield less meaningful security guarantees. We then point to several common techniques in reductions that are memory-inefficient and give a toolbox for reducing memory usage. We review common cryptographic assumptions and their sensitivity to memory usage. Finally, we prove an impossibility result showing that reductions between some assumptions must unavoidably be either memory- or time-inefficient. This last result follows from a connection to data streaming algorithms for which unconditional memory lower bounds are known.
DOI：
10.1007/978-3-662-49896-5_10
发表时间：
2016-05
期刊：
--
影响因子：
--
作者：
Christoph Bader;Tibor Jager;Yong Li;Sven Schäge
通讯作者：
Christoph Bader;Tibor Jager;Yong Li;Sven Schäge