Забывчивая передача (часто сокращается как OT — oblivious transfer) — в криптографии тип протокола передачи данных, в котором передатчик передает по одной возможные части информации получателю, но не запоминает (является забывчивым), какие части были переданы, если вообще были.

Первая форма забывчивой передачи была представлена в 1981 году Михаэлем О. Рабином. В этой форме передатчик передает сообщение получателю с вероятностью в 1/2, в то же время не запоминая, было или нет сообщение получено получателем. Забывчивый алгоритм Рабина основывается на RSA криптосистеме. Более полезная форма забывчивого протокола называется 1-2 забывчивая передача или «забывчивая передача 1 из 2», была разработана позже Шимоном Ивеном, Одедом Голдрейхом и Абрахамом Лемпелем с целью создания протокола для протоколов конфиденциального вычисления. Этот протокол впоследствии был обобщён в «Забывчивая передача 1 из n», где пользователь получал в точности 1 часть информации, а сервер не знал, какую именно; кроме того, пользователь не знал ничего об оставшихся частях, которые не были получены.

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

Забывчивый алгоритм передачи Рабина В забывчивом протоколе передачи данных Рабина, отправитель генерирует RSA публичные модули N=pq где p и q большие простые числа и экспоненту е взаимно простую с (p-1)(q-1). Отправитель шифрует сообщение m как me mod N. Отправитель посылает N, e и me mod N получателю. Получатель выбирает случайное x mod N и передает x2 mod N отправителю. Отправитель находит квадратный корень y из x2 mod N и передает y получателю.

Если отправитель находит y не являющийся ни x ни -x mod N, получатель сможет факторизовать N и тем самым расшифровать me для получения m. (более подробно Криптосистема Рабина)

Однако, если y равно x или -x mod N получатель не будет иметь информации о m. Так как каждый квадратичный вычет по mod N имеет 4 квадратных корня, шанс что получатель расшифрует m равен 1/2.

Забывчивый протокол 1 к 2 В данной версии протокола, отправитель посылает два сообщения m0 и m1, а получатель имеет бит b, и хотел бы получить mb, без того что бы отправитель узнал b, в то же время отправитель хочет быть уверенным в том, что получатель получил только одно из двух сообщений.

Отправитель имеет два сообщения, , и хочет отправить одно единственное получателю, но не хочет знать какое из них именно он получит. Отправитель генерирует пару ключей RSA, содержащие модули , публичную экспоненту и скрытую . Отправитель так же генерирует два случайных значений и отсылает их получателю вместе с публичными модулями и экспонентой Получатель выбирает (1, 0) и получает если b = 1, в ином случае получает (далее ). Получатель генерирует случайное значение и шифрует рассчитывая , которые возвращает отправителю. Отправитель не знает какое из и выбрал получатель, и пытается расшифровать оба случайных сообщения, получая два возможных значения : и . Одно из них будет соответствовать , будучи корректно расшифрованным, тогда как другое будет случайным значение, не раскрывающем никакой информации о . Отправитель шифрует оба секретных сообщения с каждым возможным ключом , и посылает их оба получателю. Получатель знает какое из двух сообщений может быть расшифровано с помощью , и он получает возможность расшифровать только одно сообщение

Забывчивый протокол 1-из-n и забывчивый протокол k-из-n Забывчивый протокол 1-из-n и забывчивый протокол k-из-n может быть определён как обобщение забывчивого протокола 1-из-2. Отправитель имеет n сообщений, а получатель — индекс i; получатель желает получить только i-е сообщение из списка, без того что бы отправитель узнал i, а получатель получил только это сообщение.

В дальнейшем этот тип протоколов был обобщён до k-из-n, где получатель получает набор из k из n коллекции сообщений. Набор из k сообщений может быть получен одновременно, или же они могут быть запрошены по порядку, где каждый следующий запрос основан на предыдущем запросе.

См. также Протокол конфиденциального вычисления Доказательство с нулевым разглашением Получение скрытой информации

Примечания

Ссылки Michael O. Rabin. «How to exchange secrets by oblivious transfer.» Technical Report TR-81, Aiken Computation Laboratory, Harvard University, 1981. Scanned handwriting on eprint.iacr.org archive . Typed version available on Dousti’s homepage (Alternate link on Google Docs). Joe Kilian. «Founding Cryptography on Oblivious Transfer», Proceedings, 20th Annual ACM Symposium on the Theory of Computation (STOC), 1988. Paper at ACM portal (subscription required) Gilles Brassard, Claude Crépeau and Jean-Marc Robert. «All-or-nothing disclosure of secrets.» In Advances in Cryptology: CRYPTO ’86, volume 263 of LNCS, pages 234—238. Springer, 1986. Moni Naor and Benny Pinkas. «Oblivious transfer with adaptive queries.» In Advances in Cryptology: CRYPTO ’99, volume 1666 of LNCS, pages 573—590. Springer, 1999.

Категория:Криптографические протоколы