RUS  ENG
Полная версия
ЖУРНАЛЫ // Труды Математического института имени В. А. Стеклова // Архив

Труды МИАН, 2011, том 274, страницы 210–221 (Mi tm3328)

Эта публикация цитируется в 4 статьях

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

Ан. А. Мучник


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

УДК: 510.5

Поступило в марте 2011 г.


 Англоязычная версия: Proceedings of the Steklov Institute of Mathematics, 2011, 274, 193–203

Реферативные базы данных:


© МИАН, 2024