Введение в современную криптографию
Эксперимент привязки обязательства Binding ACom (n)
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- DEFINITION 5.13
- Ссылки и дополнительная литература
| Эксперимент привязки обязательства Binding ACom (n):
1. Параметры params ← Gen(1n) генерируются. 2. Aполучает входные params и выводит (com, m, r, mr, rr). 3. Результат эксперимента - определнн как 1, если и только если m ƒ= mr и Com(params, m; r) = com = Com(params, mr; rr). DEFINITION 5.13 Схема обязательства Com является защищенной, если для всех PPT злоумышленников A существует пренебрежимо малая функция negl такая, чтобы Легко сконструировать защищенную схему обязательства из случайного ора- кула H. Чтобы привязаться к сообщению m, отправитель выбирает универслаь- ное значение r ∈ {0, 1}n и выводит com := H(m||r). (В модели со случайным оракулом Gen и params не нужны, так как H по сути служит как публичные параметры схемы.) Наглядно, сокрытие проистекает из факта, что злоумыш- 208 ленник опрашивает H(>||r) с только лишь пренебрежимо малой вероятностью (так как r является универсальной n-битной строкой); если он ни разу не сделает запрос этой формы, тогда H(m»r) ничего не откроет о m. Привязка проистекает из факта, что H является стойкой к коллизиям. Схемы обязательств могут быть сконструированы без случайных оракулов (фактически, из однонаправленной функции), но подробности находятся за пределами данной книги. Ссылки и дополнительная литература Стойкие к коллизиям хэш-функции были формально определены Дамгордом [52]. Дополнительное описание касательно понятий о безопасности для хэш- функций помимо стойкости к коллизиям можно найти в [120, 150]. П реобразова- ние Меркле-Дамгорда было представлено отдельно Дамгордом и Меркле [53, 123] HMAC был представлен Белларом и др. [14], а позже и стандартизирован [131]. Атаки «дней рождения» малого пространства, описанные в Разделе 5.4.2, опираются на алгоритм нахождения цикла Флойда (Floyd). Соответстующие алгоритмы описаны по сслыке: http://en.wikipedia.org/wiki/Cycle_detection. Идея нахожде- ния значимых коллизий с использований атак малого пространства по Ювалю (Yuval) [180]. Ключ параллелизации атак нахождения коллизий, которые могут предложить зна- чительные ускорения на практике, описана в [170]. Компромиссы простран- ства/времени для функции инверсии были представлены Хеллманом (Helman) [87] с практическими улучшениями, не описанными здесь, предоставленными Ривестом (Risvest) (неопубликовано) и Oechslin [134]. Первая формальная трактовка модели со случайным оракулом была дана Бел- ларом и Рогавэем [21], хотя идея использования «произвольно ищущей» функ- ции в криптографических приложениях была предложена ранее в значительной степени Фиатом (Fiat) и Шамиром (Shamir) [65]. Правильная реализация слу- чайного оракула на основе конкретной криптографической хэш-функции опи- сана в [21, 22, 23, 48]. Фундаментальный негативный результат касательно мо- дели со случайным оракулом принадлежит Канетти (Canetti) и др. [41], который показал (изобрел) схемы, которые защищены в модели со случайным оракулом, но незащищены для любых конкретных реализаций случайного оракула. Деревья Меркле были представлены в [121]. Установление ключа, использу- емое на практике, включая HKDF, PBKDF2 и bcrypt. См. [109] для формальной трактовки проблемы и анализа HKDF. |