Колмогоровская сложность и криптография

С точки зрения колмогоровской сложности рассматриваются задачи о построении сообщений, которые содержат разное количество информации о заданном объекте в зависимости от того, какой дополнительной информацией располагает получатель. Предположим, что получатель знает слово $a$ и мы хотим сообщить получателю информацию о некотором слове $b$, причем таким образом, чтобы наше сообщение само по себе (без $a$) не позволяло восстановить $b$. Оказывается, что это возможно (если слова $a$ и $b$ не слишком просты). Далее рассматриваются более сложные родственные вопросы: что будет, если “противник” знает некоторую информацию $c$? насколько длинным должно быть сообщение? Мы уточняем эти вопросы, указываем условия, при которых сообщение может иметь полиномиальную длину, и показываем, что они существенны.