Лемма об оставшемся хеше

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

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

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

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

Пусть $X$ — случайная величина над ${\mathcal {X}}$ и пусть $m>0$ . Позволять ${\textstyle h\colon {\mathcal {S}}\times {\mathcal {X}}\rightarrow \{0,\,1\}^{m}}$ быть 2-универсальной хэш-функцией . Если

{\textstyle m\leq H_{\infty }(X)-2\log \left({\frac {1}{\varepsilon }}\right)}

тогда для $S$ униформы закончилось ${\mathcal {S}}$ и независимо от $X$ мы имеем:

{\textstyle \delta \left[(h(S,X),S),(U,S)\right]\leq \varepsilon .}

где $U$ однороден по $\{0,1\}^{m}$ независимо от $С.$ и ^[2]

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

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

См. также

Ссылки

^ Импальяццо, Рассел ; Левин Леонид А. ; Луби, Майкл (1989), «Псевдослучайная генерация из односторонних функций», Джонсон, Дэвид С. (редактор), Труды 21-го ежегодного симпозиума ACM по теории вычислений, 14–17 мая 1989 г., Сиэтл , Вашингтон, США , {ACM}, стр. 12–24, doi : 10.1145/73007.73009 , S2CID 18587852
^ Рубинфельд, Роннит ; Друкер, Энди (30 апреля 2008 г.), «Лекция 22: Лемма об остаточном хэше и явное извлечение» (PDF) , конспекты лекций по курсу 6.842 Массачусетского технологического института, Случайность и вычисления , Массачусетский технологический институт , получено 19 февраля 2019 г.

[1] Импальяццо, Рассел ; Левин Леонид А. ; Луби, Майкл (1989), «Псевдослучайная генерация из односторонних функций», Джонсон, Дэвид С. (редактор), Труды 21-го ежегодного симпозиума ACM по теории вычислений, 14–17 мая 1989 г., Сиэтл , Вашингтон, США , {ACM}, стр. 12–24, doi : 10.1145/73007.73009 , S2CID 18587852

[2] Рубинфельд, Роннит ; Друкер, Энди (30 апреля 2008 г.), «Лекция 22: Лемма об остаточном хэше и явное извлечение» (PDF) , конспекты лекций по курсу 6.842 Массачусетского технологического института, Случайность и вычисления , Массачусетский технологический институт , получено 19 февраля 2019 г.

[1]

[2]