什么是理想的记忆硬功能？

Question

这说，f_n是很难记忆的，如果，对于任何空间S和时间T，S\cdot T \in \Omega(n^2)。

我的问题：

• S是什么？太空？例如可用内存的字节？
• n是什么？内存硬函数请求内存的字节？
• T是什么？子弹的数量？
• 这个定义有多好？它有多紧？例如，\Omega(n^2)是渐近下限，但我想不是所有\in \Omega(n^2)函数都是相等的。也许有些更好？所以，我想这个定义不够紧，不能告诉我们哪个内存硬的KDF一定会更好？
• 有更好的记忆硬度定义吗？比简单的\in \Omega(n^2)更紧？

Answer 1

这篇文章讨论了其中的许多问题。在这种情况下，“对手”是一些算法，它可以使用比我们预期的更少的资源来评估f_n。

• S =对手的空间/内存复杂性。在这一行工作中，f_n是一个调用某个随机oracle H : \{0,1\}^k \to \{0,1\}^k的函数，而S是对手(最坏情况)的空间使用情况，以k-bit“块”来衡量。
• T =对手的时间复杂性。通常以调用H的次数来衡量。在某些模型中，对手可以免费对H进行并行调用，因此T是对H的“顺序回合”调用的数量。
• n =内存硬函数的可调硬度参数.更大的n增加了评估函数f_n所需的工作量(理想情况下，工作量在n中是二次扩展的)。诚实的各方应该选择最大的n，这样他们就愿意花费精力来评估f_n。

这个定义有多好？所以，我想这个定义不够紧，不能告诉我们哪个内存硬的KDF一定会更好？

诚然，n^2/1000与1000n^2有很大的不同，但是这个定义对于具有这两个难度级别的内存硬函数会很满意。在本文编写时，大多数候选内存硬函数的渐近性比\Theta(n^2)差得多.因此，这个定义非常有效地排除了许多不好的候选人。一旦你有很多候选人满足这个渐近定义，那么你就可以开始担心常数因素了。

有更好的记忆硬度定义吗？

是的，这个定义只考虑最坏的空间使用情况S。假设f_n是一个函数，它确实需要n内存单元来计算--如果在某个时刻不保存n内存单元，就无法计算f_n。这并不排除只在很短的时间内需要n内存单位的可能性。换句话说，可能有一个用于f_n的算法，其内存使用时间图如下所示：

(从列奥·雷津在氪星上的幻灯片拍摄的图片)

如果该算法具有最大的空间利用率n且同时使用n时间，则其ST-复杂度为\Omega(n^2).复杂性就像这张图片中蓝色边框矩形的区域。

但是这种记忆硬度的测量掩盖了一些问题。假设一个对手想要在许多不同的输入上评估f_n，并且它聪明地将这些评估安排如下：

此策略可用于评估示例f_n在n上的不同输入，只需使用O(n)时间和O(n)总内存！因此，用于计算函数n时间的总“ST成本”为O(n^2)，这意味着每个实例的摊销成本仅为O(n)。

对函数的记忆硬度进行分类的一个更好的方法是测量曲线下的面积，而不是包围框的面积。这确实是在后续工作中提出的，在那里，内存硬度度量被称为“累积内存复杂性”。