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

В криптографии, протокол Забывчивая передача (часто сокращается как 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^emodN.

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

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

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

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

1. Отправитель имеет два сообщения, $m_0, m_1$, и хочет отправить одно единственное получателю, но не хочет знать какое из них именно он получит.
2. Отправитель генерирует пару ключей RSA, содержащие модули $N$, публичную экспоненту $e$ и скрытую $d$.
3. Отправитель так же генерирует два случайных значений $x_0, x_1$ и отсылает их получателю вместе с публичными модулями и экспонентой
4. Получатель выбирает $b$ (1, 0) и выбирает или первый или второй $x_b$.
5. Получатель генерирует случайное значение $k$ и шифрует $x_b$ рассчитывая $v = (x_b + k^e)\mod N$, которые возвращает отправителю.
6. Отправитель не знает какое из $x_0$ и $x_1$ выбрал получатель, и пытается расшифровать оба случайных сообщения, получая два возможных значения $k$: $k_0 = (v - x_0)^d\mod N$ и $k_1 = (v - x_1)^d\mod N$. Одно из них будет соответствовать $k$, будучи корректно расшифрованным, тогда как другое будет случайным значение, не раскрывающем никакой информации о $k$.
7. Отправитель шифрует оба секретных сообщения с каждым возможным ключом $m'_0 = m_0 + k_0$ $m'_1 = m_1 + k_1$ и посылает их оба получателю.
8. Получатель знает какое из двух сообщений может быть расшифровано с помощью $k$, и он получает возможность расшифровать только одно сообщение $m_b = m'_b - k$

Забывчивый протокол 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.