Введение
Тип криптографического протокола
В криптографии протокол скрытой передачи (OT) — это тип протокола, в котором отправитель передает один из потенциально многих фрагментов информации получателю, оставаясь при этом в неведении относительно того, какой фрагмент (если таковой имеется) был передан. Первая схема скрытой передачи была предложена в 1981 году Майклом О. Рабином. В этой схеме отправитель отправляет сообщение получателю с вероятностью 1/2, при этом оставаясь в неведении о том, получил ли получатель сообщение. Схема скрытой передачи Рабина основана на криптосистеме RSA. Более полезная схема скрытой передачи, называемая скрытой передачей 1–2 или "1 из 2 скрытых передач", была разработана позднее Шимоном Ивеном, Одедом Голдрейхом и Абрахамом Лемпелем для построения протоколов безопасных многосторонних вычислений. Она обобщается до "скрытой передачи 1 из n", где пользователь получает ровно один элемент базы данных, не позволяя серверу узнать, какой элемент был запрошен, и не предоставляя пользователю никакой информации о других элементах, которые не были получены. Последнее понятие скрытой передачи является усилением задачи частного поиска информации, в которой база данных не хранится в секрете. Клод Крепо показал, что скрытая передача Рабина эквивалентна скрытой передаче 1–2. Последующие исследования показали, что скрытая передача является фундаментальной и важной задачей в криптографии. Она считается одной из ключевых задач в этой области из-за важности приложений, которые можно построить на её основе. В частности, она является полной для безопасных многосторонних вычислений: то есть, при наличии реализации скрытой передачи возможно безопасно вычислять любую функцию, вычислимую за полиномиальное время, без использования каких-либо дополнительных примитивов.
In cryptography, an oblivious transfer (OT) protocol is a type of protocol in which a sender transfers one of potentially many pieces of information to a receiver, but remains oblivious as to what piece (if any) has been transferred. The first form of oblivious transfer was introduced in 1981 by Michael O. Rabin. In this form, the sender sends a message to the receiver with probability 1/2, while the sender remains oblivious as to whether or not the receiver received the message. Rabin's oblivious transfer scheme is based on the RSA cryptosystem. A more useful form of oblivious transfer called 1–2 oblivious transfer or "1 out of 2 oblivious transfer", was developed later by Shimon Even, Oded Goldreich, and Abraham Lempel, in order to build protocols for secure multiparty computation. It is generalized to "1 out of n oblivious transfer" where the user gets exactly one database element without the server getting to know which element was queried, and without the user knowing anything about the other elements that were not retrieved. The latter notion of oblivious transfer is a strengthening of private information retrieval, in which the database is not kept private. Claude Crépeau showed that Rabin's oblivious transfer is equivalent to 1–2 oblivious transfer. Further work has revealed oblivious transfer to be a fundamental and important problem in cryptography. It is considered one of the critical problems in the field, because of the importance of the applications that can be built based on it. In particular, it is complete for secure multiparty computation: that is, given an implementation of oblivious transfer it is possible to securely evaluate any polynomial time computable function without any additional primitive.
Протокол перевода Рабина
В протоколе слепой передачи Рабина отправитель генерирует публичный модуль RSA N=pq, где p и q – большие простые числа, и экспоненту e, взаимно простую с λ(N) = (p − 1)(q − 1). Отправитель шифрует сообщение m как me mod N.
Отправитель отправляет N, e и me mod N получателю. Получатель выбирает случайное x по модулю N и отправляет x² mod N отправителю. Следует отметить, что НОД(x, N) = 1 с преобладающей вероятностью, что гарантирует наличие 4 квадратных корней x² mod N.
Отправитель находит квадратный корень y из x² mod N и отправляет y получателю. Если получатель обнаруживает, что y не является ни x, ни −x по модулю N, он сможет факторизовать N и, следовательно, расшифровать me для восстановления m (см. шифрование Рабина для получения подробностей). Однако, если y равно x или −x mod N, получатель не получит никакой информации о m, кроме его шифротекста. Поскольку каждый квадратный вычет по модулю N имеет четыре квадратных корня, вероятность того, что получатель узнает m, равна 1/2.
The sender finds a square root y of x2 mod N and sends y to the receiver. If the receiver finds y is neither x nor −x modulo N, the receiver will be able to factor N and therefore decrypt me to recover m (see Rabin encryption for more details). However, if y is x or −x mod N, the receiver will have no information about m beyond the encryption of it. Since every quadratic residue modulo N has four square roots, the probability that the receiver learns m is 1/2.
12 непредвиденная передача
В протоколе слепой передачи 1–2 Алиса, отправитель, имеет два сообщения m0 и m1 и хочет обеспечить, чтобы получатель узнал только одно из них. Боб, получатель, имеет бит b и хочет получить mb, не раскрывая Алисе значение b. Протокол Even, Goldreich и Lempel (который авторы частично приписывают Silvio Micali) является общим, но может быть реализован с использованием RSA-шифрования следующим образом.
Алиса | Боб | Вычисления | Секретное | Публичное | Публичное | Секретное | Вычисления
------- | -------- | -------- | -------- | -------- | -------- | -------- | --------
Генерирует пару ключей RSA и отправляет публичную часть Бобу | Получает публичный ключ | | | | | |
Генерирует два случайных сообщения | Получает случайные сообщения | | | | | |
Выбирает b и генерирует случайное r | | | | | | |
Вычисляет шифр от mb, "ослепляет" его с помощью r и отправляет Алисе | | | | | | |
Один из результатов будет равен mb, но Алиса не знает, какой именно. | Отправляет оба зашифрованных сообщения Бобу | | | | | |
Получает оба сообщения | Боб расшифровывает mb, так как он знает, какое сообщение (m0 или m1) он выбрал ранее. | | | | | |
У Алисы есть два сообщения, m0 и m1, и она хочет отправить Бобу ровно одно из них. Боб не хочет, чтобы Алиса знала, какое именно сообщение он получил. Алиса генерирует пару ключей RSA, состоящую из модуля n, публичного показателя e и приватного показателя d. Она также генерирует два случайных значения, k1 и k2, и отправляет их Бобу вместе со своим публичным модулем n и показателем e. Боб выбирает b равным либо 0, либо 1, и выбирает r. Боб генерирует случайное значение s и использует его для "ослепления" mb, вычисляя c = s * mb (mod n), которое он отправляет Алисе. Алиса комбинирует c с обоими своими случайными значениями, чтобы получить: c1 = c + k1 (mod n) и c2 = c + k2 (mod n). Теперь один из c1 и c2 будет равен mb, а другой – бессмысленным случайным значением. Однако, поскольку Алиса не знает значение r, выбранное Бобом, она не может определить, какое из c1 и c2 равно mb. Она комбинирует два секретных сообщения с каждым из возможных ключей, e и d, и отправляет их обоих Бобу. Боб знает r, поэтому он может вычислить mb. Однако, поскольку он не знает k1 и k2, он не может вычислить k1 и k2 и, следовательно, не может определить, какое сообщение получила Алиса.
1-из-n непредвиденная передача и k-из-n непредвиденная передача
Протокол передачи 1 из n с сохранением конфиденциальности может быть определен как естественное обобщение протокола передачи 1 из 2 с сохранением конфиденциальности. В частности, отправитель имеет n сообщений, а получатель – индекс i, и получатель хочет получить i-е сообщение из набора сообщений отправителя, не раскрывая отправителю значение i, при этом отправитель должен убедиться, что получатель получит только одно из n сообщений. Передача 1 из n с сохранением конфиденциальности не сопоставима с приватным поиском информации (PIR). С одной стороны, передача 1 из n с сохранением конфиденциальности накладывает дополнительное требование к конфиденциальности базы данных: а именно, получатель должен получить не более одной записи из базы данных. С другой стороны, PIR требует коммуникации, сублинейной относительно n, в то время как передача 1 из n с сохранением конфиденциальности не имеет такого требования. Однако, предположение об односерверном PIR является достаточным для построения передачи 1 из 2 с сохранением конфиденциальности. Первый протокол передачи 1 из n с сохранением конфиденциальности с сублинейной коммуникацией был разработан (как обобщение односерверного PIR) Эялем Кушилевицем и Рафаилом Островским. Более эффективные конструкции были предложены Мони Наором и Бенни Пинкасом, Уильямом Айелло, Ювалем Ишаем и Омером Рейнгольдом, Свеном Лором и Хельгером Липмаа. В 2017 году Колесников и др. предложили эффективный протокол передачи 1 из n с сохранением конфиденциальности, требующий примерно в 4 раза больше ресурсов, чем передача 1 из 2 с сохранением конфиденциальности, в амортизированной модели. Брассар, Крепо и Роберт дополнительно обобщили это понятие до передачи k из n с сохранением конфиденциальности, при которой получатель получает набор из k сообщений из коллекции из n сообщений. Набор из k сообщений может быть получен одновременно ("неадаптивно") или запрошен последовательно, при этом каждый запрос основан на ранее полученных сообщениях.
Общественная невнимательная передача
k n Обычная передача является частным случаем обобщенной обычной передачи, представленной Ишаи и Кушилевицем. В данной схеме отправитель располагает набором U из n сообщений, а ограничения на передачу задаются коллекцией A допустимых подмножеств U. Получатель может получить любое подмножество сообщений из U, которое содержится в коллекции A. Отправитель не должен знать о выборе, сделанном получателем, в то время как получатель не должен узнавать значения сообщений, не входящих в выбранное им подмножество. Коллекция A монотонно убывает, то есть замкнута относительно подмножеств (то есть, если данное подмножество B принадлежит коллекции A, то все подмножества B также принадлежат ей). Решение, предложенное Ишаи и Кушилевицем, использует параллельные вызовы обычной передачи 1/2, используя специальную модель приватных протоколов. Позже были опубликованы другие решения, основанные на разделении секрета – одно Бхавани Шанкаром, Каннаном Сринатханом и С. Панду Ранганом, а другое – Тамиром Тассой.
Квантовая невнимательная передача
Протоколы для передачи без раскрытия информации могут быть реализованы с использованием квантовых систем. В отличие от других задач в квантовой криптографии, таких как квантовое распределение ключей, было показано, что квантовая передача без раскрытия информации не может быть реализована с безусловной безопасностью, то есть безопасность протоколов квантовой передачи без раскрытия информации не может быть гарантирована исключительно законами квантовой физики.