WikiDer > Лемма о оставшихся хэшах

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

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

• Универсальное хеширование
• Мин-энтропия
• Энтропия Реньи
• Информационно-теоретическая безопасность

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

• К. Х. Беннет, Г. Брассард и Дж. М. Роберт. Усиление конфиденциальности путем публичного обсуждения. SIAM Journal on Computing, 17 (2): 210-229, 1988.
• К. Беннет, Г. Брассард, К. Крепо и У. Маурер. Обобщенное усиление конфиденциальности. IEEE Transactions по теории информации, 41, 1995.
• J. Håstad, R. Impagliazzo, L.A. Levin и M. Luby. Генератор псевдослучайных ситуаций из любой односторонней функции. SIAM Journal on Computing, v28 n4, pp. 1364-1396, 1999.