Теория информации

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

Прямое противостояние между Кирой и L начинается с прибытия команды детективов в Японию. В конечном итоге Кира оказывается слабейшим из двух игроков: хотя он и убивает L, тот уже знает, что Ягами Лайт и Кира одно и то же лицо. Возможно, Лайт и мог бы выиграть, но у более талантливого Киры эта игра вообще не состоялась бы. Тетрадь убивает со стопроцентной эффективностью, не оставляет никаких следов и позволяет подстраивать сколь угодно сложные обстоятельства. По большому счёту, Death Note это мысленный эксперимент на тему как можно быть пойманным, имея безупречное орудие убийства.

Другие пользователи Тетрадей смерти демонстрируют самый очевидный способ. Члены Yotsuba Group не только истребляют преступников, но и убивают своих конкурентов. Это довольно быстро сужает круг подозреваемых со всего человечества до группы из 8 человек, но очевидное qui prodest не самый интересный ход даже для рядового детектива. К тому же Лайт передал им Тетрадь как раз для того, чтобы они были в конце концов пойманы, так что перед нами не самые умные убийцы на планете. Кира не бросается сводить личные счёты, не ведёт блога со списком жертв и вообще не совершает (поначалу) ничего непроходимо тупого, но в конечном итоге всё же попадается. Как?

Расследование как задача оптимизации

Когда у L нет вообще никакой информации, он вынужден подозревать всё человечество. Его работа как детектива состоит в том, чтобы выбрать из 7 миллиардов людей ровно одного, а это классическая задача поиска. В реальности список подозреваемых обычно меньше, но очень похожую задачу соответствующие органы решают, например, при ловле деятелей даркнета. Так или иначе, L необходимо добыть примерно 33 бита информации (log2(7e9) 32.7). Много это или мало?

Не так уж и много. Адресация конкретного байта из 8 гигабайт оперативки, скажем, больших проблем не вызывает. Что касается человечества, L мог бы для начала поднять криминальную статистику и обнаружить, что подавляющее большинство серийных убийц и террористов мужчины. Кира ещё не совершил ни одной ошибки, а один бит у преследователей уже есть. Гипотетические суперрациональные Киры могли бы это предусмотреть и с некоторой вероятностью передавать свои тетради женщинам, чтобы восстановить нормальное соотношение полов. Скажем, если женщинам достаётся всего четверть тетрадей, то Киры-мужчины могли бы бросать кубик и передавать свою тетрадь женщине, если выпадет 1 или 2. (прим. пер.: суперрациональная модель требует, чтобы Кир было много и они знали о существовании друг друга. Ни то, ни другое не относится к Лайту по состоянию на начало аниме.)

Можно заметить, что даже в самом Death Note есть женщина с тетрадью Миса Амане. Но она, во-первых, вообще довольно искусственный персонаж (потому что какое же аниме без анимешных девочек, а основной каст Death Note чисто мужской), а во-вторых безумно влюблена в Лайта и действует в основном по его воле.

Надо сразу сказать, что сколько-то бит Лайт всё равно потеряет. Чтобы не отдавать вообще никакой информации, ему надо было запереть Тетрадь в шкаф и забыть про неё. Любое активное действие по определению наблюдаемо, хотя бы в теории. На практике весь смысл деятельности Киры в том, чтобы сокращать жизни преступников. Невозможно их одновременно сокращать и не сокращать; даже безупречный Кира оставил бы след в статистике ФСИН и аналогичных организаций.

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

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

Ошибки Киры

Ошибка 1: способ убийства

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

Итак, первая и самая фундаментальная ошибка: имея в своём распоряжении буквально любые причины смерти, Лайт фокусируется на сердечных приступах. Это не только сообщает всему миру (а значит, и L) о его существовании, это ещё и позволяет отделить убийства Киры от не связанных с ним смертей в той же когорте. Сразу становится понятно, что метод убийства сверхъестественно точен и не требует личного присутствия, но непригоден для преступников, о которых неизвестно широкой публике. Какие бы оправдания своим действиям он ни придумывал, Лайт в первой же паре серий подарил детективам массу информации о Тетради.

Разумеется, Ягами Лайт по сути персонаж греческой трагедии, и его губит прежде всего его собственная гамартия: беспредельная гордыня и стремление поиграть со всем человечеством в кошки-мышки. Требовать от него, чтобы он спокойно оптимизировал долгосрочный план действий не умнее, чем советовать Ахиллу с Агамемноном поумерить понты, или рассказывать Клитемнестре, а затем Электре с Орестом, о прощении. Он не может работать скрытно и планомерно.

Даже для своей номинальной цели, то есть запугивания преступников, образ сверхъестественного мстителя может оказаться субоптимальным. Если Кира это конкретный человек, то он очевидно не может знать обо всём, он не может не ошибаться, у него есть личные предпочтения. Можно предположить, например, что коррупционеры или торговцы ворованными данными не вызывают в нём той же ярости, что и педофилы. В конце концов, он смертен, и более того внезапно смертен. У преступников всегда есть надежда, что эпоха Киры закончится вот буквально на днях и лично до них он добраться не успеет.

Эта ошибка фундаментальна, но личность Киры напрямую не выдаёт. 33 бита остаются за ним.

Ошибка 2: расписание

Смерти преступников одинаковы не только по своим обстоятельствам, они ещё и происходят в определённое время дня. L строит распределение и приходит к выводу, что в это время мог бы убивать студент или служащий, живущий в часовом поясе Токио. Это сужает круг подозреваемых с 7 миллиардов человек до 128 миллионов японцев, или с 33 бит до 27 (log2(1.28e8) 26.93). Шесть бит только за привычку не убивать во время уроков!

(прим. пер.: Кира мог бы быть жителем российской Восточной Сибири, одной из Корей или восточной Индонезии. Япония самая многочисленная страна в своём часовом поясе, но важность этой ошибки всё же завышена примерно на один бит)

Самое неожиданное в этом шаге то, что он работает в реальном мире. Большинство зрителей просто решили, что авторам нужно было как-то обосновать приезд L в Японию, и они притянули улику за уши. В самом деле, пара пиков утром и вечером по японскому времени, и всё? В общем-то да. Я обнаружил тот же эффект за годы до того, как посмотрел Death Note. В то время я много редактировал англоязычную Википедию, и время от времени возникала необходимость узнать, не являются ли часом два участника одним и тем же лицом. Иногда мне было важно знать, откуда родом тот или иной википедист. Если на странице участника и в обсуждениях не было ничего полезного, я открывал счётчик правок и смотрел, когда этот человек был активен. Суточный график имеет примерно следующий вид: ~4 часа без единой правки, затем 4 часа умеренной или высокой активности, резкий провал, 8 часов медленного подъёма, затем пик длиной около 4 часов и постепенное снижение до нуля. Читать это надо так: глубокой ночью (около 4 часов местного времени) спят практически все. С утра человек встаёт, проверяет новости и, возможно, вносит мелкие правки. Потом он идёт на работу, откуда изредка что-то постит (скорее всего после того, как закончит с делами отсюда повышение к концу рабочего дня), возвращается домой и сидит за википедией весь вечер. После полуночи он почти наверняка идёт спать.

Разумеется, график не идеально ровный. Время от времени человек может засидеться до глубокой ночи, редактировать весь день или уехать в отпуск. Но установить часовой пояс удавалось всегда. Я ни разу не ошибался на пол-планеты, потому что объект работает в ночную смену. Корреляция между временем правок и географией IP подтверждена и на больших выборках участников Википедии. В Twitter другие циркадные ритмы, но там они тоже есть.

Исследования указывают на много других не менее странных способов деанонимизировать пользователя. Так как всё коррелирует со всем, любой мелочи может быть достаточно для деанонимизации пользователя:

• Мелкие погрешности в часах компьютера (даже через Tor)
• История браузера, а то и просто версия и набор плагинов. Это не считая случаев, когда баги Firefox, Google Docs или Facebook напрямую сливают личность пользователя.
• Атаки по времени, основанные на измерении времени загрузки. С их помощью можно даже узнать имя пользователя и число приватных фото.
• 42% пользователей XING были однозначно идентифицированы по набору групп, в которых они состоят. Тот же принцип может работать и в других соцсетях.
• Зная всего несколько фильмов, которые пользователь посмотрел на Netflix (неважно, популярных или малоизвестных), можно найти все остальные данные его профиля. Эта атака работает только для профилей, вошедших в анонимизированный датасет Netflix Prize, но она позволяет идентифицировать человека по невероятно малому количеству информации. Никто и не подозревал, что ваши предпочтения в аниме могут вас выдать, даже если не смотреть экзотические тайтлы.
• Те же авторы использовали поиск изоморфизмов между произвольными графами, скажем, социальными сетями безо всяких данных, кроме топологии графа друзей/групп (конкретно для соцсетей показано на паре Flickr/Twitter) для деанонимизации людей, вошедших в публичные анонимизированные датасеты. Поиск изоморфизмов между произвольными графами звучит как NP-трудная задача и вполне может ей являться, но на практике современные алгоритмы с ней неплохо справляются.
• Про имена пользователей и их переиспользование я вообще молчу.
• Кстати об анонимизированных данных, даты рождения, пола и места проживания вполне достаточно для кросс-корреляции между предположительно анонимизированными наборами медицинских или судебных данных и публичными списками избирателей. 97% зарегистрированных избирателей Кембриджа (Массачусетс) однозначно идентифицируются по дате и месту рождения (прим. пер.: имеется в виду не город рождения, а ZIP code, почтовый индекс), а 29% по дате рождения и полу.
• Ритм использования клавиатуры пригоден для биометрии. Звук или видео печати не только идентифицируют человека, но и могут использоваться для кражи паролей.
• Зная путь от дома до работы с точностью до квартала, можно однозначно идентифицировать человека; 5% людей идентифицируются даже по пути с точностью до почтового индекса.
• В опознании по почерку нет ничего нового; а как вам опознание по тому, как человек заштриховывает поле в анкете? Точность не абсолютная, но в 51% случаев алгоритм угадывает человека, а в 75% называет его среди топ-3 кандидатов из примерно сотни.
• Кстати о письме, автоматическое определение автора по стилю текста широко распространённая практика.
• Незаметный для человека шум в электрической проводке меняется со временем и позволяет датировать аудиозаписи. Подобные уникальные шумы могут использоваться для отслеживания людей или приборов, мониторинга активности в помещении и прочая и прочая.
• Каждый школьник знает про подслушивание с помощью лазерных микрофонов. А как насчёт подслушивания через видеозапись пачки чипсов или фантика от конфеты? Как насчёт подслушивания через гироскоп мобильника? Как насчёт использования жёсткого диска в качестве микрофона? С помощью лазера можно ещё и считать на растоянии сердечный ритм, а он уникален.
• Водителя можно опознать по стилю вождения, иногда даже за единственный разворот.
• Историю перемещений мобильного телефона можно отследить при отключенном GPS за счёт изменения часовых поясов, атмосферного давления, корреляции с публичными данными типа расписания поездов и прочих мелочей.
• Фотографии со смартфона позволяют идентифицировать конкретное устройство по мелким погрешностям сенсоров и линз. Фейсбук это даже запатентовал.
• Паттерн использования смартфона коррелирует с болезнью Альцгеймера и чертами личности.
• Голос коррелирует не только с возрастом и этнической принадлежностью, но и с внешностью.

Коротко говоря, дифференциальная приватность практически невозможна; почти любая активность выдаёт достаточно информации, чтобы опознать деятеля; и вообще приватность мертва. Можно утешать себя тем, что это палка о двух концах и утрата приватности позволяет гражданам следить за своей властью. На самом деле это не очень работает: например, уровень слежки за гражданами как рос до Wikileaks, так и растёт после него (прим. пер.: в наших реалиях много ли чиновников село после расследований Навального?). Но идея всё равно приятная. Впрочем, вернёмся к Death Note.

Провокация с Тейлором

Выяснив, что убийца находится в Японии, L начинает сужать круг поисков. Он заставляет приговорённого преступника Линда Л. Тейлора выступить на телевидении с заявлением, что он и есть L, и оскорблениями в адрес Киры. Передача транслируется только в Канто (регионе, в котором проживает около трети японцев). Убив Тейлора, Лайт даёт понять, что он её увидел, и тем самым выдаёт своё местоположение. Вообще-то в данном случае он поступает глупо: это очевидная провокация L, и одного этого должно быть достаточно, чтобы на неё не реагировать. Хотя Лайт и не знает, что L надеется получить от этого хода, последний наверняка имеет какой-то план и незачем ему следовать. Тем не менее, потери не особенно велики: круг подозреваемых уменьшился втрое, L получил ~1.6 бит информации. Киру всё ещё нужно найти среди 21.5 миллионов мужчин (половина 43-миллионного населения Канто), и у него остаётся log2(2.15e7) 24.36 бит анонимности. К тому же эта информация устаревает: в любой момент убийца может уехать из Канто. Несложно проверить, был ли данный подозреваемый там-то и там-то тогда-то и тогда-то, но с течением времени становится всё тяжелее составить список людей, в нужное время присутствовавших в огромном столичном регионе.

L тоже действует не самым оптимальным образом: лучше было бы разделить Японию на две примерно равные половины и иметь матожидание полученной информации в один бит. При делении 2:1 операция приносит либо ~1.6 бит (если убийца в Канто), либо ~0.3 бит (если его там нет). Как бы то ни было, он рискнул и выиграл. К тому же провокация с Тейлором позволила выяснить, что для успешного убийства Кире достаточно лица и имени жертвы L ещё не видел Тетради, но о том, как от неё защититься, он знает всё.

Ошибка 4: конфиденциальная информация

Отец Ягами Лайта полицейский, участвующий в поисках Киры. Не в силах устоять перед искушением, Лайт влезает в полицейские базы данных и убивает преступников, о которых не сообщалось в медиа. Ещё одна ошибка, которой можно было бы избежать: Лайт мог бы ограничиться только теми преступниками, о которых сообщалось в новостях. Они к тому же лучше всего подходят для его пропагандистских задач. Он мог бы использовать доступ отца только для немногочисленных приоритетных целей, хотя бы чтобы не дать полиции понять, что их базы скомпрометированы (и не лишиться доступа). Наконец, он мог бы использовать для получения информации магические возможности тетради (скажем, написав Продажный прокурор Х кончает с собой, предварительно опубликовав список всех неосуждённых убийц Токио) или репутацию Киры (создав что-то вроде Wikileaks).

Это крупнейшая ошибка из всех, совершённых Лайтом. Обычно в качестве таковой фанаты называют реакцию на провокацию с Тейлором или интригу с прокурором Миками, но если измерять ошибки убийцы количеством утраченной анонимности катастрофа случилась именно сейчас. Теперь L знает, что Кира имеет доступ к полицейским данным, то есть он либо опер японской полиции, либо родственник опера. Таких всего несколько тысяч и круг подозреваемых сужается на три порядка: с 21.5 миллиона до, скажем, 10 000 человек, а анонимность уменьшается с 24 до 14 бит. Десять с лишним бит это почти вдвое больше, чем вторая ошибка (отсекающая буквально 98% человечества) и в восемь раз больше, чем третья (обычно считающаяся самым красивым ходом L за всю игру).

Ошибка 5: невеста Пенбара

После предыдущей ошибки L делит полицейских и их родственников на группы и распределяет их проверку между своими подчинёнными. Агенту ФБР Рею Пенбару среди прочих достаётся и Ягами Лайт; узнав об этом, Кира убивает самого Пенбара и его невесту. Самого полицейского он из игры, конечно, выводит, но даёт остальным понять, что Кира находится среди Пенбаровых подозреваемых.
Это совсем уж непроходимая глупость: если считать, что Пенбару досталось 200 человек из 10 000, то Кира безо всякой пользы для себя потратил шесть бит анонимности из остававшихся 14 столько же, сколько ему стоила вторая ошибка. Мы не знаем точно, сколько подозреваемых было у Пенбара, но после его смерти L однозначно нужно меньше десятка бит.

Эндшпиль

К этому моменту расследование практически завершено L уверен, что Кирой является Ягами Лайт, и ему остаётся только собрать доказательства. Вероятно, последние 6-8 бит он добрал классическими детективными методами: среди подозреваемых Пенбара вряд ли было много высокомерных интеллектуалов без стопроцентного алиби хотя бы на какие-то из убийств. Оставшаяся часть аниме хороша как драма, но с точки зрения анонимности и теории информации уже неинтересна.

Анонимность это сложно, или как быть Кирой и не сесть

Как же следовало действовать Лайту? Ответ простой, но он не очень легко воплощается в жизнь. Он мог бы дезинформировать L вместо того, чтобы его информировать. Теренс Тао пишет об анонимности и дезинформации:

Ещё один способ увеличить анонимность намеренная дезинформация. Допустим, актор раскрывает 100 независимых бит информации. Если все они истинны, то он теряет сто бит анонимности (предполагая, что априорные вероятности 0 и 1 для каждого бита равны друг другу) и, соответственно, сужает круг подозреваемых в 2^100 раз. Если, с другой стороны, 5 из 100 бит информации намеренно фальсифицированы, то существует (100 choose 5) 226 вариантов того, какие именно 5 бит ложны. По сути это возвращает 26 бит анонимности. На практике дезинформирующий актор получает даже больше аннонимности, так как для поиска фальсифицированных бит атакующему необходимо решить вычислительно сложную задачу выполнимости. Впрочем, со временем прогресс SAT-решателей может свести этот бонус к нулю.

С утверждением, что Лайт должен был или мог использовать дезинформацию при выборе времени убийств, есть одна проблема. Советовать задним числом легко, но откуда ему было знать, что время убийств вообще может выдать его часовой пояс? Выше я упоминал, что использовал этот приём в Википедии, но на тот момент я был единственным, кто им пользовался (позднее его использовали в попытках установления личности Dread Pirate Roberts и Сатоши Накамото). Наверняка существуют и другие утечки анонимности, о которых я не имею ни малейшего представления. Если бы я был Кирой и помнил про свой трюк, но не озаботился равномерно распределить убийства по времени или создать обманный паттерн (указывающий, например, на Европу вместо Японии) мне было бы некого винить, кроме самого себя. Но во время действия Death Note деанонимизация по времени активности ещё не была изобретена. Как мог Лайт защититься от атаки, о которой он ничего не знал?

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

Можно позаимствовать пример из Uncontrolled Джима Манци: допустим, мы изучаем разные способы похудеть. Поскольку все эти заморочки с рандомизацией ниже нашего достоинства, мы распределяем субъектов между контрольной и экспериментальной группой не случайно, а тупо в том порядке, в каком они пришли к нам в клинику. Скажем, сперва набираем 10 человек экспериментальной группы, а всех пришедших позже отправляем в контроль. В остальном эксперимент безупречен размер групп одинаковый, субъекты распределены на подгруппы по исходному весу, представлены разные возраста и т.д. и т.п. Вот только так вышло, что в некоей семье присутствует редкая мутация, влияющая на набор веса. Записываться на эксперимент они пришли всей семьёй, к тому же в первый же день. В результате у большей части экспериментальной группы мутация есть, ни у кого в контрольной её нет, и по сути мы исследовали не эффект нашей диеты, а различия между людьми с мутацией и без неё. Вся работа псу под хвост. Можно перезапустить эксперимент и убедиться, что люди с данной мутацией представлены в обеих группах, но где гарантия, что не придёт семейство с какой-нибудь другой мутацией или не вылезет ещё один неожиданный фактор? А вот если бы мы сперва набрали людей, а потом случайно выбрали эксперимент и контроль мутация (или что угодно ещё) почти наверняка была бы представлена в обеих группах и результаты были бы валидны.

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

Гораздо безопаснее было бы рандомизировать время смерти, личность жертвы и обстоятельства смерти. Даже если считать, что Лайт обязан выдать существование Киры и добиться международной известности (что само по себе проблема между славой и эффективностью обычно приходится выбирать), ему всё ещё незачем снижать свою анонимность сильно ниже исходных 32 бит.

1. Время каждой смерти могло бы определяться случайно (например, броском 24-гранной и 60-гранной кости).
2. Обстоятельства смерти можно было бы рандомизировать в соответствии с легко доступными демографическими показателями (хотя этот пункт противоречит требованию славы и скорее годится для того, чтобы скрыть факт убийства).
3. Жертв можно выбирать только на основании международных источников. Статью в какой-нибудь New York Times в принципе мог бы прочитать почти любой человек на планете; если откладывать убийство на месяцы или годы, то можно скрыть источник информации. В противном случае даже без провокации с Тейлором Лайт рано или поздно убил бы преступника, о котором сообщал только мелкий японский телеканал.

Можно придумать и другие стратегии рандомизации. Важно помнить, что все эти советы относятся только к анонимному Кире, использующему низкотехнологичные стратегии. Идеи типа почему бы Лайту не создать рынок убийств или не захватить мир с помощью Тетради противоречат всей задумке Death Note.

В страхе перед квантовым компьютером, способном взломать современные методы шифрования, криптографы всего мира продолжают поиски криптографических систем, устойчивых к атаке квантового компьютера. Одна из таких криптосистем была изобретена ещё в 1978 году и базируется на теории алгебраического кодирования. В данной статье приведён обзор кодовой криптографии на основе кодов с малой плотностью проверок на чётность (или просто LDPC кодов). Всех заинтересовавшихся прошу под кат.

Содержание

1. Введение
2. Линейные коды
3. Кодовая криптография
4. Низкоплотностые (LDPC) коды
5. Криптография на LDPC кодах
6. Заключение
7. Литература

Введение

Данный материал рассчитан на людей с базовыми знаниями в областях криптографии, теории информации и линейной алгебры и написан студентом, которому просто понравилось изучать данную предметную область. Основная терминология, на которую я опираюсь, приведена в первых разделах, но для углубленного понимания подразумевается самостоятельный поиск и изучение дополнительной информации по теме. Некоторая литература, способствующая этому, приведена в конце статьи.

Линейные коды

Матричное кодирование

Назовём порождающей матрицей $inline$G$inline$ линейного пространства $inline$С$inline$ матрицу вида:

На этом месте условимся, что все вычисления проводятся в $inline$GF(2)$inline$, поэтому все $inline$x_{ij}$inline$ принимают значения 0 или 1.

В систематическом виде матрица $inline$G$inline$ представляет собой конкатенацию единичной матрицы $inline$I$inline$ и чётность части матрицы $inline$P$inline$. Из систематического вида легко получить соответствующую проверочную матрицу $inline$H$inline$, которая имеет вид:

На самом деле, матрице $inline$G$inline$ не обязательно быть в систематической форме. В этом смысле важно, чтобы между $inline$H$inline$ и $inline$G$inline$ сохранялось отношение: $inline$GH^{T}=0$inline$. Тогда кодирование имеет вид: $inline$с = mG$inline$, где $inline$m$inline$ исходное слово, $inline$c$inline$ полученное кодовое слово.

Проблема декодирования

Проверочная матрица служит для контроля того, что при передачи сообщения не произошло ошибок. Назовём синдромом $inline$s$inline$ вектор, полученный после вычисления $inline$s = Hc^{T}$inline$. Если синдром представляет собой нуль-вектор, то ошибок при передаче не произошло. В ином случае вместо $inline$c$inline$ мы получаем $inline$с'=с+е$inline$, где $inline$e$inline$ вектор ошибки (в позициях, где произошли ошибки, он принимает значения 1).

Чтобы декодировать кодовое слово $inline$c'$inline$, необходимо сначала освободить его от ошибок. Декодирование максимального правдоподобия (maximum likelihood decoding) представляет собой задачу поиска такого $inline$e$inline$, что $inline$He^{T} = s$inline$. Это следует из:

Эквивалетная задача: для данного кода $inline$c'$inline$ найти ближайшее корректное кодовое слово $inline$c$inline$ (ближайшее в смысле метрики расстояния Хэмминга). Проблема решается только полным перебором всех векторов ошибки (либо всех кодовых слов).

Для многих линейных кодов изобретены алгоритмы эффективного декодирования (например, для LDPC кодов, рассмотренных ниже, применяются алгоритмы belief propagation и bit-flipping, позволяющие декодировать код с ошибками за линейное время). Но в общем случае декодирование произвольного линейного кода это NP-трудная задача.

Кодовая криптография

Основная идея

Ключевая идея кодовой криптографии: заставить атакующего решать NP-трудную задачу, а именно декодировать случайный линейный код.

Подход здесь является следующим:

• Давайте спрячем структуру кода с известным алгоритмом декодирования при помощи некоторых линейных преобразований (например, перестановок) над $inline$G$inline$ и получим новую порождающую матрицу $inline$G'$inline$
• Используем $inline$G'$inline$, чтобы закодировать слово со случайным вектором ошибки $inline$e$inline$
• Зная те операции, которые мы применили к $inline$G$inline$, мы можем применить обратные операции к $inline$G'$inline$ и декодировать кодовое слово эффективным алгоритмом, освобождая его от ошибок
• Для атакующего этот код будет выглядеть случайным

Криптосистема Мак-Элиаса

Самые популярные криптосистемы в кодовой криптографии были предложены Мак-Элиасом и немного позже Нидеррайтером. Алгоритмы носят соответсвующие названия.

Для них характерно:

• Ассимитричное шифрование: имеется открытый и закрытый ключ
• В качестве основы может быть использован любой линейный код с известным эффективным алгоритмом декодирования
• Криптосистемы устойчивы к атаке квантового компьютера
• Основной недостаток: огромный размер ключей (исчисляется в Мб)

В дальнейшем мы подробнее остановимся только на криптосистеме Мак-Элиаса.

Генерация ключей

Ключи генерируются по следующему алгоритму:

1. Пусть $inline$G$inline$ порождающая (k, n)-матрица (n, k)-линейного кода, исправляющего $inline$t$inline$ ошибок
2. Возьмём случайную невырожденную (k, k)-матрицу $inline$S$inline$
3. Возьмём случайную (n, n)-матрицу перестановки $inline$P$inline$
4. Публичный ключ: пара $inline$(SGP, t)$inline$, где $inline$SGP = G'$inline$
5. Приватный ключ: тройка $inline$(S, G, P)$inline$

Пояснение: невырожденность матриц $inline$S$inline$ и $inline$P$inline$ является обязательный условием, потому что по ним ищутся обратные матрицы, и умножение на них происходит при дешифровании, а t необходимо для того, чтобы не получилось добавить в код больше ошибок, чем он может исправить, при шифровании.

Интересным является простота алгоритма (оригинальная статья автора занимала всего 3 страницы!), но при этом и его потенциал. Думаю, написана уже не одна сотня текстов, продолжающих эту идею.

Шифрование

Зашифровываем сообщение следующим образом:

1. Берём случайный вектор ошибки $inline$е$inline$ длины $inline$n$inline$ и веса $inline$w$inline$ не больше $inline$t$inline$
2. Кодируем сообщение следующим образом: $inline$c = mG + e$inline$

Теперь расшифруем наш шифротекст c:

1. Рассчитаем $inline$c = cP^{-1}$inline$
2. Декодируем $inline$c'$inline$ извеcтным алгоритмом, получим сообщение $inline$m'$inline$
3. Восстановим исходное сообщение $inline$m = mS^{-1}$inline$

Весь математический концепт можно выписать в виде одной формулы:

Модификации

В оригинале автор предложил использование своего алгоритма на основе двоичных кодов Гоппы, но вскоре математики начали предлагать модификации алгоритма с другими линейными кодами. Перечислю некоторые: недвоичные коды Гоппы, коды Рида-Соломона, Габидуллина, Рида-Маллера, LDPC, LRPC, полярные, алгебро-геометрические коды и многие их вариации.

К сожалению, большинство из этих кодов были довольно быстро взломаны: примерно через несколько лет после публикации идеи другие математики предлагали эффективную атаку. Эксплуатировалась в основном сильная алгебраическая структура многих кодов.

Есть небольшой список линейных кодов, до сих пор не поддавшихся эффективному криптоанализу:

• Двоичные коды Гоппы
• Свёрточные коды
• MDPC коды (вариация LDPC кодов)

Далее рассмотрим вариацию криптосистемы на базе LDPC кодов и их более устойчивой разновидности MDPC кодов.

Низкоплотностые (LDPC) коды

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

Для тех, кто не сталкивался с LDPC кодами ранее, настоятельно рекомендую ознакомиться с замечательной статьёй по ним здесь или на Википедии.

Достоинства LDPC кодов

Для кодов с малой плотностью проверок на чётность характерны:

• Разреженная матрица проверки на чётность: количество единиц в ней стремится к 0 при росте n. Структура матрицы при этом выглядит довольно случайной.
• Они могут быть декодированы за линейное время. Существуют алгоритмы "мягкого" и "жёсткого" декодирования (в англ. литературе "soft-decision" и "hard-decision" decoding).
• Отличная корректирующая способность: нерегулярные LDPC коды очень близки к границе Шеннона.
• Квазициклическая вариация (QC-LDPC) может быть представлена в виде компактной формы полинома.

Криптография на LDPC кодах

Приведённые выше достоинства LDPC кодов позволяют им быть отличной базой для криптосистемы Мак-Элиаса, потому что:

1. Структуру LDPC кода легко "спрятать" под линейными преобразованиями.
2. Существуют алгоритмы быстрого декодирования.
3. Компактная форма QC-LDPC кодов может существенно уменьшить размер закрытого ключа.

Но есть и недостатки:

1. Корректирующая способность случайно сгенерированного LDPC кода неизвестна (для определения параметра t используется либо моделирование декодирования с ошибками, либо алгоритм density evolution).
2. На код уже известны некоторые атаки (например, атака по дуальному коду).
3. Нужно брать сравнительно большие коды, чтобы достичь достаточного уровня криптостойкости.

Разновидности LDPC кодов

На данный момент в криптографии более применимы модификации LDPC: MDPC и его квазициклическая форма (QC-MDPC).

MDPC коды

MDPC (Moderate Density Parity-Check) коды это более "тяжёлая" разновидность LDPC кодов. Если для генерации LDPC кодов рекомендуется брать вес вектора w не больше 10, то для MDPC кода средний вес строки выбирается из расчёта $inline$w = \sqrt{n\cdot log(n)}$inline$, где n длина вектора-строки (считается, что эта цифра является наиболее оптимальной).

MDPC коды характерны меньшей корректирующей способностью, но большей устойчивостью к структурным криптографическим атакам: в данном случае уже нельзя проэксплуатировать разреженность проверочной матрицы.

Квазициклические коды

Порождающая матрица низкоплостностого квазициклического (QC-LDPC) кода задаётся в виде конкатенации нескольких циркулянт. Циркулянтой называется (n, n)-матрица, в первой строчке которой записан полином, а остальные строки его циклические сдвиги:

Задавая код в таком виде, мы немного теряем в корректирующей способности, но можем хранить порождающую матрицу в компактной форме: теперь нам нужно хранить только порождающие полиномы, а построить порождающую матрицу можно выписав их циклические сдвиги.

Давайте оценим, во сколько раз можно уменьшить наш приватный ключ, используя такой подход для (p, n)-QC-LDPC кода с параметрами n = 9602 и p = 4801 (размер одной циркулянты):

1. Бинарная матрица перестановки P(n, n): ~11 Mb --> целочисленный вектор P(n): ~9.5 Kb. В данном случае мы храним массив переставленных столбцов, избавляясь от огромной размерности.
2. Порождающая матрица G(n, p): ~5.5 Mb --> полиномиальная форма G(n): ~1.2 Kb.
3. Бинарная матрица S(p, p): ~2.75 Mb --> полиномимальная форма S(p): ~0.6 Kb. Используя S тоже в форме циркулянты, мы немного потеряем в криптостойкости, но сильно уменьшим затраты памяти.

Итоговый профит: приватный ключ в 1760 раз меньше! К сожалению, для публичного ключа такой же фокус провернуть не выйдет.

Уровень криптостойкости

Уровнем криптостойкости называется двоичный логарифм от количества итераций, необходимых атакующему для взлома криптосистемы.

Например, Мак-Элиас на базе (1024, 524, 101)-кода Гоппы гарантировал уровень криптостойкости в 50 бит (то есть атакующему потребовалось бы $inline$2^{50}$inline$ итераций для успешной атаки).

Для сравнения: MDPC код с параметрами n = 9602 и w = 90 обеспечивает уровень криптостойкости в 80 бит. В данном случае для криптоанализа не известно других методов, кроме как атаки на произвольный линейный код (например, декодирование по информационной совокупности), и на данный момент этот уровень считается довольно надёжным.

Заключение

Кодовая криптография сравнительно новая и несомненно интересная тема для изучения. Её актуальность подчёркивает увеличение компьютерных мощностей, перед которыми начинают сдаваться классические криптосистемы.

Широкому развитию кодовых криптосистем препятствуют в основном огромные размеры ключей, но учёные продвинулись и в этом направлении: квазициклические коды способны существенно уменьшить размер приватного ключа.

Все факты, утверждения и цифры, использованные в статье, были взяты из источников ниже и из Википедии свободной энциклопедии. Надеюсь, данный материал был интересен для изучения. Приветствуются любые комментарии, вопросы и уточнения по теме.

Литература

1. A Public-Key Cryptosystem Based On Algebraic Coding Theory (R. J. McEliece)
2. An Introduction to Low-Density Parity Check Codes (Daniel J. Costello, Jr.)
3. On the Usage of LDPC Codes in the McEliece Cryptosystem (Marco Baldi)
4. LDPC codes in the McEliece cryptosystem: attacks and countermeasures (Marco Baldi)
5. QC-LDPC Code-Based Cryptography (Marco Baldi)
6. MDPC-McEliece: New McEliece Variants from Moderate Density Parity-Check Codes (Rafael Misoczki and Jean-Pierre Tillich and Nicolas Sendrier and Paulo S. L. M. Barreto)
7. Modern Coding Theory (Tom Richardson, Rudiger Urbanke)