Модель со случайным оракулом

191
При попадании в такую ситуацию, существуют несколько выходом. Один 
из таких выходов - найти схемы, которые могут наверняка обеспечить защи-
ту на основе какого-либо обоснованного предположения об испольуемой хэш-
функции. Это хороший подход, но он оставляет открытым вопрос о том, что же 
делать до того, пока такие схемы не будут найдены. Также доказуемо защищен-
ные конструкции могут быть значительно менее эффективные, чем другие под-
ходы, защита которых не была доказана. (Это очевидная проблема, с которой 
мы столкнемся в условиях крптосистем с открытым ключом.)
Другая возможность, конечно же, - это использование существующей крип-
тосистемы, даже если нет другого обоснования ее защиты, кроме, возможно, 
того факта, что разработчики постарались атаковать ии и потерпели неудачу. 
Это идет вразрез со всем, что мы сказали о важности научного, современного 
подхода к криптографии, и должно быть ясно, что это неприемлемо.
Подход, который был очень успешен на практике и который предлагает «золотую 
середину» между полным научным доказательством защиты с одной стороны и от-
сутствием каких-либо доказательств - с другой, заключается в том, чтобы представить 
идеализированную модель для доказательства защиты криптографических схем. Хотя
идеализация может не быть точным отражением реальности, мы можем по крайней 
мере извлечь некоторые меры уверенности в работоспособности проекта схемы из до-
казательства в рамках идеализированной модели. Если модель является обоснованной, 
такие доказательства определенно лучше, чем отсутствие доказательств.
Наиболее популярный пример такого подхода - это модель со случайным ора-
кулом, которая рассматривает криптографическую хэш-функцию H в качестве 
истинно случайной функции. (Мы уже видели пример этому в нашем описании 
компромиссов времени/пространства, хотя там мы анализировали скорее атаку, 
чем конструкцию.) Выражаясь более конкретно, модель со случайным ораку-
лом предполагает существование публичной, случайно функции H , которая 
может быть вычислена только путем «опроса» оракула, своего рода «черного 
ящика», который возвращает H(x) после получения водного элемента x. (Мы 
обсудим, как это можно истолковать, в следующем разделе.) Чтобы разграни-
чить вещи, модтель, которую мы использовали до этого (где не присутствовал 
случайный оракул) часто называют «стандартной моделью».
Никто не утверждает, что случайный оракул существует, хотя были выдвинуты 
предположения, что случайный оракул мог бы имплементирован на практике с 
использованием доверительной стороны (то есть какого-то сервера в интернете). 
Конечно, модель со случайным оракулом обеспечивает формальную методоло-
гию, которая может быть использована для разработки и валидации криптогра-
фических схем с использованием следующего двухшагового подхода: 

192
1. Во-первых, схема разрабатывается, и доказывается ее защита, на модели со 
случайным оракулом. То есть мы предполагаем, что среда содержит случайного 
оракула и конструирует и анализирует криптографическую схему внутри такой 
модели. Стандартные криптографические предположения такого типа, которые 
мы видели и ранее, и теперь могут быть использованы в доказательстве.
2. Когда мы хотим имплементировать схему на практике, случайный оракул 
становится недоступным. Вместо этого, случайный оракул реализовывается 
посредством криптографической хэш-функции H. (Мы вернемся к этому мо-
менту в конце раздела.) То есть на каждом этапе, когда схема требует, чтобы 
сторона опращивала оракула на предмет значения H(x), сторона вместо этого 
самостоятельно вычисляет Hˆ (x).
Надежда в том, что криптографическая хэш-функция, используемая во вре-
мя второго шага, является «достаточно хорошей» при эмуляции случайного 
оракула, поэтому доказательство защиты, полученное во время первого шага, 
будет перенесено на практическую реализацию схемы. Трудность заключается 
в том, не существует теоретического обоснования такой надежды, и, фактиче-
ски, имеют место (искусственные) схемы, защита которых может быть доказана 
на модели со случайным оракулом, но незащищенные независимо от того, как 
случайный оракул реализован на втором шаге. Более того, неясно (с матема-
тической точки зрения или эвристической), что для хэш-функции значит быть 
«достаточно хорошей» при эмуляции случайного оракула, и также неясно, мож-
но ли вообще достичь такой цели. В частности, никакая конкретная реализация 
Hˆникогда не сможет вести себя как случайная функция, так как Hˆявляется де-
терминированной и фиксированной. По этой причине доказательство защиты 
на модели со случайным оракулом должно рассматриваться как предоставле-
ние подтверждения того, что схема не имеет «внутренних недостатков проек-
тирования», и не является научным доказательством того, что любая реальная 
реализация схемы защищена. Дальнейшее описание того, как истолковать до-
казательства в модели со случайным оракулом представлено в Разделе 5.5.2.

жүктеу/скачать 6.4 Mb.

Достарыңызбен бөлісу: