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

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

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

Забывчивый алгоритм передачи Рабина

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

1. Отправитель посылает N , e и m ^e mod N получателю.
2. Получатель выбирает случайное x mod N и передает x ² mod N отправителю.
3. Отправитель находит квадратный корень y из x ² mod N и передает y получателю.

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

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

Забывчивый протокол 1 к 2

В данной версии протокола, отправитель посылает два сообщения m ₀ и m ₁ , а получатель имеет бит b , и хотел бы получить m _b , без того что бы отправитель узнал b , в то же время отправитель хочет быть уверенным в том, что получатель получил только одно из двух сообщений.

1. Отправитель имеет два сообщения, ${\displaystyle m_{0},m_{1}}$ , и хочет отправить одно единственное получателю, но не хочет знать какое из них именно он получит.
2. Отправитель генерирует пару ключей RSA, содержащие модули ${\displaystyle N}$ , публичную экспоненту ${\displaystyle e}$ и скрытую ${\displaystyle d}$ .
3. Отправитель так же генерирует два случайных значений ${\displaystyle x_{0},x_{1}}$ и отсылает их получателю вместе с публичными модулями и экспонентой
4. Получатель выбирает ${\displaystyle b}$ (1, 0) и выбирает или первый или второй ${\displaystyle x_{b}}$ .
5. Получатель генерирует случайное значение ${\displaystyle k}$ и шифрует ${\displaystyle x_{b}}$ рассчитывая ${\displaystyle v=(x_{b}+k^{e})\mod N}$ , которые возвращает отправителю.
6. Отправитель не знает какое из ${\displaystyle x_{0}}$ и ${\displaystyle x_{1}}$ выбрал получатель, и пытается расшифровать оба случайных сообщения, получая два возможных значения ${\displaystyle k}$ : ${\displaystyle k_{0}=(v-x_{0})^{d}\mod N}$ и ${\displaystyle k_{1}=(v-x_{1})^{d}\mod N}$ . Одно из них будет соответствовать ${\displaystyle k}$ , будучи корректно расшифрованным, тогда как другое будет случайным значение, не раскрывающем никакой информации о ${\displaystyle k}$ .
7. Отправитель шифрует оба секретных сообщения с каждым возможным ключом ${\displaystyle m'_{0}=m_{0}+k_{0}}$ , ${\displaystyle m'_{1}=m_{1}+k_{1}}$ и посылает их оба получателю.
8. Получатель знает какое из двух сообщений может быть расшифровано с помощью ${\displaystyle k}$ , и он получает возможность расшифровать только одно сообщение ${\displaystyle m_{b}=m'_{b}-k}$

Забывчивый протокол 1-из- n и забывчивый протокол k -из- n

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

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

См. также

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

Примечания

Ссылки

• . «How to exchange secrets by oblivious transfer.» Technical Report TR-81, Aiken Computation Laboratory, Harvard University, 1981. от 23 ноября 2021 на Wayback Machine . Typed version available on от 2 июля 2013 на Wayback Machine ( ).
• . «Founding Cryptography on Oblivious Transfer», Proceedings, 20th Annual ACM Symposium on the Theory of Computation (STOC), 1988.
• Gilles Brassard , and . «All-or-nothing disclosure of secrets.» In Advances in Cryptology: CRYPTO ’86, volume 263 of LNCS, pages 234—238. Springer, 1986.
• and . «Oblivious transfer with adaptive queries.» In Advances in Cryptology: CRYPTO ’99, volume 1666 of LNCS, pages 573—590. Springer, 1999.