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

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

09.11.2020

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

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

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

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

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

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

Задержка между моментом передачи и прочтением информации в такой схеме зависит от расстояния между первым и вторым агентом Алисы A 1 , A 2 {displaystyle A_{1},A_{2}} . К примеру, если первый агент Алисы A 1 {displaystyle A_{1}} передаёт информацию агенту Боба из Москвы, а второй A 2 {displaystyle 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 исследовали фиксированные временные задержки, после которых раскрывается секретное значение. Это показывают, что данный принцип может быть использован в аукционах или для подписания контрактов.

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

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

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

ϵ ≲ 2 ( − n / 2 ) m − 1 {displaystyle epsilon lesssim 2^{(-n/2)^{m-1}}} ,

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

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

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

ϵ ⩽ m ⋅ 2 ( − n + 3 ) / 2 {displaystyle epsilon leqslant mcdot 2^{(-n+3)/2}} .

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