57
доступ к по-настоящему произвольным битам. Аналогичным образом, мы можем
рассматривать случайный алгоритм, как тот, которому помимо входных данных за-
дана равномерно распределенная случайная лента достаточной длины1, чьи биты
он может использовать в своей работе по мере необходимости. Существуют две
причины, по которым мы по умолчанию рассматриваем случайные алгоритмы.
Во-первых, случайность существенна для криптографии (например, при выборе
случайных ключей и т.д .), поэтому честные участники должны быть вероятност-
ными, исходя из чего естественно допускать, что и противники тоже могут быть
вероятностными. Во-вторых, рандомизация практична и, насколько нам известно,
наделяет перехватчиков дополнительной мощностью. Поскольку нашей целью яв-
ляется создание модели всех реалистичных атак, мы предпочитаем более свобод-
ное определение эффективного вычисления.
Достарыңызбен бөлісу: