Многие из них рассмотрены в статье.В этой постановке «противником» является некоторый алгоритм, который может оценить $f_n$ используя меньше ресурсов, чем мы надеялись.
$S$ = сложность пространства/памяти противника. В этом направлении работы $f_n$ это функция, которая обращается к какому-то случайному оракулу $H : \{0,1\}^k \to \{0,1\}^k$, и $S$ это (в худшем случае) использование пространства противником, измеренное в $к$-битные «блоки».
$Т$ = временная сложность противника. Обычно измеряется количеством обращений к $Ч$. В некоторых моделях противнику разрешено делать параллельные вызовы $Ч$ бесплатно, так что $Т$ количество "последовательных раундов" обращений к $Ч$.
$n$ = настраиваемый параметр жесткости функции жесткой памяти. Больше $n$ увеличивает усилия, необходимые для оценки функции $f_n$ (и в идеале усилия масштабируются квадратично в $n$). Честные партии должны выбирать самые крупные $n$ так что они готовы потратить усилия на оценку $f_n$.
Насколько хорошо это определение? ... Итак, я полагаю, что это определение недостаточно точное, чтобы показать нам, какой KDF с жестким объемом памяти обязательно лучше?
Это правда, что $n^2/1000$ сильно отличается от $1000n^2$, но это определение подходит для функций, требовательных к памяти, с любым из этих уровней сложности.
На момент написания этой статьи большинство функций-кандидатов, требовательных к памяти, были асимптотически гораздо хуже, чем $\Тета(n^2)$.
Таким образом, это определение достаточно эффективно для исключения многих плохих кандидатов.
Как только у вас будет много кандидатов, удовлетворяющих этому асимптотический определения, то вы можете начать беспокоиться о постоянных факторах.
Есть ли лучшее определение жесткости памяти?
Да, это определение касается только наихудший использование места в кейсе $S$.
Предполагать $f_n$ это функция, которая действительно требует $n$ единицы памяти для оценки - нет способа оценить $f_n$ без удержания $n$ единицы памяти в какой-то момент.
Это не исключает возможности того, что $n$ единицы памяти требуются только в течение очень короткого промежутка времени.
Другими словами, может существовать алгоритм для $f_n$ чей график использования памяти с течением времени выглядит так:
(изображения взяты из Слайды Лео Рейзина на скрипте)
Если этот алгоритм имеет максимум использование пространства $n$ а также использует $n$ время, его ST-сложность равна $\Омега(n^2)$.
ST-сложность похожа на площадь синего прямоугольника ограничивающей рамки на этом рисунке.
Но эта мера жесткости памяти скрывает некоторые проблемы.
Предположим, противник хочет оценить $f_n$ на многих различных входных данных, и он умело планирует эти оценки следующим образом:
Эту стратегию можно использовать для оценки примера $f_n$ на $n$ различные входы, используя только $ О (п) $ время и $ О (п) $ Общий объем памяти!
Таким образом, общая «стоимость ST» для оценки функции $n$ раз $ О (п ^ 2) $, что означает, что амортизированный стоимость одного экземпляра только $ О (п) $.
Лучшим способом классификации памяти функции было бы измерение площадь под кривой а не площадь ограничивающей рамки.
Именно это и предлагается в последующие работы, где метрика жесткости памяти называется «кумулятивной сложностью памяти».
