Лемма о оставшихся хэшах - Leftover hash lemma

В оставшаяся хеш-лемма это лемма в криптография впервые заявлено Рассел Импальяццо, Леонид Левин, и Майкл Луби.^[1]

Представьте, что у вас есть секрет ключ $Икс$ который имеет $п$ равномерный случайный биты, и вы хотите использовать этот секретный ключ для шифрования сообщения. К сожалению, вы были немного небрежны с ключом и знаете, что противник смог узнать ценности некоторых $т < п$ биты этого ключа, но вы не знаете, какие $т$ биты. Вы все еще можете использовать свой ключ или вам придется выбросить его и выбрать новый ключ? Лемма об оставшемся хеше говорит нам, что мы можем создать ключ размером примерно $п - т$ биты, над которыми противник имеет почти нет знание. Поскольку противник знает все, кроме $п - т$ бит, это почти оптимальный.

Точнее, лемма об остатках хеша говорит нам, что мы можем извлечь асимптотику длины для ${displaystyle H_ {infty} (X)}$ (в мин-энтропия из $Икс$ ) биты из случайная переменная $Икс$ которые распределены почти равномерно. Другими словами, противник, который частично знает о $Икс$ , почти не будет знать о добытом значении. Вот почему это еще называют усиление конфиденциальности (см. раздел об усилении конфиденциальности в статье Квантовое распределение ключей ).

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

Позволять $Икс$ быть случайной величиной над ${displaystyle {mathcal {X}}}$ и разреши ${displaystyle m> 0}$ . Позволять ${extstyle hcolon {mathcal {S}} imes {mathcal {X}} ightarrow {0,, 1} ^ {m}}$ быть 2-универсальный хэш-функция. Если

{extstyle mleq H_ {infty} (X) -2log осталось ({frac {1} {varepsilon}} ight)}

тогда для $S$ униформа ${displaystyle {mathcal {S}}}$ и независимо от $Икс$ , у нас есть:

{extstyle delta left [(h (S, X), S), (U, S) ight] leq varepsilon.}

куда $U$ однороден по ${displaystyle {0,1} ^ {m}}$ и независимо от $S$ .^[2]

${extstyle H_ {infty} (X) = - log max _ {x} Pr [X = x]}$ это мин-энтропия $Икс$ , который измеряет количество случайности $Икс$ имеет. Мин-энтропия всегда меньше или равна Энтропия Шеннона. Обратите внимание, что ${extstyle max _ {x} Pr [X = x]}$ вероятность правильно угадать $Икс$ . (Лучшее предположение - угадать наиболее вероятное значение.) Следовательно, минимальная энтропия измеряет, насколько сложно угадать $Икс$ .

${extstyle 0leq delta (X, Y) = {frac {1} {2}} sum _ {v} left | Pr [X = v] -Pr [Y = v] ight | leq 1}$ это статистическое расстояние между $Икс$ и $Y$ .

Лемма о оставшихся хэшах - Leftover hash lemma

Смотрите также

Рекомендации