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

Лемма в криптографии

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

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

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

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

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

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

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

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

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

${\textstyle H_{\infty }(X)=-\log \max _{x}\Pr[X=x]}$ является минимальной энтропией $X$ , которая измеряет степень случайности $X.$ Минимальная энтропия всегда меньше или равна энтропии Шеннона . Обратите внимание, что это вероятность правильного угадывания $X.$ (Лучшей догадкой является угадывание наиболее вероятного значения.) Таким образом, минимальная энтропия измеряет, насколько сложно угадать $X.$ ${\textstyle \max _{x}\Pr[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) , заметки лекций по курсу MIT 6.842, Случайность и вычисления , MIT , получено 19 февраля 2019 г.

CH Bennett, G. Brassard и JM Robert. Усиление конфиденциальности путем публичного обсуждения. SIAM Journal on Computing, 17(2):210-229, 1988.
C. Bennett, G. Brassard, C. Crepeau и U. Maurer. Обобщенное усиление конфиденциальности. IEEE Transactions on Information Theory, 41, 1995.
J. Håstad, R. Impagliazzo, LA Levin и M. Luby. Генератор псевдослучайных чисел из любой односторонней функции. SIAM Journal on Computing, v28 n4, стр. 1364-1396, 1999.

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

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