Относительные биты безопасности более медленных функций

Если оставить в стороне предположения о жесткости памяти, некоторые медленные хеш-функции представляют собой повторяющиеся версии обычных криптографических хэшей с добавлением соли. Обычно это определяется круглый параметр, т. е. в PBKDF2. Есть ли документ по криптографии, в котором рассматривается определение битов безопасности на основе фактора раунды линейных последовательных вызовов (не параллельных) для одного выходного вычисления?

То есть, конкретный пример: ломает прообраз sha3 (свежая_соль, входное_значение) легче чем sha3(sha3(sha3(sha3(fresh_salt, input_value)))) для некоторой низкой энтропии input_value (т. е. 64 бита), и если да последний предлагает 2 бита дополнительной безопасности, потому что относительные усилия, требуемые злоумышленником, в 4 раза больше? Любая исследовательская работа, в которой обсуждается это (относительное состязательное усилие, необходимое между независимыми или линейно-зависимыми функциями и прагматичными битами предлагаемой безопасности)?

• Этот вопрос похож на Последствия безопасности медленных хэшей для относительной безопасности по сравнению с размером хэша, но меня больше всего интересует ответ, связанный с доказательством безопасности.

Были уточнены представления о том, что означает наличие у протокола $\лямбда$- немного безопасности. Самый известный из них, вероятно, Micciancio-Walter. О битовой безопасности криптографических примитивов.

Понятие битовой безопасности отличается от того, работаете ли вы с

• игра решения, где это $\min_A\log_2 \frac{T(A)}{(\mathsf{adv}^A)^2}$, то есть весы квадратично с преимуществом противника или

• игра поиск где это $\min_A \log_2 \frac{T(A)}{\mathsf{adv}^A}$, то есть весы линейно с преимуществом противника.

$\мин_А$ минимизируется по всем противникам, атакующим примитив, и $Т(А)$ время работы $А$. Обратите внимание, что преимущество в играх с поиском/решением определяется по-разному (для игр с поиском это примерно вероятность успеха, для игр с принятием решений – $2\дельта-1$, куда $\дельта$ вероятность успеха).

Во всяком случае, в этой структуре вы можете попытаться доказать что-то вроде

Если $Ч(\кдот)$ это хэш-функция, которая $\каппа$-bit устойчивый к предварительному изображению, затем $ Н ^ {\ circ k} (\ cdot) $, $к$-складная композиция из $Ч$, является $(\log_2(k) + \каппа)$-bit pre-image устойчивый.

Доказательство примерно выглядит следующим образом

1. Начните с $\min_A \log_2 \frac{T(A)}{\mathsf{adv}_H^A}\geq \kappa$, куда $\mathsf{adv}^A_H$ является преимуществом $А$ в игре, определяющей предобразное сопротивление.

2. Установить некую границу преимущества $\mathsf{adv}_{H ^{\circ k}}^A \leq \mathsf{adv}_H^A$, отслеживая время работы нового противника $В$ один (неявно) конструируется как часть этого.Для простоты предположим, что $\mathsf{adv}_{H ^{\circ k}}^B \leq \mathsf{adv}_H^A$, и $Т(В) = кТ(А)$ --- мне не ясно, это правда, но я думаю, что это предположение подразумевается в вашем вопросе.

3. Тогда у нас есть это $\min_B \frac{T(B)}{\mathsf{adv}_{H ^{\circ k}}^B} \geq \min_A\frac{kT(A)}{\mathsf{adv}_{ H}^A} = \log_2 k + \каппа$.

Как указывает № 2 выше, это действительно сводится к показу (традиционной) границы преимущества формы.

Для любого противника $В$ против $ SHA3 ^ {\ circ k} $, есть противник $А$ против $SHA3$ с

• $Т(В) = кТ(А)$, и
• $\mathsf{adv}^B_{SHA3^{\circ}} \leq\mathsf{adv}^A_{SHA3}$.

Это означает, что структура MW позволяет обсуждать, насколько более высокое время работы $В$ влияет на безопасность (это ваш вопрос), но все же нужно доказать наличие преимущества.

Несколько мыслей по этому поводу, не совсем уверен, что мой ответ затронет вас, и, возможно, у него есть недостатки.

Сначала несколько слов о безопасности. Когда мы говорим, что криптографическая схема имеет $λ$ части безопасности, что мы обычно имеем в виду, что единственный способ сломать его — это взломать информацию о лазейке и, таким образом, попытаться $2^О»$ комбинации. Конечно, мы не рассматриваем какие-либо другие типы атак, атаки по сторонним каналам и т. д. После этого мы рассматриваем модель противника, например. вычислительно ограничен. И если мы докажем, что схема защищена от этого противника, то мы скажем, что она $λ$ кусочки безопасности.

Поскольку вы имеете в виду теоретическую безопасность, ответ нет. Вероятно, было бы да, если бы вы имели в виду количественную безопасность. Я попытаюсь предложить очень интуитивный контрпример.

Вместо рассмотрения хеш-функции рассмотрите, например, Textbook RSA с правильным дополнением. Определим его безопасность только с точки зрения семантической безопасности. Итак, он безопасен, и поэтому мы говорим, что он имеет $1^О»$ биты безопасности, если для любого $PPT$ противник (по параметру безопасности) любая пара сообщений одинаковой длины $м_1, м_2$, их основные зашифрованные тексты вычислительно неразличимы. Если предположение RSA верно, мы знаем, что RSA семантически безопасен.

Теперь рассмотрим новую схему, где $c=Enc_k(Enc_k(x))$. Если бы последняя схема шифрования была более надежной, чем первая, это означало бы, что противник смог бы добиться существенного преимущества в игре, где ему даются два шифротекста, каждый из которых зашифрован с помощью двух схем, например. распределения должны быть не пренебрежимо близкими. Исходя из предположения RSA, этого не может быть.