Лефтовер Хэш Лемма (LHL), пересмотр

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 01:15, 27 декабря 2015.
Leftover Hash Lemma, Revisited
Rotational Rebound Attacks on Reduced Skein.png
Авторы Boaz Barak, Yevgeniy Dodis, Hugo Krawczyk, Olivier Pereira, Krzysztof Pietrzak, Francois-Xavier Standaert, and Yu Yu
Опубликован 2011 г.
Сайт https://eprint.iacr.org/
Перевели Ilya Smirnov
Год перевода 2015 г.
Скачать [1]

Краткий обзор

Известный Лефтовер Хэш Лемма (LHL) заявляет, что (почти) универсальные функции Хэша — хорошие экстракторы случайности. Несмотря на его многочисленные приложения, основанные на LHL экстракторы страдают от следующих двух ограничений:

  • Большая Потеря Энтропии: чтобы извлечь -биты распределения из минимальной энтропии , которые -закрыты к форме, нужно установить , подразумевая, что потеря энтропии .

Для многих приложений, такая потеря энтропии слишком высока.

  • Большая продолжительность отбора: продолжительность отбора (почти) универсальной функции хэша, требуемой LHL, должна быть, по меньшей мере , где  — длина ключа (источника), который должен возрастать с количеством извлеченных битов.

Удивительно, но мы видим, что оба ограничения LHL — большая потеря энтропии и большая продолжительность отбора могут быть преодолены (или, по крайней мере, смягчены) в различных важных сценариях. Во-первых, мы видим, что потеря энтропии могла быть уменьшена до для урегулирования получения секретных ключей для широкого ряда криптографических приложений. Определенно, безопасность этих схем с LHL-полученным ключом корректно ухудшается от почти до . (Обратите внимание, что, в отличие от стандартного LHL, эта граница значима, даже когда один извлекает больше битов, чем минимальная энтропия, которую мы имеем!). Основываясь на этих результатах мы строим общий вычислительный экстрактор, который обладает низкой потерей энтропии и может быть использован, чтобы наглядно подтвердить универсальную ключевую функцию происхождения для любого криптографического приложения.

Во-вторых, мы изучим разумность естественного подхода «расширение-для-извлечения», где каждый использует псевдослучайный генератор (PRG), для расширения короткого «входного отбора » в более длинный «исходящий отбор» , чтобы затем использовать полученный в качестве отбора, требуемого LHL (или, более широко, любым случайным экстрактором). Мы покажем, что в целом подход «расширение-для-извлечения» не нормальный, если предположение Задач Диффи—Хеллмана верно. Несмотря на это, мы видим, что это также представляет: (1) извлекая «маленькое» (логарифмическое в безопасности PRG) число битов; или (2) в minicrypt. Значение (2) предполагает, что подход расширение-для-извлечения, вероятно, безопасен, когда используется с «практическим» PRGs, несмотря на недостаток в редукционистском доказательстве безопасности!

Введение

Знаменитый Лефтовер Хэш Лемма [1] (LHL; см. также[1] для более ранних формулировок), нашел огромное число приложений во многих областях теории сложности и криптографии. В его самой простой форме говорится, что универсальные хеш-функции[2] являются хорошими (сильными) экстракторами случайности[3]. В частности, если является распределением минимальной энтропии по некоторому пространству , - семейство универсальных функций (см. Определение 2) от до , - случайный участник , то, даже обусловленное "отбором” , статистическое расстояние между и равномерным распределением до , ограничено , где. Параметр определяется как потеря энтропии и измеряет количество минимальной энтропии, “принесенной в жертву”, для достижения хорошей экстракции случайности. Таким образом, никакое приложение не может отличить “извлеченную” случайность от универсального случайности с преимуществом более, чем , даже если отбор опубликован (пока независим от ).

LHL чрезвычайно привлекателен по многим причинам. Во-первых, и в первую очередь, он приводит к простым и эффективным экстракторам случайности и может быть использован во многих приложениях, требующих высокой секретной случайности. Одна из основных настроек – настройка деривации криптографического ключа, которая необходима во многих ситуациях, таких как, например, усиление конфиденциальности[4], обмена ключами Диффи-Хеллмана[5][6], биометрии[7][8], а также для генераторов случайных чисел из физических источников случайности[9][10]. Во-вторых, многие простые функции, такие как внутренний продукт или, более широко, матрица – векторная мультипликация, универсальны. Такие изящные функции имеют хорошие алгебраические свойства, которые могут использоваться по другим причинам, не зависящим от экстракции случайности (представлено несколько примеров, см.[11][12][13]). В-третьих, многие простые и эффективные конструкции (почти) универсальных хеш-функций известны[2][14][15][16], что делает экстракторы на LHL-основе самыми эффективными экстракторами на сегодняшний день. Наконец, LHL достигает оптимального значения потери энтропии , достаточного для достижения желаемого статистического расстояния . В частности, LHL достигает , что, как известно, является самой минимальной потерей энтропии для любого экстрактора[17].

Несмотря на эти чрезвычайно привлекательные свойства, основанные на LHL экстракторы не обязательно применимы или достаточны в различных ситуациях. Это происходит, прежде всего, из-за следующих двух ограничений LHL: большая потеря энтропии и большая продолжительность отбора.

  • Большая потеря энтропии. В теории потеря энтропии может показаться весьма незначительной, особенно в асимптотическом смысле. Однако, в практических ситуациях это часто все портит, особенно, когда применяется к установке ключевой деривации. В этом случае главный вопрос заключается в том, чтобы определить наименьшую min – энтропию значения , достаточного для извлечения -битного ключа с -безопасностью . Минимизация значения , которого мы называем стартовой энтропией, часто имеет решающее значение, особенно в ограниченных сценариях энтропии, таких как Обмен ключами Диффи-Хеллмана (особенно на эллиптических кривых) или биометрии. Например, для Обмена ключами Диффи-Хеллмана, значение m соответствует размеру точек эллиптической кривой, которая непосредственно влияет на эффективность. Это одна из причин, почему статистические экстракторы часто заменяются на практике на эвристические конструкции на основе криптографических хэш-функций.
  • Большая продолжительность отбора. Еще одним существенным препятствием в использовании LHL является то, что универсальные хеш-функции требуют длинного описания, что означает, что у экстракторов, основанных на LHL длительный отбор. Действительно, Стинсон[14] показал, что (совершенно) универсальные хеш-функции требуют, чтобы длительность отбора была линейна в длине источника . В целом, даже “достаточно хорошие” почти универсальные хеш-функции для LHL требуют длины отбора, по крайней мере, [14], и, таким образом, она должна вырасти с увеличением числа извлеченных битов. Эта большая продолжительность отбора делает его неудобным во многих приложениях экстракторов (например[18][19][5]), включая любое использование экстракторов для дерандомизации, где необходимо эффективно перечислить весь отбор.

Большая (и переменная длина) отбора также неудобны для стандартизированных криптографических приложений, где ключи фиксированного размера, независимо от размера вводов, одобрены (как в случае блочных шифров или криптографических хеш-функций). Когда экстракторы используются в криптографических параметрах настройки, отборы просматриваются как ключи, и следовательно отборы фиксированного размера очень желательны. В приложениях экстракторов, где атакующий, как предполагается, достаточно ограничен относительно невозможности получения источника X зависящего от отбора (например, при извлечении ключей из биометрии, физических измерений или в Обмене ключами Диффи-Хеллмана), можно было бы рассмотреть фиксацию хорошего общедоступного отбора и неоднократно использовать ее с быстрым доказуемо безопасным экстрактором. Как уже говорилось, это невозможно с универсальными хеш-функциями, так как их длина отбора должна возрастать совместно с длиной . (В теории можно создать (не на основе LHL) экстракторы, когда продолжительность отбора равна примерно логарифмической длине источника (см.[20][21]). Однако, получающиеся конструкции имеют в основном теоретическое значение и теряют простоту и эффективность основанных на LHL экстракторов).

ВЫВОДЫ. Совершенно неожиданно мы увидели, что оба ограничения LHL — большая потеря энтропии и большой отбор — могут быть преодолены или, по крайней мере, смягчены в различных важных сценариях. Мы опишем эти результаты далее.

Уменьшение потери энтропии

Сначала, снижение потери энтропии может показаться невозможной, так как мы уже упоминали, что у любого экстрактора должна быть потеря энтропии [17]. Однако это невозможно при общем применении экстракторов, где мы должны быть убеждены, что извлеченную последовательность не сможет отличить от случайной никакой статистический тест . Напротив, когда экстракторы используются для получения криптографических ключей, мы заботимся только об ограниченных типах статистических тестов . Конкретно, о тестах, которые соответствуют игре безопасности между атакующим и соперником . Например, при получении ключа для схемы подписи, единственные тесты, о которых мы заботимся, соответствуют атакующему, видящему несколько подписей и затем выводящему новую подпись. А именно, мы заботимся только о том, чтобы не пренебречь вероятностью успешной подделки, когда секретный ключ получен, используя экстрактор вместо того, чтобы быть случайным. И так как схема подписи, как предполагается, безопасна с действительно случайным ключом, мы можем ограничить наше внимание к очень ограниченному классу статистических тестов, которые почти никогда не выводят 1.

Подобные ограничения в естественных различиях возникают для других криптографических примитивов, что дает нам надежду, что нижняя граница[17] могла бы быть преодолена в таких параметрах настройки.

  • Обобщенный LHL и Приложения. Действительно, мы получаем более сложную форму LHL, называемую обобщенным LHL (см. Теорему 1), который нетривиально зависит от типа различающегося . Наша оценка содержит новый термин, неофициально измеряющий стандартное отклонение преимущества отличающегося (стандартный LHL - особый случай, где этот термин ограничен 1). Применяя это новое ограничение для анализа криптографических функций, мы получаем гораздо более жесткие рамки для безопасности криптографического приложения широкого класса. Они включают ключевую деривацию для всех приложений “непредсказуемости”, таких как подписи, MACs, односторонние функции, идентификационные схемы, и т. д. Удивительно, но они также включают ключевую деривацию для некоторых видимых “не различимостей” приложений, которые включают все схемы шифрования такие как CPA - и ССА-безопасности, и в общественных и симметричных настройках ключей, а также слабые псевдослучайные функции. В частности, в каждом из этих случаев, обозначьте -безопасность криптографического примитива (т. е., лучшую вероятность успеха или преимущество атакующего с определенными ресурсами), когда ключи с совершенно случайным ключом -bit, и соответствующее значение -безопасности, когда ключ будет получен из несовершенного источника энтропии -бит через LHL. Мы видим (вспомните, что представляет потерю энтропии):

  • Сравнение со Стандартным LHL. Давайте сначала найдем связь постоянной с LHL. Последнему требуется , для того, чтобы достигнуть того же типа безопасности как и с идеальной случайностью. Используя наше улучшение, мы видим, что уже при половине этой суммы, .

Фактически, мало того, что мы видим улучшенные оценки потери энтропии , мы также получаем значимые оценки безопасности для произвольных значений , даже отрицательные (когда потеря энтропии становится “энтропийным усилением”)! Например, стандартный LHL ничего не дает для , в то время как мы достигаем значительной безопасности для (без потери энтропии!), и даже начинаем “изящно заимствовать” безопасность из нашего приложения, когда мы извлекаем больше битов, чем минимальная энтропия источника, до (т.е., ).

  • Вычислительный Экстрактор с Улучшенной Потерей. Несмотря на то, что улучшенная связь, как уже говорилось, не применима ко всем криптографическим приложениям (самое важное упущение, являющееся псевдослучайными функциями и поточными шифрами), в Разделе 3.2 мы используем наши результаты, чтобы создать ключевую функцию деривации общего назначения для любого (защищенного по вычислениям) криптографического приложения при предоставлении полных энтропийных преимуществ, полученных из Уравнения (1). Схема комбинирует любой основанный на LHL экстрактор с любым (слабым) семейством псевдослучайной функциональности.

Сокращение продолжительности отбора

  • "Расширение для извлечения". Естественная идея уменьшить продолжительность отбора заключается в том, чтобы использовать псевдослучайный генератор (PRG), для того, чтобы развернуть короткий “входной отбор” в более длинный “выходной отбор” , и затем использовать получаившийся в качестве отбора, требуемого LHL, или, более широко, любым экстрактором случайности. Давайте назовем этот естественный подход, "расширение для извлечения". Конечно, пока каждый скрывает короткий и использует длинный в качестве общедоступного отбора для экстрактора, извлеченные биты псевдослучайны. Но действительно ли возможно гарантировать псевдослучайность вывода экстрактора, если фактический короткий отбор опубликован? Если бы это имело место, мы получили бы эффективные, основанные на LHL экстракторы с коротким отбором и, кроме того, экстрактор, длина отбора которого независима от продолжительности ввода, как требуется для практических сценариев, рассмотренных ранее.
  • Встречный пример. В Разделе 4.1 мы покажем, что подход "расширение для извлечения" не будет работать. Мы построим простой PRG (который безопасен при принятии решения Диффи-Хеллмана (DDH)) и экстрактор (который является естественной, совершенно универсальной хеш-функцией), где вывод экстрактора — любое (например, даже универсальной формы) распределение — можно эффективно отличить от случайного с вероятностью близкой к 1, когда данный короткий отбор используется для генерации псевдослучайных длинных отборов для экстрактора. Несмотря на вышесказанное, мы также видим два положительных результата, которые приятно дополняют наш встречный пример.
  • Извлечение нескольких Битов. Во-первых, в Разделе 4.2 мы покажем, что расширение для извлечения всегда работает при условии, что количество извлеченных битов “маленькое”. Здесь “маленькое” означает логарифмическое на уровне безопасности PRG, которое может колебаться от до (где - параметр безопасности), в зависимости от того, предполагается ли PRG полиномиальным или экспонентным образом. Вполне интересно, что в этом случае мы даже не должны соглашаться на псевдослучайные биты: наше небольшое число извлеченных битов фактически статистически случайно, пока PRG защищена от схем, размер которых экспоненциален в . Предположение для этого результата возникает из того, что мы можем протестировать в экспоненциале времени в , “хорош” ли данный -битный отбор экстрактора или “плох” для нашего источника . Мы также знаем, что большинство самых случайных длинных отборов должны быть хорошими. Следовательно, безопасность PRG, то же должна быть истиной для “большинства” псевдослучайных отборов , которые является именно теми, что нам нужны.
  • Безопасность в minicrypt. Во-вторых, несмотря на то, что наш исходный контрпример довольно простой и естественный, он включает в себя предположение (DDH) от “мира публичных ключей”. В Разделе 4.3, мы покажем, что такое удивительное предположение “мир публичных ключей” действительно необходимо для любого контрпримера. Мы показываем, что подход "расширение для извлечения" звучит в minicrypt[22](т.е. в гипотетическом мире, где псевдослучайные генераторы существуют, но криптография существует без публичного ключа). В частности мы создаем простой протокол с 2 сообщениями (созданный из PRG и экстрактора), который включает в себя безопасный протокол согласования ключей для любой комбинации PRG/экстрактора, для которой подход "расширение для извлечения" небезопасен. Так как у нашего протокола есть только 2 сообщения, мы получаем семантически безопасное шифрование с открытым ключом (PKE). Следовательно, так как PKE протокола не существует в minicrypt, "расширение для извлечения" должно быть безопасным.
  • Практическая Интерпретация. Это приводит к следующей практической интерпретации наших результатов, указывающих, на то, что использование подхода "расширение для извлечения" с общими псевдослучайными примитивами, такими как AES, безопасно, несмотря на отсутствие прямого (редукционистского) доказательства безопасности. На самом деле, рассмотрим схему "расширение для извлечения", реализованную через AES (в некотором режиме поточного шифра). Наши результаты показывают, что, если эта схема экстракции перестала работать, то мы нашли схему шифрования с открытым ключом, которая является доказано безопасной на основе такой безопасности AES, как блочный шифр! Кроме того, у получающегося PKE есть очень строгая форма, где секретный ключ - отбор PRG , и открытый ключ PRG-выход . (Например, в случае c AES открытый ключ - просто оценка AES на нескольких отличных точках). Как мы утверждаем в Разделе 4.3, существование такого PKE, кажется, крайне маловероятным, и это стало бы основным прорывом в искусстве. Таким образом наши результаты дают убедительные доказательства, что подход "расширение для извлечения" может быть безопасным “на практике” —, когда используется с “быстрыми” шифрами (как AES) — несмотря на то, что (обычно) небезопасен “в теории”!

Заметим также, что все наши результаты изящно обрабатывают информацию о стороне , что атакующий может знать о нашем источнике (как видно[7], такие экстракторы “среднего случая” очень удобны в криптографических приложениях), и также можем сделать вывод к существованию почти универсальных хеш-функций.

Работа со связями

Хаст[23] также заметил, что для некоторых криптографических приложений, соответствующие атакующие соответствуют ограниченным классам отличительных признаков, которые позволяют им получить улучшенные оценки безопасности, тогда как хардкорный бит Голдрейч-Левина[24] используется в качестве “вычислительного” экстрактора случайности. Этот результат несравним с нашим. С одной стороны, мы рассматриваем общие (мультиразрядные) основанные на LHL экстракторы, а не только единственную разрядную функцию скалярного произведения (который является формой предиката Голдрейч-Левина). С другой стороны, Хаст работал в вычислительном урегулировании и должен был сделать явное сокращение с различающегося на прогнозирующее устройство источника , который не требуется в нашем урегулировании.

Мы также упоминали понятие среза экстракторов, определенных Радхакришнаном и Та-Шма[17], который ограничивает тип статистических испытаний "редких" отличительных признаков. В меру нашего понимания это определение не было мотивировано приложениями, а скорее было удобной “параметризацией” на дороге к другим результатам. Однако, это понятие примерно соответствуют урегулированию ключевой деривации для приложений аутентификации, когда атакующий редко успешно выполняет свою цель. Интересно, Радхакришнан и Та-Шма[17] показали, что нижняя граница потери энтропии части экстракторов (нижняя из общих экстракторов) соответствует нижней границе экзистенциальной конструкции. Как выяснилось, наш улучшенный LHL сразу уступает дорогу конструктивному, чтобы соответствовать этой нижней границе, показывая, что основанные на LHL экстракторы - оптимальные экстракторы части с точки зрения потери энтропии. Эта связь более подробно описана в полной версии данной статьи[25].

В совсем другом (некриптографическом) контексте создания хэш-таблиц, Митзенмачер и Вахдан[26] также заметили, что улучшенные границы в “потере энтропии” могли быть получены, когда стандартное отклонение “различий” - гораздо меньше, чем 1. В их урегулировании потери энтропии была минимальная энтропия, требуемая от входного потока хорошего хеширования, и различия были характеристической функцией ряда занятых блоков.

Отметим, что наш “беспроигрышный” результат для подхода "расширение для извлечения" похож по духу на несколько других “беспроигрышных” результатов[27][28][29][30], где (гипотетический) противник для одной задачи превращен в “удивительно полезный” протокол для казалось бы, несвязанных задач. Среди вышеупомянутого результат, наиболее близкий к нашему[27], тот, где PRG используется для расширения ключа для “прямого безопасного хранения”, который является понятием, связанным с “локально вычислимыми” экстракторами.

С более практической стороны наших результатов в частности для манипуляции деривацией, стоит упомянуть работу[5][31], которая анализирует конструкции ключевых функций деривации (KDFs) на основе криптографических хеш-функций. Эти конструкции не используют стандартные, универсальные предположения, такие как псевдослучайность, но основываются на определенных режимах операций на их функции сжатия и полагаются на выделенных, иногда идеализируемых предположениях. В таких идеализированных предположениях эти схемы поддерживают ситуации, где KDF должен быть смоделирован как случайный оракул, или где у источника есть только “энтропия непредсказуемости”[32]. С другой стороны, за пределами случайной эвристики оракула, большой части анализа[5][31] изученные достаточные условия на функции сжатия и/или источника вводят распределение, при котором криптографические хеш-функции “достаточно универсальны”, чтобы применить стандартный LHL. Также, эти исследования страдают теми же недостатками, как и любой другой основанный на LHL экстрактор. В частности, наши результаты относительно улучшения потери энтропии для основанных на LHL экстракторов должны улучшить результаты[5][31], в то время как наши результаты на расширении для извлечения могли бы быть рассмотрены как частичное оправдание эвристики, где функция сжатия фиксированной длины описания заменена случайным числом в большинстве (но не во всех) исследований.[5][31]

Стандартный Лефтовер Хеш Лемма

Обозначения. Для множества , мы позволим обозначать равномерное распределение . Для целого числа , мы позволим обозначить равномерное распределение , строки битов длиной . Для распределения случайной переменной мы пишем , для обозначения выборки случайного согласно . Для мы пишем как сокращение для .

Минимальная энтропия и Экстракторы. Минимальная энтропия случайной переменной определена как . В криптографических приложениях часто используется средняя минимальная энтропия случайной переменной обусловленной на другой случайной переменной . Это выглядит так:

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

Мы обозначим преимущество схемы в различении случайных переменных . Статистическое расстояние между двумя случайными переменными определено как:

где максимум берется по всем (потенциально неограниченным вычислительно). При данной информации о стороне , мы пишем и как сокращения для соответственно.

Экстрактор[3] может быть использован для извлечения равномерной случайности из слабо - случайного значения, у которого, как предполагается, есть достаточная минимальная энтропия. Наше определение соответствует тому[7], что определено в терминах условной мин-энтропии.

Определение 1 (Экстракторы). Эффективная функция (средний случай, сильный) () - экстрактор (для пространства ). Если для всех таким образом, что распределен по и , мы получаем:

где обозначает (названный отбором). Значение означает потерю энтропии , и значение – продолжительность отбора .

  • Универсальный Хэш и Лефтовер Хэш Лемма. Теперь напомним определение универсального хеширования и Лефтовер Хэш Леммы [18], которое утверждает, что универсальные хеш-функции – также являются хорошими экстракторами.

Определение 2 (-Универсальная, Хеширующая). Семейство (детерминированных) функций : является -Универсальным семейством хэша (на пространстве ). Если для любого мы получаем ,тогда , и мы можем сказать, что универсален.

Мы можем наконец утвердить Лефтовер Хэш Лемму (LHL). (Появились многократные версии этой леммы; мы используем формулировку[33], дополненную[7] для случая условной энтропии; см.[1] и ссылки там же для более ранних формулировок).

Лемма 1 (Лефтовер Хэш Лемма). Предположим, что семейство функций , тогда - универсальное семейство хеша. Тогда экстрактор , где - универсальный , () - экстрактор, где (напомним, потеря энтропии). В частности универсальная хеш-функция дает - экстракторы.

Сокращение потери энтропии

Как мы уже упоминали, энтропийная потеря оптимальна, когда речь идет об общих отличительных признаках [17]. Как мы показываем, в различных криптографических сценариях, мы заботимся только о нескольких ограничительных классах отличительных признаков, которые позволяют нам снизить потерю энтропии для таких приложений.

Ниже, мы приведем обобщенный LHL (Теорема 1), которое будет включать новый термин, измеряющий стандартное отклонение различных преимуществ, и затем получим некоторые полезные особые случаи (Теорема 2). В Разделе 3.1, мы затем применим наше более трудное, обязанное получить улучшенные границы потерь энтропии для различных криптографических приложений, включая границы для всех приложений аутентификации (Теорема 3) и некоторых приложений кондифенциальности, включая выбранный открытый текст безопасного шифрования (Теорема 4) и слабый PRFs. В Разделе 3.2 мы далее расширим наши результаты, чтобы получить универсальную ключевую функцию деривации с улучшенной энтропийной потерей для любого вычислительно безопасного применения, включая поточные шифры и PRFs.

Вероятность коллизии и -дисперсия. Учитывая распределение , его вероятность коллизии . Учитывая совместное распределение , мы позволяем . Мы также используем , чтобы обозначить распределение вероятностей каждой первой выборки , но тогда заменяется независимой, универсальной выборкой от . Наконец, учитывая случайную переменную и постоянную , мы определяем его -вариацию как и -стандартную деривацию как . Когда , мы изменяем стандартную вариацию и стандартное различие и ,и заметьте, что это самые маленькие значения для и . Однако, мы позже сочтем что проще использовать (немного более слабые) границы, полученные с определенными значениями

Мы начнем с полезной независимой интересной леммы, которая обобщает Лемму 4.5.1.[26]

Лемма 2. Предположим, являются парой коррелированого распределения случайных переменных на набор . Тогда для любой (детерминированной) действительной функции и любой константы , мы имеем:

Доказательство этой леммы можно найти в полной версии данной статьи[25]. Полезная функция связи, представленной, в Уравнении (2), исходит из того, что значение не зависит от фактического распределения , заменяет равномерное распределение, в то время как значение не зависит от функции , чье среднее число мы пытаемся сохранить (используя вместо ). В частности, мы получаем последовательное заключение, которое позволит нам в конечном счете получить все наши улучшенные границы.

Теорема 1 (Обобщенный LHL). Пусть - некоторое совместное распределение по семейство универсальных хеш-функций, - случайный член , и пусть – потеря энтропии.

Тогда, с любой постоянной и любого (возможно вероятностного) различителя , мы имеем:

Доказательство теоремы можно найти в полной версии этой статьи[25]. Уравнение (3) ограничивает преимущество в различении реальной и извлеченной случайности, использующей два термина. Второй член (под квадратным корнем) зависит от универсальности и энтропийной потери (но не от ). Новый термин - -стандартное отклонение , которое мы просто назовем -стандартное-отклонение и обозначим . Интуитивно, оно измеряет, насколько “сконцентрирован” ожидаемый результат к определенному значению в “идеальном месте” (при подаче , а не ). Мы видим, что для любого и любого , -стандартное-отклонение . Включение этой тривиальной связи в Уравнении (3) отменяет зависимость от , и (по существу) дает нам утверждение стандартного LHL из Леммы 1. Как упомянуто выше, тем не менее, это вынуждает энтропийную потерю быть, по крайней мере, , чтобы достигнуть -безопасности. Ниже показано несколько особых случаев, когда верхняя граница примерно , что означает, что энтропийная потеря только должна быть примерно (скажем, совершенно универсальным ) для достижения -безопасности.

Теорема 2. Пусть - некоторое совместное распределение по - семейство - универсальных хеш-функций, - случайный член , - потеря энтропии и некоторый (возможно вероятностный) различитель. Затем для каждого из значений определенны сценарии (a) - (c) указанные далее:

(a) Предположим, что для определенного имеет следующее условие:

(b) Предположим, (где вероятность взята по и ).

(c) Для фиксированных , и , определяют различитель следующим образом. Во-первых, сделайте две независимых выборки . Затем если, вернитесь, возвращаясь в . Предположим далее, что

Доказательство этой Теоремы дано в полной версии[25]. В следующем разделе мы продемонстрируем использование Теоремы 2, концентрируясь на важном случае ключевой деривации, используя LHL, где значение будет по факту соответствовать “криптографической безопасности” приложения под рукой.

Улучшенный LHL для ключевой деривации

Рассмотрим любой криптографический примитивный (например, подпись, шифрование, и т.д.), который использует случайность , чтобы получить ее секретный ключ (и, публичности, в случае необходимости). Без потери публичности мы можем предположить, что сам – это секретный ключ. В “идеальном” соотношении совершенно универсален и независим от любой информации о стороне доступной атакующему. В” реальном урегулировании”, у ключевого владельца есть источник случайности, представленный случайной переменной и возможно коррелируемый с информацией о стороне атакующего . Тогда выбирается универсальная хеш-функция , используя (новую) общедоступную случайность и используется извлеченное значение как его ключ. Мы хотели бы утверждать что, если - “-безопасность” в идеальном месте (против атакующих с ресурсами менее ), то также “-безопасность” в реальном урегулировании (против атакующих с ресурсами менее ), где не намного больше, чем . Конечно, чтобы иметь надежду на достижение этого, должен быть “достаточно универсальным”, и должен быть “достаточно высоким”. Для параметризации этого, мы будем писать () - действительная модель, для обозначения реальной модели выше, где -универсальный и . Мы формализуем эту общую настройку подобным образом.

АБСТРАКТНЫЕ ИГРЫ БЕЗОПАСНОСТИ. Мы предполагаем, что безопасность определена с помощью интерактивной игры между вероятностным атакующим и вероятностным претендентом . Здесь следует думать о и как об определенных значениях хеш-функции и дополнительной информации, соответственно, и о как об определенном значении, используемом претендентом в алгоритме генерирования ключей . Заметим, что использует только секретный ключ и не зависит от и . В идеальной обстановке, где , атакующий не использует значения и (и так или иначе оптимальные значения и могут быть предрасположены в в неоднородной модели), все же, для удобства, мы все еще передадим и к для идеального урегулирования.

В конце игры, выводы немного -битны, где если , то атакующий “выиграл игру”. Так как фиксирован определением (например, выполняет игру нековкости для подписи или семантическую игру безопасности для шифрования, и т.д.), мы обозначаем D^ (r, h, z) (краткий обзор) различающийся, который моделирует всю игру между (h, z) и C(r) и выводит бит b, и WinА (Г, h, z) = PR [D^ (r, h, z) = 1] вероятность, которая (h, z) выигрывает игру против C(r). С этой нотацией вероятность выигрывания игры в “реальном урегулировании” представлена случайной переменной , и та же вероятность в идеальном урегулировании становится . Кроме того, различие между этими вероятностями - просто различающее преимущество сообщения обособленно реальной и извлеченной случайностью, когда даны :

Поскольку мы выравниваем затем по ширине, чтобы обсудить безопасность в реальном урегулировании, принимающем его безопасность в идеальном урегулировании, достаточно для нас утверждать, что вышеупомянутое преимущество различений “небольшое” для всех легальных атакующих . И так как безопасность будет обычно ограничивать силу атакующих (следовательно, также силу краткого обзора различающихся ), мы можем использовать результаты Теоремы 2, чтобы обсудить лучшие границы энтропийной потери .

Определение 3. Пусть для приложений непредсказуемости (подпись, MAC, односторонняя функция, и т.д.) и для приложений неразличимости (шифрование, псевдослучайная функция/перестановка, и т.д.). Зафиксируйте также: - семейство универсального хеша и совместное распределение , удовлетворяющее , так, чтобы реальное и идеальная модель были четко определены.

Мы говорим, что - это - безопасность в идеальной модели, если для всех атакующих с ресурсами меньше, чем , мы имеем

Точно так же - это - безопасность в реальной модели, если для всех атакующих есть ресурсы меньше, чем , мы имеем

Неравенство треугольника в сочетании с уравнением (6) немедленно вытекает в Следствие.

Лемма 3. Фиксированные и определений реальных и идеальных моделей. Предположим, что - безопасность в идеальной модели, и для всех атакующих с ресурсами меньше, чем (где ) мы имеем . Тогда это()-безопасность в ()-реальной модели.

Теперь мы готовы применить Лемму 3 и Теорему 2 к различным криптографическим примитивам . Ниже, мы устанавливаем постоянным управлением безопасностью (0 для непредсказуемости и 1/2 для приложений неразличимости). Из-за пространственного ограничения, мы оставляем приложение части (a) Теоремы 2 к так называемым “строго безопасным” примитивам, где (для некоторых и ) у любого атакующего есть преимущества больше, чем от до в части ключей , и перемещаются непосредственно в другие приложения, которые используют части (b) и (с) Теоремы 2. Также можно посмотреть несколько конкретных примеров в полной версии[25].

Улучшенная граница для непредсказуемых приложений. Проверив, аутентификация приложения соответствуют и включает схемы подписи, MACS, односторонние функции/перестановки, и т.д. В этом случае () - безопасность в идеальной модели подразумевает что для любого атакующего , . Ссылаясь на определение абстрактного различающегося , это то же самое что, , что именно является условием для части (б) Теоремы 2. Таким образом, комбинируя уравнения (4) с леммой 3, мы непосредственно получим:

Теорема 3. Фиксированные и определений реальных и идеальных моделей. Предположим аутентификацию примитивного (соответствующий ) () - безопасности в идеальной модели. Тогда это ()-безопасность в ()-реальной модели, где:

В частности если и , то . Кроме того, когда , безопасность связи значима даже при отрицательной энтропийной “потери” , когда один извлекает больше битов, чем минимальная энтропия и “заимствует дефицит безопасности” из идеальной безопасности .

Интуитивно, Теорема 3 фактически используется, поскольку для приложений аутентификации единственные заботы о различиях, которые почти никогда не выводят 1, так как атакующий почти никогда не подделывает успешно.

Улучшенное направление в некоторых неразличимых приложениях. Теперь рассмотрим более сложный случай неразличимости приложений, где . В целом мы не ожидаем выиграть у стандартного LHL, как проиллюстрировано примером шифра Вернама. Вполне удивительно, что для класса приложений, включая выбранную атаку простого текста (CPA) безопасное шифрование, можно все еще получить улучшенные границы по сравнению со стандартным LHL. В частности, пока примитивный позволяет атакующему “тестировать” свой успех прежде, чем принять “вызов” со стороны , мы все еще получаем значительные сбережения. Мы запускаем, определяя общий тип игр безопасности, применяя наш метод.

Бит-ролевые Игры. Как обычно, в игру играет атакующий и претендент . У игры может быть произвольная структура, кроме победы, условие определено следующим образом. В некоторый момент просит у “задание”. зеркально отражает случайный бит и отправляет значение . Игра продолжается произвольным способом и заканчивается созданием предположения . Побеждает тот, у кого .

До сих пор это все еще включает все стандартные игры неразличимости, включая шифр Вернама. Дополнительное предположение, которое мы делаем, является следующим. Для любого допустимого атакующего имеющего меньше ресурсов, чем существует другой возможный атакующий (имеющий больше ресурсов ) таким образом что:

(1) Выполнение между и определяет четыре бита , таким образом, что совместное распределение () совпадает с двумя независимыми кортежами () полученный при выполнении с

(2) Биты являются точно секретным битом и предположением , что одерживает победу эквивалентно

(3) учится если прежде, чем выводится .

Мы назовем такие игры неразличимости ()-имитация. В полной версии[25] мы показываем общий результат, утверждая улучшенные границы энтропийной потери для любой () - имитации приложения, и также показываем, что CPA-безопасность (публичный или симметричный ключ) схемы шифрования имитации, где как ожидалось “ресурсы” примерно удвоены по сравнению с . (Интуитивно, атакующий может мысленно увидеть победит ли.) В частности мы получаем следующую теорему как следствие этого общего результата:

Теорема 4. Фиксированные и определений реальных и идеальных моделей, и установка .

Предположим, что - схема шифрования с открытым ключом, которая является -безопасностью, в идеальной модели, против атакующих со временем выполнения , где - время выполнения процесса шифрования. Тогда - это -безопасность, в ) - реальной модели, против атакующих со временем выполнения

Точно так же предположим, что - схема шифрования с симметричным ключом, которая является -безопасностью, в идеальной модели, против атакующих со временем выполнения и делающий запрос шифрования. Тогда - это -безопасность, в ) - реальной модели, против атакующих со временем выполнения и делающий запросы шифрования.

Ограничения и Расширения. К сожалению, несколько других примитивов неразличимости, таких как псевдослучайные генераторы, функции или перестановки, кажутся, не имитированными. Проблема, кажется, находится в проверке условия победы (условие (3) из имитации), так как это должно быть сделано относительно фактического секретного ключа r, не известного атакующему. Для PRFs (или PRPs), заманчиво решить проблему при помощи эквивалентного определения, где атакующий может изучить значение PRF в любой точке, но тогда, проблема в том, чтобы отличить значение PRF в не запрошенной точке от случайного. Несмотря на то, что этот вариант позволяет атакующему проверять условие победы во время первого “виртуального” выполнения, это теперь создает различную проблему в этом, точка проблемы во время второго “фактического” выполнения, возможно, была запрошена во время первого показа, делая такого атакующего недействительным.

Интересно, вышеупомянутое “фиксирует” работы для полезной релаксации PRFs, известного как слабый PRFs (wPRFs). Здесь атакующий только добирается, чтобы видеть значения PRF в нескольких случайных точках и должен отличить новое значение от случайного. Принимая достаточно большой входной домен, вероятность коллизии между значениями PRF показала на первоначальном показе и возможностями во втором периоде, незначительно, который позволяет завершать (допустимое) моделирование. Кроме того, он работает на немного более сильную релаксацию PRFs, известного как случайная проблема PRFs. Как wPRFs, получает в качестве задачи в реальном или на случайных оценок PRF в случайной точке, но может дополнительно запросить PRF в произвольных точках, отличных от точки проблемы. В Разделе 3.2 мы покажем, что wPRFs - все, что мы должны применить к нашим результатам к универсальной ключевой функции деривации.

Универсальная ключевая функция деривации

До сих пор мы обсуждали приложения нашей обобщенной Лефтовер Хеш Леммы и Теоремы 2 к деривации криптографических ключей в энтропии - ограничительные среды для определенных приложений. Несмотря на то, что наш анализ охватывает много таких приложений, он не охватывает все, включая PRFs и поточные шифры. В этом разделе мы сделаем простое наблюдение, которое позволит нам избавиться от этого ограничения и спроектировать универсальную ключевую функцию деривации (KDFs), которая (в вычислительном отношении) безопасна для любого криптографического приложения, все еще обладая той же экономией энтропийной потери. Идея состоит в том, чтобы составить универсальные хеш-функции слабого PRF (wPRF), где случайный ввод к wPRF теперь становится частью отбора экстрактора, и использовать тот факт, что wPRFs подпадают под класс имитационных приложений, как определено в Разделе 3.1.

В частности мы определяем KDF на основе -универсального хеш семейства с -битными выводами, и wPRF , принимает -битный вход , и -битный ключ , а также выводящий -бит , следующим образом. Публичный отбор для KDF является парой , где - случайная универсальная функция от , и - случайный элемент в домене . Затем мы определяем ; т.е., первоначально извлеченное значение используется в качестве ключа wPRF, который используется, чтобы оценить и .

Мы также заметили, что, если нужно извлечь многократные ключи для нескольких приложений, мы можем просто использовать вывод нашего вычислительного KDF как отбор регулярного PRG или PRF, так как такие приложения теперь “скрыты”.

Примечание 1. В случае получения многократных ключей, как указано выше, мы видим, что шаг wPRF не необходим, если все ключи для криптографических приложений, покрыты нашим методом (т.е., строго защищены, непредсказуемы, или имитированы в примитивы). А именно, в таком случае мы можем непосредственно использовать первоначально извлеченный ключ в качестве отбора для (регулярного) PRF/PRG, чтобы получить все требуемые ключи. Это позволяет нам избегать увеличения продолжительности отбора на k биты и сохраняет одно приложение wPRF. Доказательство этого требования следует простым гибридным параметром (который мы опускаем). В целом, тем не менее, находящееся в wPRF решение предпочтительно, поскольку оно добавляет значительную общность по относительно умеренной стоимости.

Сокращение продолжительности отбора

В этом разделе мы изучим обоснованность естественного подхода "расширение для извлечения", описанного во Введении, учитывая наш отрицательный результат в Разделе 4.1 и наши два положительных результата в Разделе 4.2 и Разделе 4.3.

Незначительные и союзники. Мы используем для обозначения параметра безопасности. Функция незначительна если для любого есть , таким образом что для всего . Наоборот, ненезначителен, если для определенного у нас есть для бесконечно многих . На протяжении всего, обозначает незначительную функцию в .

Функция подавляется если незначительна. Функция если для некоторого есть , таким образом что для всего . Обратите внимание на то, что ненезначительное не то же самое, что примечательное. Например, ненезначительно, но и не примечательно.

Вычислительные Экстракторы и PRGs. Напомним, что мы обозначаем преимущество схемы в различении случайных переменных и . Пусть обозначает класс всех вероятностных схем размера . мы обозначаем вычислительное расстояние и , здесь максимум по . Когдав неограниченном, мы восстанавливаем понятие статистического расстояния (). То, когда и будут семействами распределений, индексированными параметром безопасности , мы скажем, что и в вычислительном отношении неразличимы, обозначая , если для каждого многочлена .

Определение 4 (Вычислительный Экстрактор). Мы говорим, что эффективная функция: (средний случай, сильный) вычислительный -экстрактор (для пространства ), если везде наиболее эффективны таким образом, что распределен по и (здесь все индексированы параметром безопасности ).

Определение 5 (Псевдослучайный Генератор). Возрастающая функция длины псевдослучайный генератор (PRG) если . Мы также говорим, что Prg () - безопасность если .

Вычислительные Экстракторы с Короткими Отборами? Мы готовы формализовать наш основной вопрос: действительно ли можно безопасно развернуть отбор экстрактора, используя PRG?

Гипотеза 1 [Расширение для извлечения], Если Ext - экстрактор с длиной отбора , где незначителен и - псевдослучайный генератор, тогда Ext' определяется, как

это вычислительный m-экстрактор.

Контрпример: Расширение Отбора Небезопасно в целом

В этом разделе мы показываем, что к сожалению Гипотеза 1 неправильная в целом.

Теорема 5 (Гипотеза 1, неправильно принимающая DDH). Под предположением DDH, существует псевдослучайный генератор Prg(.) и сильный экстрактор Ext(.;.) (который является совершенно универсальной хеш-функцией) таким образом что , может эффективно отличаться от универсальной формы на любом входном распределении (т.е. Ext' не является вычислительным экстрактором.)

Доказательство (Теоремы 5). Позвольте G быть главной циклической группой порядка p с генератором g, где проблема DDH трудна. Тогда определяется как

это и есть безопасный псевдослучайный генератор[34]. Тогда :

Можно легко заметить, что Ext - совершенно универсальная хеш-функция от (и из Леммы 1, сильный () - экстрактор). Теперь рассмотрим распределение:

Распределение (8) не псевдослучайное как любой кортеж формы (8) удовлетворяет , который может быть эффективно проверен, в то время как случайное распределение удовлетворит это отношение с вероятностью 1/p.

Расширение Отбора Безопасно при Извлечении Нескольких Битов

Следующей теоремой Гипотеза "расширение для извлечения" действительно работает, если псевдослучайный генератор Prg, используемый для расширения, достаточно силен. Требуемая сила зависит по экспоненте от продолжительности вывода v экстрактора. Доказательство следующей Теоремы дано в полной версии этой статьи[25]

Теорема 6. Пусть (m, e) - экстрактор с временем выполнения и () - псевдослучайный генератор, для некоторых:

Тогда , () - экстрактор. В частности если время работы Ext - полиномиал в k, его ошибка e (k) = negl (k), его выходной размер , и Prg безопасен против полиномиала (в k) размер различающийся, то Ext' (m, e') - экстрактор для e' (k) = negl (k).

Расширение Отбора Безопасно в minicrypt

Прежде, чем мы можем сформулировать основной результат этого параграфа, нам нужны еще несколько определений.

Бит соглашение. Бит- соглашение - протокол между двумя эффективными сторонами, которые мы именуем как Элис и Боб. Они получают параметр безопасности k в унарном (обозначим ) как общий ввод, и могут связаться по подлинному каналу. Наконец, Элис и Боб выводят немного и , соответственно. Протокол корреляции e = e (k), для всего k, . Кроме того, у протокола есть безопасность , если для каждого эффективного противника Eve, который может наблюдать целую коммуникацию C, и для всего k, .

Ключевое соглашение и PKE. Если e (-) и (-) подавляющие то, такой протокол достигает согласования ключей. Используя параллельное повторение и усиление конфиденциальности, известно, что любой протокол[35][36], который достигает разрядного соглашения со значимой корреляцией e (-) и подавляющей безопасности (-), может быть превращен в протокол согласования ключей, не увеличивая число раундов. Протокол согласования ключей с 2 сообщениями эквивалентен шифрованию с открытым ключом (PKE). Доказательство следующей Теоремы дано в полной версии статьи.[25]

Теорема 7 (Гипотеза 1 содержит в minicrypt). Если существует безопасный псевдослучайный генератор Prg и сильный экстрактор Ext, где Ext (.;.) = Ext (Prg (.);.) не, вычислительный экстрактор, тогда протокол из рисунка 1 - двухбитное сообщение - протокол соглашения со значимой корреляцией и подавляющей безопасностью (и таким образом подразумевает PKE).

Примечание 2. В вышеупомянутой теореме, не являющейся безопасным вычислительным экстрактором, означает, что существует эффективная универсальная форма D, которая может отличить Ext (Prg (.);.) со значимым преимуществом (в параметре безопасности k). Если Ext (Prg (.);.)небезопасен против неоднородных противников, тогда также получающийся протокол (который использует D), будет неоднородным. Если различающийся D только будет иметь не - незначительное преимущество (т.е. только работает на бесконечно многих, но не на всех параметрах безопасности k), то также протокол будет работать на бесконечно многих k. Эта проблема свойственна от взаимовыгодных результатов типа, где противник превращен в “полезный” протокол.[27] Это базируется на том факте, что в криптографии мы обычно помещаем слабые требования для противников, чтобы считаться эффективными (может быть неоднородным и только иметь не - незначительное преимущество), тогда как мы обычно требуем от практических алгоритмов, чтобы быть универсальными и безопасными для всех (достаточно больших) параметров безопасности.

Рис. 1. Немного протокола соглашения от любого Prg, Ext, которые составляют контрпример (через различный D) к Гипотезе 1.

Мы получаем следующее заключение, доказательство которого непосредственно на рисунке 1.

Заключение 1.Предположим, что Prg - безопасный псевдослучайный генератор. Предположим далее, что там не существует никакая схема шифрования с открытым ключом (с ненезначительным разрывом между безопасностью и правильностью дешифрования) с псевдослучайными шифрованными текстами, секретный ключ которых - отбор Prg и чей то открытый ключ - вывод Prg. Тогда гипотеза "расширение для извлечения" является истиной для Prg.

ОБСУЖДЕНИЕ.

Заключение 1 уменьшает разумность подхода, "расширение для извлечения" до невозможности построения шифрования с открытым ключом от данного PRG очень определенным способом, где шифрованные тексты псевдослучайные и, что еще более важно, алгоритм генерации ключей выбирает случайный s и устанавливает sk = s, pk = Prg (s). Насколько нам известно, это предположение невозможности кажется вероятным для “практического” PRGs, такого как AES. Например, не только нет никакой конструкции черного ящика PKE (или согласование ключей) от один PRG, как показывают Импальяццо и Радич[37], но, фактически, это есть некоторая вычислительная модель / класс сложности (например, возможно некоторое расширение BQP или AM coAM), который достаточно способен повредить все схемы с открытым ключом, но не достаточно мощный, чтобы повредить AES. Если это так, тогда основы AES разворачивают и извлекают схему, безопасно относительно всех эффективных входных дистрибутивов и различий полностью непротиворечивых современным знаниям, что эти две задачи отделимы, в том смысле, что (даже те, которые основываются на инструментах с открытым ключом, таких как факторинг, решетки и т.д.). Кроме того, мы не знаем конструкции черного ящика PKE от PRG и любого другого “криптомании” предположения (как неинтерактивные доказательства нулевого знания, полностью гомоморфное или основанное на идентификационных данных шифрование, и т.д.), где открытый ключ PKE - просто вывод PRG. Подводя итог, наши результаты дают убедительные доказательства, что подход "расширение для извлечения" является безопасным использованием любого практического PRG (как AES), несмотря на то, чтобы быть (обычно) небезопасным в теории.

Подтверждения: Мы хотели бы благодарить Рассела Импэглиэззо и Ронена Шэлтила за полезные обсуждения.

Список литературы

  • Boaz Barak, Yevgeniy Dodis, Hugo Krawczyk, Olivier Pereira, Krzysztof Pietrzak,Francois-Xavier Standaert, and Yu Yu. Leftover hash lemma, revisited. Cryptology ePrint Archive, Report 2011/088, 2011. http://eprint.iacr.org/.
  • Boaz Barak and Shai Halevi. A model and architecture for pseudo-random generation with applications to /dev/random. In ACM CCS 2005.
  • Boaz Barak, Ronen Shaltiel, and Eran Tromer. True random number generators secure in a changing environment. In CHES 2003.
  • Charles H. Bennett, Gilles Brassard, and Jean-Marc Robert. Privacy amplification by public discussion. SIAM Journal on Computing, 17(2):210–229, 1988.
  • Xavier Boyen, Yevgeniy Dodis, Jonathan Katz, Rafail Ostrovsky, and Adam Smith. Secure remote authentication using biometric data. In EUROCRYPT 2005.
  • Ran Canetti, Yevgeniy Dodis, Shai Halevi, Eyal Kushilevitz, and Amit Sahai. Exposure-resilient functions and all-or-nothing transforms. In Eurocrypt 2000.
  • J.L. Carter and M.N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18:143–154, 1979.
  • C?eline Chevalier, Pierre-Alain Fouque, David Pointcheval, and S?ebastien Zimmer. Optimal randomness extraction from a diffie-hellman element. In EUROCRYPT 2009.
  • Yevgeniy Dodis, Rosario Gennaro, Johan H°astad, Hugo Krawczyk, and Tal Rabin. Randomness extraction and key derivation using the cbc, cascade and hmac modes. In CRYPTO 2004.
  • Yevgeniy Dodis, Jonathan Katz, Leonid Reyzin, and Adam Smith. Robust fuzzy extractors and authenticated key agreement from close secrets. In CRYPTO 2006.
  • Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM Journal on Computing, 38(1):97–139, 2008.
  • Bella Dubrov and Yuval Ishai. On the randomness complexity of efficient sampling. In STOC 2006.
  • Stefan Dziembowski. On forward-secure storage. In CRYPTO 2006.
  • Rosario Gennaro, Hugo Krawczyk, and Tal Rabin. Secure hashed diffie-hellman over non-ddh groups. In EUROCRYPT 2004.
  • O. Goldreich and L. Levin. A hard-core predicate for all one-way functions. In STOC 1989.
  • V. Guruswami, C. Umans, and S. Vadhan. Unbalanced expanders and randomness extractors from parvaresh–vardy codes. J. ACM, 56(4), 2009.
  • Gustav Hast. Nearly one-sided tests and the goldreich levin predicate. J. Cryptology,17(3):209–229, 2004.
  • J. H°astad, R. Impagliazzo, L.A. Levin, and M. Luby. Construction of pseudorandom generator from any one-way function. SIAM Journal on Computing,28(4):1364–1396, 1999.
  • Thomas Holenstein. Key agreement from weak bit agreement. In STOC 2005.
  • Thomas Holenstein. Strengthening Key Agreement using Hard-Core Sets. PhD thesis, ETH Zurich, Zurich, Switzerland, 2006.
  • Chun-Yuan Hsiao and Leonid Reyzin. Finding collisions on a public road, or do secure hash functions need secret coins. In CRYPTO 2004.
  • Russell Impagliazzo. A personal view of average-case complexity. In Structure in Complexity Theory Conference, pages 134–147, 1995.
  • Russell Impagliazzo and Steven Rudich. Limits on the provable consequences of one-way permutations. In STOC 1989.
  • Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Cryptography with constant computational overhead. In STOC 2008.
  • Hugo Krawczyk. Cryptographic Extraction and Key Derivation: The HKDF Scheme. In CRYPTO 2010.
  • Ueli Maurer and Stefan Wolf. Privacy amplification secure against active adversaries. In CRYPTO 1997.
  • Michael Mitzenmacher and Salil P. Vadhan. Why simple hash functions work: exploiting the entropy in a data stream. In SODA 2008.
  • Moni Naor and Omer Reingold. Number-theoretic constructions of efficient pseudorandom functions. In FOCS 1997.
  • Moni Naor and Gil Segev. Public-key cryptosystems resilient to key leakage. In CRYPTO 2009.
  • Wim Nevelsteen and Bart Preneel. Software performance of universal hash functions. In EUROCRYPT 1999
  • Noam Nisan and David Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 52(1):43–53, 1996.
  • Krzysztof Pietrzak. Composition implies adaptive security in minicrypt. In EUROCRYPT 2006.
  • Krzysztof Pietrzak and Johan Sj?odin. Weak pseudorandom functions in minicrypt. In ICALP 2008.
  • Jaikumar Radhakrishnan and Amnon Ta-Shma. Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM Journal on Computing, 13(1):2–24, 2000.
  • Renato Renner and Stefan Wolf. Unconditional authenticity and privacy from an arbitrarily weak secret. In CRYPTO 2003.
  • Ronen Shaltiel. Recent developments in explicit constructions of extractors. Bulletin of the EATCS, 77:67–95, 2002.
  • D. R. Stinson. Universal hashing and authentication codes. Designs, Codes, and Cryptography, 4(4):369–380, 1994.
  • D. R. Stinson. Universal hash families and the leftover hash lemma, and applications to cryptography and computing. Journal of Combinatorial Mathematics and Combinatorial Computing, 42:3–31, 2002. Available at http://www.cacr.math.uwaterloo.ca/~dstinson/publist.html.

Ссылки

  1. 1,0 1,1 1,2 J. H°astad, R. Impagliazzo, L.A. Levin, and M. Luby. Construction of pseudorandom generator from any one-way function. SIAM Journal on Computing,28(4):1364–1396, 1999.
  2. 2,0 2,1 J.L. Carter and M.N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18:143–154, 1979.
  3. 3,0 3,1 Noam Nisan and David Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 52(1):43–53, 1996.
  4. Charles H. Bennett, Gilles Brassard, and Jean-Marc Robert. Privacy amplification by public discussion. SIAM Journal on Computing, 17(2):210–229, 1988.
  5. 5,0 5,1 5,2 5,3 5,4 5,5 Hugo Krawczyk. Cryptographic Extraction and Key Derivation: The HKDF Scheme. In CRYPTO 2010.
  6. Rosario Gennaro, Hugo Krawczyk, and Tal Rabin. Secure hashed diffie-hellman over non-ddh groups. In EUROCRYPT 2004.
  7. 7,0 7,1 7,2 7,3 Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM Journal on Computing, 38(1):97–139, 2008.
  8. Xavier Boyen, Yevgeniy Dodis, Jonathan Katz, Rafail Ostrovsky, and Adam Smith. Secure remote authentication using biometric data. In EUROCRYPT 2005
  9. Boaz Barak and Shai Halevi. A model and architecture for pseudo-random generation with applications to /dev/random. In ACM CCS 2005.
  10. Boaz Barak, Ronen Shaltiel, and Eran Tromer. True random number generators secure in a changing environment. In CHES 2003.
  11. Ueli Maurer and Stefan Wolf. Privacy amplification secure against active adversaries. In CRYPTO 1997.
  12. Yevgeniy Dodis, Jonathan Katz, Leonid Reyzin, and Adam Smith. Robust fuzzy extractors and authenticated key agreement from close secrets. In CRYPTO 2006.
  13. Moni Naor and Gil Segev. Public-key cryptosystems resilient to key leakage. In CRYPTO 2009.
  14. 14,0 14,1 14,2 D. R. Stinson. Universal hashing and authentication codes. Designs, Codes, and Cryptography, 4(4):369–380, 1994.
  15. Wim Nevelsteen and Bart Preneel. Software performance of universal hash functions. In EUROCRYPT 1999
  16. Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Cryptography with constant computational overhead. In STOC 2008.
  17. 17,0 17,1 17,2 17,3 17,4 17,5 Jaikumar Radhakrishnan and Amnon Ta-Shma. Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM Journal on Computing, 13(1):2–24, 2000.
  18. Ran Canetti, Yevgeniy Dodis, Shai Halevi, Eyal Kushilevitz, and Amit Sahai. Exposure-resilient functions and all-or-nothing transforms. In Eurocrypt 2000.
  19. Renato Renner and Stefan Wolf. Unconditional authenticity and privacy from an arbitrarily weak secret. In CRYPTO 2003.
  20. V. Guruswami, C. Umans, and S. Vadhan. Unbalanced expanders and randomness extractors from parvaresh–vardy codes. J. ACM, 56(4), 2009.
  21. Ronen Shaltiel. Recent developments in explicit constructions of extractors. Bulletin of the EATCS, 77:67–95, 2002
  22. Russell Impagliazzo. A personal view of average-case complexity. In Structure in Complexity Theory Conference, pages 134–147, 1995.
  23. Gustav Hast. Nearly one-sided tests and the goldreich levin predicate. J. Cryptology,17(3):209–229, 2004.
  24. O. Goldreich and L. Levin. A hard-core predicate for all one-way functions. In STOC 1989.
  25. 25,0 25,1 25,2 25,3 25,4 25,5 25,6 25,7 Boaz Barak, Yevgeniy Dodis, Hugo Krawczyk, Olivier Pereira, Krzysztof Pietrzak,Francois-Xavier Standaert, and Yu Yu. Leftover hash lemma, revisited. Cryptology ePrint Archive, Report 2011/088, 2011. http://eprint.iacr.org/.
  26. 26,0 26,1 Michael Mitzenmacher and Salil P. Vadhan. Why simple hash functions work: exploiting the entropy in a data stream. In SODA 2008.
  27. 27,0 27,1 27,2 Stefan Dziembowski. On forward-secure storage. In CRYPTO 2006.
  28. Krzysztof Pietrzak. Composition implies adaptive security in minicrypt. In EUROCRYPT 2006.
  29. Bella Dubrov and Yuval Ishai. On the randomness complexity of efficient sampling. In STOC 2006.
  30. Krzysztof Pietrzak and Johan Sj?odin. Weak pseudorandom functions in minicrypt. In ICALP 2008.
  31. 31,0 31,1 31,2 31,3 Yevgeniy Dodis, Rosario Gennaro, Johan H°astad, Hugo Krawczyk, and Tal Rabin. Randomness extraction and key derivation using the cbc, cascade and hmac modes. In CRYPTO 2004.
  32. Chun-Yuan Hsiao and Leonid Reyzin. Finding collisions on a public road, or do secure hash functions need secret coins. In CRYPTO 2004.
  33. D. R. Stinson. Universal hash families and the leftover hash lemma, and applications to cryptography and computing. Journal of Combinatorial Mathematics and Combinatorial Computing, 42:3–31, 2002. Available at http://www.cacr.math.uwaterloo.ca/~dstinson/publist.html.
  34. Moni Naor and Omer Reingold. Number-theoretic constructions of efficient pseudorandom functions. In FOCS 1997.
  35. Thomas Holenstein. Strengthening Key Agreement using Hard-Core Sets. PhD thesis, ETH Zurich, Zurich, Switzerland, 2006.
  36. Thomas Holenstein. Key agreement from weak bit agreement. In STOC 2005.
  37. Russell Impagliazzo and Steven Rudich. Limits on the provable consequences of one-way permutations. In STOC 1989.