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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

Забывчивый алгоритм передачи Рабина[править | править вики-текст]

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

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

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

Забывчивый протокол 1 к 2[править | править вики-текст]

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

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

Забывчивый протокол 1 из-n и забывчивый протокол k-из-n[править | править вики-текст]

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

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

Ссылки[править | править вики-текст]