Бит с отложенным прочтением

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

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

Принцип действия

Вертикальная ось — ось времени, горизонтальная — ось расстояний между агентами. В начале координат первый агент Боба (B1) передает агенту Алисы (A1) случайное сообщение (x1). Путь распространения сообщения имеет наклон, который ограничен скоростью света. Красные линии показывают пути сообщений, которыми могут пытаться обмениваться агенты Алисы для подмены бита. Как видно, они оказываются там, где физически расположены агенты Алисы, уже после того, как произошел очередной сеанс связи.

Схема экспериментальной установки бита с отложенным прочтением

В основе техники для передачи бита с «отложенным прочтением» лежит существование двух агентов Алисы $A_{1},A_{2}$ и двух агентов Боба $B_{1},B_{2}$, попарно находящихся в разных точках земного шара. Расстояние $L$ между агентами Боба подобрано таким образом, чтобы сеанс связи между агентами $A_{i}$ и $B_{i}$ длился определённое время, гарантируя безопасность информации.

Первый агент Боба $B_{1}$отправляет расположенному неподалёку первому агенту Алисы $A_{1}$ случайное $n$-битовое число $x_{1}$. Агент Алисы $A_{1}$ суммирует его и отправляет обратно с другим заранее заготовленным секретным числом $a_{1}$ с помощью известного обоим метода, зависящего от передаваемого бита ($y_{1}=a_{1}$ для значения «ноль» или $y_{1}=x_{1}\oplus a_{1}$ для значения «единица», где «$\oplus$» — операция $XOR$, исключающее или).

Затем второй агент Алисы $A_{2}$ в ответ на отправку ей числа $x_{2}$ раскрывает второму агенту Боба $B_{2}$ передаваемый бит и секретное число, возвращая значение $y_{2}=(x_{2}\cdot a_{1})\oplus a_{2}$, где операция «$\cdot$» есть умножение в поле Галуа ${F_{2}}^{n}$. Второй агент Боба $B_{2}$ сверяет информацию с первым агентом Боба $B_{1}$ и убеждается, что за время между передачей первого и второго сообщений Алиса не совершила подлог, поменяв значение передаваемого бита.

Задержка между моментом передачи и прочтением информации в такой схеме зависит от расстояния между первым и вторым агентом Алисы $A_{1},A_{2}$. К примеру, если первый агент Алисы $A_{1}$передаёт информацию агенту Боба из Москвы, а второй $A_{2}$ — из Сиднея или Веллингтона, то безопасное время, за которое Алиса не успеет подменить бит, составит около 21 миллисекунды.

Для того, чтобы увеличить эту задержку, необходимо либо переместить одну из пар за пределы Земли (например, поместив одну из пар на Плутоне, тогда безопасное время достигнет нескольких часов), либо потребовать несколько циклов связи между агентами.

Чтобы быть уверенным в невозможности «подмены» со стороны Алисы, каждый новый цикл (а они происходят поочерёдно в каждой паре) должен начинаться до того, как агенты Алисы успеют связаться друг с другом. Чтобы у Боба не было возможности надёжно угадать передаваемый бит до окончания всех циклов передачи, требуется большой объём информации — чем больше время задержки, тем экспоненциально больше длина сообщений.

История

1999 год — впервые предложена идея отложенного прочтения бита исследователем A. Kent в журнале Physical Review Letters

2015 год — группой учёных (T. Lunghi, J. Kaniewski, F. Bussières, R. Houlmann, M. Tomamichel, S. Wehner и H. Zbinden) из Университета Женевы проведён эксперимент бита с отложенным прочтением на практике. Шесть раундов обмена сообщениями на расстоянии между парами агентов в 131 километр вызвали задержку в две миллисекунды. К примеру, для масштабов, сравнимых с размерами Земли, эта задержка может быть увеличена до 200 миллисекунд.

2016 год — группой исследователей под руководством H. Zbinden эксперимент был усовершенствован. В этот раз расстояние между парами составляло около 7 километров — обе пары находились в пределах Женевы. У агентов Алисы имелся заранее приготовленный массив 128-битных строк. В первом раунде связи первый агент Боба передавал Алисе случайное 128-битное сообщение. Если Алиса заранее решила передать «ноль», то в ответ агент отправлял Бобу первую строку из массива. Иначе (если заготовленным сообщением была «единица») Алиса складывала сообщение Боба с первой строкой. Следующий сеанс связи начинался до того, как свет мог распространиться от одной Алисы до другой, сообщая о результатах первого сеанса.

Во время второго сеанса второй агент Боба отправлял второе случайное сообщение второму агенту Алисы. Агент математически комбинировал это сообщение (выполнял умножение в поле Галуа) с первой строкой массива, а затем суммировал со второй. После этого третий сеанс связи происходил уже между первыми агентами и так далее.

Последний сеанс связи (всего в эксперименте их было пять миллиардов) завершался тем, что агент Алисы отдавал Бобу в явном виде последнюю строку массива. Боб использовал её для того, чтобы вычислить предпоследнюю строку, предпредпоследнюю и так далее. Всего за 24 часа эксперимента было передано 162 гигабайта сообщений, а на полную их дешифровку с использованием обычного компьютера ушло около 72 часов.

Применение

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

Но всё же у этого метода существуют приложения. В частности, в работе D.Boneh и M.Naor исследовали фиксированные временные задержки, после которых раскрывается секретное значение. Это показывают, что данный принцип может быть использован в аукционах или для подписания контрактов.

Данный метод непригоден для того, чтобы хранить секрет вечно, но он полезен в тех ситуациях, когда необходимо заставить стороны действовать одновременно (в том смысле, что действия двух агентов не должны зависеть друг от друга) даже при последовательной коммуникационной модели.

Анализ обеспечения безопасности

Анализ обеспечения безопасности информации в работе вывел следующую вероятность удачной попытки взлома:

$\epsilon \lesssim 2^{(-n/2)^{m-1}}$,

где $n$ — это длина битовой строки при передаче от Боба к Алисе в каждом раунде передачи информации, $m+1$ — число этих раундов. Как видно из формулы, длина сообщения $n$ должна должна расти экспоненциально, дабы число $\epsilon$ было много меньше единицы.

Реализация в работе была ограничена 6 раундами связи, получая битовую задержку в 2 мс между агентами на расстоянии 131 км (расстояние между Женевой и Берном).

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

$\epsilon \leqslant m\cdot 2^{(-n+3)/2}$.

Этот результат открывает путь к реализации гораздо большей задержки. Последний анализ показывает небольшое уменьшение требуемых ресурсов.