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