Введение в современную криптографию


Эксперимент привязки обязательства Binding ACom (n)



Pdf көрінісі
бет154/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   150   151   152   153   154   155   156   157   ...   249
Криптография Катц

Эксперимент привязки обязательства 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.


209


Достарыңызбен бөлісу:
1   ...   150   151   152   153   154   155   156   157   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет