Забывчивая передача

Забывчивая передача (часто сокращается как 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.

В данной версии протокола, отправитель посылает два сообщения 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_{1}}$ если b = 1, в ином случае получает ${\displaystyle x_{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-из-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 Архивная копия от 23 ноября 2021 на Wayback Machine. Typed version available on Dousti’s homepage Архивная копия от 2 июля 2013 на Wayback Machine (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.