Лемма об остатках хеша

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

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

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

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

тогда для $S$ , равномерного по X и независимого от $X$ , мы имеем: ${\mathcal {S}}$

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