Вычислительно ограниченный противник

В теории информации проблема противника, ограниченного в вычислительном отношении, представляет собой другой взгляд на проблему отправки данных по зашумленному каналу. В предыдущих моделях лучшее, что можно было сделать, — это обеспечить корректное декодирование при ошибках до d /2, где d — расстояние Хэмминга кода. Проблема с этим способом заключается в том, что он не принимает во внимание фактический объем вычислительной мощности, доступной противнику. Скорее, речь идет только о том, сколько бит данного кодового слова может измениться и при этом сообщение будет декодироваться должным образом. В вычислительно ограниченной модели противника канал ( противник ) ограничен возможностью выполнить только разумный объем вычислений, чтобы решить, какие биты кодового слова необходимо изменить. Другими словами, в этой модели не нужно учитывать, сколько ошибок можно обработать, а только то, сколько ошибок можно внести при разумном объеме вычислительной мощности со стороны противника. Как только каналу будет присвоено это ограничение, становится возможным создавать коды, которые быстрее кодируются и декодируются по сравнению с предыдущими методами, которые также могут обрабатывать большое количество ошибок.

Сравнение с другими моделями

Модель наихудшего случая

На первый взгляд наихудшая модель кажется интуитивно идеальной. Гарантия того, что алгоритм будет успешным, несмотря ни на что, конечно, очень привлекательна. Однако оно требует слишком многого. Реальный злоумышленник не может тратить неопределенное количество времени на изучение сообщения, чтобы найти единственную модель ошибки, с которой алгоритм будет бороться.

Для сравнения рассмотрим алгоритм быстрой сортировки . В худшем случае быстрая сортировка делает O( n ²) сравнения; однако такое явление встречается редко. Вместо этого быстрая сортировка почти всегда выполняет сравнения O( n log n ) и даже превосходит другие алгоритмы, которые могут гарантировать поведение O( n log n ). Предположим, злоумышленник хочет заставить алгоритм быстрой сортировки сделать O( n ²) сравнения. Тогда ему придется искать все n ! перестановки входной строки и тестировать алгоритм на каждой, пока не найдет ту, для которой алгоритм работает существенно медленнее. Но поскольку это заняло бы O( n !) времени, противнику явно невозможно сделать это. Точно так же неразумно предполагать, что противник системы кодирования и декодирования сможет протестировать каждый шаблон ошибки, чтобы найти наиболее эффективный.

Модель стохастического шума

Модель стохастического шума можно охарактеризовать как своего рода «тупую» модель шума. То есть у него нет способности адаптироваться к «разумным» угрозам. Даже если злоумышленник ограничен, все равно возможно, что он сможет обойти стохастическую модель, проявив немного смекалки. Стохастическая модель не имеет реального способа борьбы с такого рода атаками и, как таковая, не подходит для борьбы с «разумными» угрозами, от которых было бы предпочтительнее иметь защиту.

Поэтому в качестве компромисса между ними была предложена вычислительно ограниченная состязательная модель. ^[1] Это заставляет учитывать, что сообщения могут быть искажены сознательно, даже злонамеренно, но это не заставляет разработчика алгоритма беспокоиться о редких случаях, которые, вероятно, никогда не произойдут.

Приложения

Сравнение со стохастическим шумовым каналом

Поскольку любой противник с ограниченными вычислительными возможностями может за время O( n ) подбросить монету для каждого бита, интуитивно понятно, что любая система кодирования и декодирования, которая может работать против этого противника, должна также работать в модели стохастического шума. Обратное не так просто; однако можно показать, что любая система, которая работает в модели стохастического шума, также может эффективно кодировать и декодировать против вычислительно ограниченного противника, и только за дополнительную плату, которая является полиномиальной по n . ^[1] Следующий метод для достижения этой цели был разработан Диком Липтоном и взят из: ^[1]

Иллюстрация метода. Первая строка содержит исходное закодированное сообщение; второй — после случайной перестановки и случайного R; третий, после того как противник добавит N; четвертый, после перестановки; пятый — закодированное сообщение с удаленной ошибкой противника.

Позволять $E()$ быть кодировщиком модели стохастического шума и $D()$ быть простым декодером того же самого, каждый из которых работает за полиномиальное время. Кроме того, пусть и отправитель, и получатель используют некоторую функцию случайной перестановки. $\pi$ и случайный узор $R$ .

Для кодирования: 1. Пусть $X=E(M)$ .

2. Пусть $Y=\pi (X)\oplus R$ .

3. Передача $Y$

Тогда для декодирования: 1. Получить $Y'$ . Вычислить $Z=\pi ^{-1}(Y'\oplus R)$ .

2. Рассчитать $M=D(Z)$ .

Как и в приведенном выше сравнении быстрой сортировки, если канал хочет сделать что-то умное, он должен сначала протестировать все варианты. Однако это невозможно для противника с ограниченными вычислительными возможностями, поэтому максимум, что он может сделать, — это создать случайный шаблон ошибок. $N$ . Но тогда:

Z=\pi ^{-1}(Y'\oplus R)=\pi ^{-1}(Y\oplus N\oplus R),

с $Y'=Y\oplus N$ по определению.

=\pi ^{-1}(Y\oplus R)\oplus N'

, где

N'=\pi ^{-1}(N),

поскольку любая перестановка линейна относительно XOR,

=X\oplus N',

согласно определению $Y$ выше.

С $\pi$ является случайным, $N'$ это просто случайный шум, и мы можем использовать простой декодер, чтобы декодировать полученное сообщение и вернуться обратно. $M$ .

Конкретные приложения

Предполагая, что противник ограничен в вычислительном отношении, можно разработать локально декодируемый код , который будет одновременно эффективным и почти оптимальным, с незначительной вероятностью ошибки. Эти коды используются в теории сложности для таких вещей, как самокорректирующиеся вычисления, вероятностно проверяемые системы доказательств и снижение жесткости от наихудшего случая до среднего в конструкциях псевдослучайных генераторов. Они полезны в криптографии из-за их связи с протоколами поиска частной информации . Они также используются в ряде приложений баз данных, таких как отказоустойчивое хранилище данных. ^[2]

Более того, можно создавать коды, превосходящие известные границы для кодов наихудшего случая, в частности, уникальное декодирование с $1-R$ частота ошибок. ^[3] Это можно сделать путем объединения цифровых подписей с отметками времени в сообщениях. Канал с вычислительными ограничениями не может подделать подпись; и хотя оно может иметь действительные прошлые подписи, получатель может использовать декодирование списка и выбирать сообщение только в том случае, если его подпись имеет правильную временную метку.

См. также

Бетонная безопасность

Ссылки

^ Jump up to: ^а ^б ^с Липтон (6 мая 2009 г.). «Наихудший случай сложности» . Потерянное письмо Гёделя и P=NP . Проверено 1 апреля 2013 г.
^ Островский, Пандей, Сахай. «Частные локально декодируемые коды» (PDF) . Проверено 1 апреля 2013 г. {{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Микали, Пейкерт; Судан, А. Уилсон. «Оптимальное исправление ошибок для вычислительно ограниченного шума» (PDF) . Проверено 1 апреля 2013 г.

[lipton-1] Jump up to: ^а ^б ^с Липтон (6 мая 2009 г.). «Наихудший случай сложности» . Потерянное письмо Гёделя и P=NP . Проверено 1 апреля 2013 г.

[OPScodes-2] Островский, Пандей, Сахай. «Частные локально декодируемые коды» (PDF) . Проверено 1 апреля 2013 г. {{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка )

[MPWSWoptErr-3] Микали, Пейкерт; Судан, А. Уилсон. «Оптимальное исправление ошибок для вычислительно ограниченного шума» (PDF) . Проверено 1 апреля 2013 г.

[1]

[2]

[3]