Введение в современную криптографию
Коды идентификации сообщений предполагают односторонние функции
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Вычислительная неразличимость
| Коды идентификации сообщений предполагают односторонние функции.
Верно также, что коды аутентификации сообщений, удовлетворяющие определению 4.2, предполагают существование односторонних функций. Как и в случае шифрова- ния с закрытым ключом, доказательство этого факта несколько утонченное, посколь- ку нестандартные коды аутентификации сообщений существуют, если существует теоретическая граница количества сообщений, которые будут проверены на подлин- ность. (См. раздел 4.6). Таким образом, доказательство опирается на тот факт, что оп- понент видит теги аутентификации на произвольном (полиноме) количестве сообще- ний. Это доказательство несколько запутано, поэтому мы не приводим его здесь. Обсуждение. Мы пришли к выводу, что существование односторонних функций не- обходимо и достаточно для всей (нетривиальной) криптографии с закрытым ключом. Другими словами, односторонние функции – минимальное допущение, когда речь идет о криптографии с закрытым ключом. Интересно, что, по-видимому, это не относится к хэш-функциям и шифрованию с открытым ключом, где, как известно, односторонние функции необходимы, но не известно (предполагается), что достаточны. Вычислительная неразличимость Понятие вычислительной неразличимости занимает центральное место в те- ории криптографии и она лежит в основе большей части того, что мы видели в главе 3 и в данной главе. С неформальной точки зрения, два распределения ве- роятности являются вычислительно неразличимыми, если никакой эффектив- ный алгоритм не может разделить их (или различить их). Более подробно, рас- 302 смотрим два распределения X и Y по строкам некоторой длины A; то есть, каждый X и Y присваивает некую вероятность каждой строке {0, 1}A. Говоря, что некоторый алгоритм D не может отличить эти два распределения, мы имеем в виду, что D не может сообщить, является ли данная строка отобранной в соответствии с распределе- нием X или является ли данная строка отобранной в соответствии с распределением Y . Иными словами, если представить D, выводящий «0», когда считается, что его входные данные были отобраны в соответствии с X и выводящий «1», если предпола- гается, что его входные данные были отобраны в соответствии с Y , тогда вероятность того, что D выводит «1» должна быть приблизительно той же, независимо от того, откуда D обеспечен образцом – из X или из Y . Другими словами, мы хотим, чтобы было малым. Это должно напоминать способ, которым мы определили псевдослучайные генераторы и, действительно, скоро мы формально заново определим понятие псевдослучайного генератора, используя данную терминологию. Формальное определение вычислительной неразличимости относится к вероят- ностным ансамблям, которые представляют собой бесконечные последовательности распределений вероятности. (Этот формализм необходим для осмысленного асим- птотического подхода). Хотя это понятие можно обобщить, мы рассматриваем веро- ятностные ансамбли, в которых основные распределения индексированы натураль- ными числами. Если для каждого натурального числа n существует распределение Xn, то X = {Xn}n∈N является вероятностным ансамблем. Часто бывает так, что Xn = Yt(n) для некоторой функции t, в этом случае мы записываем {Yt(n)}n∈N вместо {Xn}n∈N. Нас интересуют только «эффективно отбираемые» вероятностные ансамбли. Ансамбль X = {Xn}n∈N является эффективно отбираемым, если существует вероятностный полиномиально-временной алгоритм S , такой что случайные переменные S(1n) и Xn распределены идентично. То есть, алгоритм S является эффективным способом выбора X . Теперь можно формально определить, что означает для двух ансамблей, быть вычислительно неразличимыми. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|