kaipa | Случайность как незнание

При обсуждение поста "Случайность случайности", были справедливо подняты вопросы о связи случайности и сложности с криптографией. Я надеялся, что один из авторов прочитанной мною статьи даст коментарии, но вероятно он был слишком занят. Либо вопросы были слишком глупые. Тем не менее,

a_shen написал, что у него с коллегами вышла недавно целая книга, посвещенная вопросам колмогровской сложности и алгоритмической случайности. Издана, кстати, книга отлично; у меня есть печатный вариант -- держать в руках одно удовольствие, а фрагменты рукописей Колмогорова на разворотах добавляют особого шарма. Так вот, в этой книге, вернее в первом "философском" приложении, есть некоторые рассуждения, имеющие прямое отношение к криптографии. Приведу небольшой фрагмент целиком.

Наше обсуждение становится слишком философским, и его трудно продолжать серьёзно. Но есть важные математические результаты, которые имеют прямое отношение к этому обсуждению, и мы сейчас о них немного поговорим. Вообще в этой книге мы избегали ограничений на время и память в рассматриваемых алгоритмах, оставаясь в рамках общей теории вычислимости. (Сложность с ограничениями на ресурсы -- интересная, трудная и пока не очень развитая область, которая осталась целиком вне нашей книги.) Тем не менее при обсуждении природы вероятности не упомянуть об этих результатах нельзя.

Мы имеем в виду понятие генератора псевдослучайных битов (в смысле Блюма, Микэли и Яо; об этом центральном понятии современной сложностной криптографии можно прочесть, например, в книге Голдрайха [47]). Существование таких генераторов не доказано, но следует из некоторых сложностных предположений (существование односторонних функций), которые многие считают правдоподобными.

Объясним неформально, о чём идёт речь. Представим себе простую и быструю (полиномиальную) процедуру, которая берёт «зародыш» случайности (seed в англоязычной литературе), двоичное слово сравнительно небольшой длины, скажем, из тысячи битов. Эта процедура преобразует его в гораздо более длинное слово, скажем, в последовательность из 10^10 битов. Естественно, что получившееся слово имеет малую сложность, поскольку оно может быть задано указанием самой процедуры (которая проста по нашему предположению) и зародыша. Более того, даже и сложность с ограничением на время мала, поскольку преобразование предполагается легко вычислимым.

Тем не менее, если нам покажут такое слово из 10^10 битов, то мы можем и не отличить его от по-настоящему случайной последовательности. Это звучит па- радоксально: мы только что сказали, что колмогоровская сложность такого слова мала, а для случайных слов она близка к длине, в каком же смысле мы говорим о неотличимости?

Смысл этот вполне практический -- мы бы сразу согласились с тем, что это слово имеет малую сложность и потому нетипично, если бы нам показали зародыш. Но если нам дали это слово длины 10^10 просто так, то перебрать все 2^1000 возможных зародышей выше человеческих сил (даже если иметь в виду всё человечество со всеми его компьютерами), и никто так никогда и не узнает, что оно на самом деле было малой сложности.

Это соображение показывает, что в принципе мир может управляться простыми динамическими законами с достаточно простыми начальными условиями (описываемыми, скажем, тысячами битов). В таком мире «истинной» случайности не существует, и любая последовательность из 10^6 бросаний монеты (уже случившаяся, или которая случится в будущем) будет сильно сжимаемой. Тем не менее, вычислительно ограниченный наблюдатель (вроде нас самих) может никогда этого и не обнаружить.

Ссылка [47] -- это O. Goldreich -- Foundations of Cryptography, на русский, похоже, не переведена.