Русская Википедия:Забывчивая передача
Забывчивая передача (часто сокращается как OT — oblivious transfer) — в криптографии тип протокола передачи данных, в котором передатчик передает по одной возможные части информации получателю, но не запоминает (является забывчивым), какие части были переданы, если вообще были.
Первая форма забывчивой передачи была представлена в 1981 году Михаэлем О. РабиномШаблон:Ref. В этой форме передатчик передает сообщение получателю с вероятностью в 1/2, в то же время не запоминая, было или нет сообщение получено получателем. Забывчивый алгоритм Рабина основывается на RSA криптосистеме. Более полезная форма забывчивого протокола называется 1-2 забывчивая передача или «забывчивая передача 1 из 2», была разработана позже Шимоном Ивеном, Одедом Голдрейхом и Абрахамом Лемпелем с целью создания протокола для протоколов конфиденциального вычисления. Этот протокол впоследствии был обобщён в «Забывчивая передача 1 из n», где пользователь получал в точности 1 часть информации, а сервер не знал, какую именно; кроме того, пользователь не знал ничего об оставшихся частях, которые не были получены.
В ходе дальнейших работ забывчивые протоколы стали одной из фундаментальных и важнейших проблем в криптографии. Они рассматриваются как самая важная проблема в области шифрования из-за важности приложений, построенных на их основе. В частности, забывчивые протоколы сделали возможным существование протоколов конфиденциального вычисления.Шаблон:Ref
Забывчивый алгоритм передачи Рабина
В забывчивом протоколе передачи данных Рабина, отправитель генерирует 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, в то же время отправитель хочет быть уверенным в том, что получатель получил только одно из двух сообщений.Шаблон:Ref
- Отправитель имеет два сообщения, <math>m_0, m_1</math>, и хочет отправить одно единственное получателю, но не хочет знать какое из них именно он получит.
- Отправитель генерирует пару ключей RSA, содержащие модули <math>N</math>, публичную экспоненту <math>e</math> и скрытую <math>d</math>.
- Отправитель так же генерирует два случайных значений <math>x_0, x_1</math> и отсылает их получателю вместе с публичными модулями и экспонентой
- Получатель выбирает <math>b</math> (1, 0) и выбирает или первый или второй <math>x_b</math>.
- Получатель генерирует случайное значение <math>k</math> и шифрует <math>x_b</math> рассчитывая <math>v = (x_b + k^e)\mod N</math>, которые возвращает отправителю.
- Отправитель не знает какое из <math>x_0</math> и <math>x_1</math> выбрал получатель, и пытается расшифровать оба случайных сообщения, получая два возможных значения <math>k</math>: <math>k_0 = (v - x_0)^d\mod N</math> и <math>k_1 = (v - x_1)^d\mod N</math>. Одно из них будет соответствовать <math>k</math>, будучи корректно расшифрованным, тогда как другое будет случайным значение, не раскрывающем никакой информации о <math>k</math>.
- Отправитель шифрует оба секретных сообщения с каждым возможным ключом <math>m'_0 = m_0 + k_0</math>, <math>m'_1 = m_1 + k_1</math> и посылает их оба получателю.
- Получатель знает какое из двух сообщений может быть расшифровано с помощью <math>k</math>, и он получает возможность расшифровать только одно сообщение <math>m_b = m'_b - k</math>
Забывчивый протокол 1-из-n и забывчивый протокол k-из-n
Забывчивый протокол 1-из-n и забывчивый протокол k-из-n может быть определён как обобщение забывчивого протокола 1-из-2. Отправитель имеет n сообщений, а получатель — индекс i; получатель желает получить только i-е сообщение из списка, без того что бы отправитель узнал i, а получатель получил только это сообщение.Шаблон:Ref
В дальнейшем этот тип протоколов был обобщён до k-из-n, где получатель получает набор из k из n коллекции сообщений. Набор из k сообщений может быть получен одновременно, или же они могут быть запрошенны по порядку, где каждый следующий запрос основан на предыдущем запросе.
См. также
- Протокол конфиденциального вычисления
- Доказательство с нулевым разглашением
- Получение скрытой информации
Примечания
Ссылки
- Шаблон:Note 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 Шаблон:Wayback. Typed version available on Dousti’s homepage Шаблон:Wayback (Alternate link on Google Docs).
- Шаблон:Note 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)
- Шаблон:Note 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.
- Шаблон:Note 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.
