Незаметный перевод

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

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

Клод Крепо показал, что передача Рабина без внимания равносильна 1–2 передаче без внимания. ³

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

Невнимательный протокол передачи Рабина [ править ]

В протоколе невнимательной передачи Рабина отправитель генерирует открытый модуль RSA N = pq, где p и q - большие простые числа , а показатель степени e, взаимно простой с λ (N) = ( p  - 1) ( q  - 1). Отправитель шифрует сообщение м , как м ^е мод N .

1. Отправитель посылает N , е и м ^е по  модулю  N к приемнику.
2. Приемник выбирает случайные х по  модулю  N и посылает е ² по  модулю  N отправителю. Обратите внимание , что НОД ( х , N ) = 1 с подавляющей вероятностью, что гарантирует , что существуют 4 квадратные корни х ²  мод  N .
3. Отправитель находит квадратный корень y из x ^{2 по}  модулю  N и отправляет y получателю.

Если получатель обнаружит, что y не является ни x, ни -x по модулю N , получатель сможет разложить на множители N и, следовательно, расшифровать m ^e, чтобы восстановить m (подробнее см. Шифрование Рабина ). Однако, если y равно x или - x  mod  N , получатель не будет иметь никакой информации о m, кроме ее шифрования. Поскольку каждый квадратичный остаток по модулю N имеет четыре квадратных корня, вероятность того, что получатель узнает m, равна 1/2.

1–2 не обращая внимания на передачу [ править ]

В протоколе передачи 1-2 не обращая внимания, Алиса-отправитель имеет два сообщения m ₀ и m ₁ , а Боб-получатель имеет бит b , а получатель желает получить m _b , без того, чтобы отправитель узнал b , в то время как отправитель хочет убедитесь, что получатель получает только одно из двух сообщений. Протокол Эвена, Голдрайха и Лемпеля (который авторы частично приписывают Сильвио Микали ) является общим, но его можно создать с помощью шифрования RSA следующим образом.

Алиса				Боб
Исчисление	Секрет	Общественные		Общественные	Секрет	Исчисление
Сообщения для отправки	${\ displaystyle m_ {0}, m_ {1}}$
Сгенерируйте пару ключей RSA и отправьте публичную часть Бобу	${\ displaystyle d}$	${\ displaystyle N, e}$	${\ displaystyle \ Rightarrow}$	${\ displaystyle N, e}$		Получить публичный ключ
Создать два случайных сообщения		${\ displaystyle x_ {0}, x_ {1}}$	${\ displaystyle \ Rightarrow}$	${\ displaystyle x_ {0}, x_ {1}}$		Получать случайные сообщения
					${\ displaystyle k, b}$	Выбрать и сгенерировать случайный${\ displaystyle b \ in \ {0,1 \}}$${\ displaystyle k.}$
		${\ displaystyle v}$	${\ displaystyle \ Leftarrow}$	${\ displaystyle v = (x_ {b} + k ^ {e}) \ mod N}$		Вычислить шифрование , вслепую и отправить Алисе${\ displaystyle k}$${\ displaystyle x_ {b}}$
Один из них будет равным , но Алиса не знает какой.${\ displaystyle k}$	${\ displaystyle {\ begin {align} k_ {0} & = (v-x_ {0}) ^ {d} \ mod N \\ k_ {1} & = (v-x_ {1}) ^ {d} \ mod N \ end {выровнено}}}$
Отправьте оба сообщения Бобу		${\ displaystyle {\ begin {align} m '_ {0} = m_ {0} + k_ {0} \\ m' _ {1} = m_ {1} + k_ {1} \ end {align}}}$	${\ displaystyle \ Rightarrow}$	${\ displaystyle m '_ {0}, m' _ {1}}$		Получите оба сообщения
					${\ displaystyle m_ {b} = m '_ {b} -k}$	Боб расшифровывает, поскольку он знает, что он выбрал ранее.${\ displaystyle m '_ {b}}$${\ displaystyle x_ {b}}$

1. У Алисы есть два сообщения,, и она хочет отправить ровно одно из них Бобу. Боб не хочет, чтобы Алиса знала, какой из них он получает.${\ displaystyle m_ {0}, m_ {1}}$
2. Алиса генерирует пару ключей RSA, включающую модуль , публичную экспоненту и частную экспоненту.${\ displaystyle N}$${\ displaystyle e}$${\ displaystyle d}$
3. Она также генерирует два случайных значения и отправляет их Бобу вместе со своим общедоступным модулем и показателем.${\ displaystyle x_ {0}, x_ {1}}$
4. Боб выбирает 0 или 1 и выбирает либо первое, либо второе .${\ displaystyle b}$${\ 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-из-of н забывает передачи и к -out-of п рассеянной передачи [ править ]

А 1-из-of н забывает протокол передачи может быть определена как естественное обобщение не обращая внимания протокола передачи в 1-из-2. В частности, у отправителя n сообщений, а у получателя есть индекс i , и получатель желает получить i-е среди сообщений отправителя, без того, чтобы отправитель узнал i , в то время как отправитель хочет убедиться, что получатель получит только одно из в п сообщений.

1-из-of п не обращая внимания переноса несравним с частным поиска информации (PIR). С одной стороны, 1-из-of п забывающий передачи накладывает дополнительные требования конфиденциальности для базы данных , а именно: что приемник учиться в наиболее одной из записей базы данных. С другой стороны, PIR требует сублинейной по n коммуникации, в то время как передача 1-вне- n без внимания не требует такого требования. Тем не менее, предположение, что PIR для одного сервера является достаточным допущением, чтобы построить Забвенную передачу 1 из 2 ¹⁴ .

1-из-of п не обращая внимания протокол передачи с сублинейного связи впервые был построен (как обобщение одного сервера PIR) по Eyal Kushilevitz и Rafail Островского ¹⁵ . Более эффективные конструкции были предложены Мони NaOR и Бенни Пинкас , ¹⁰ William Айелло , Юваль Ишай и Омер Рейнгольд , ¹¹ Sven Laur и Helger Lipmaa . ¹² . В 2017 году Колесников и др. , ¹³ предложили эффективный протокол передачи 1-n без внимания, который требует примерно в 4 раза больше стоимости 1-2 пересылки без уведомления в условиях амортизации.

Брассар , Крепо и Робер далее обобщили это понятие на k - n неявную передачу ^{5, в} которой получатель получает набор из k сообщений из набора n сообщений. Набор из k сообщений может быть получен одновременно («неадаптивно») или они могут быть запрошены последовательно, причем каждый запрос основан на предыдущих полученных сообщениях. ⁶

Обобщенный перевод без внимания [ править ]

k - n Перенос без внимания - это частный случай обобщенного переноса без внимания, который был представлен Ишаем и Кушилевицем. ⁷ В этой установке, отправитель имеет множество U из п сообщений, и ограничение передачи определяется коллекции A допустимых подмножеств U . Приемник может получить любое подмножество сообщений в U , который появляется в коллекции A . Отправитель не должен обращать внимания на выбор, сделанный получателем, в то время как получатель не может узнать значение сообщений за пределами подмножества сообщений, которые он решил получить. Коллекция Aмонотонно убывает в том смысле, что он замкнут при включении (т. е., если данное подмножество B находится в наборе A , то же самое относится ко всем подмножествам B ). Решение, предложенное Ишаи и Кушилевицем, использует параллельные вызовы 1-2 неявной передачи при использовании специальной модели частных протоколов. Позже, другие решения, основанные на тайном обмене были опубликованы - один за другим Bhavani Шанкар, Kannan Srinathan и C. Панду Rangan , ⁸ и другим путем Тамир Tassa. ⁹

Истоки [ править ]

В начале семидесятых Стивен Визнер представил примитив, называемый мультиплексированием, в своей основополагающей статье «Сопряженное кодирование», которая стала отправной точкой квантовой криптографии . ^[1] К сожалению, на публикацию книги ушло более десяти лет. Несмотря на то, что этот примитив был эквивалентен тому, что позже было названо 1-2 неявной передачей , Визнер не видел его применения в криптографии.

Квантовый неявный перенос [ править ]

Протоколы неявной передачи могут быть реализованы с помощью квантовых систем . В отличие от других задач в квантовой криптографии , таких как квантовое распределение ключей , было показано, что квантовая передача без внимания не может быть реализована с безусловной безопасностью, то есть безопасность протоколов квантовой передачи без внимания не может быть гарантирована только законами квантовой физики . ^[1]

См. Также [ править ]

• k-анонимность
• Безопасные многосторонние вычисления
• Доказательство с нулевым разглашением
• Получение частной информации

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

• ^ 0. Стивен Визнер, "Сопряженное кодирование", Sigact News, vol. 15, вып. 1, 1983, стр. 78–88; Оригинальная рукопись написана примерно в 1970 году.
• ^ 1. Майкл О. Рабин. «Как обмениваться секретами незаметной передачей». Технический отчет TR-81, вычислительная лаборатория Айкена, Гарвардский университет, 1981.Отсканированный почерк + печатная версия в архиве eprint.iacr.org. Печатная версия доступна надомашней странице Дусти.
• ^ 2. С. Эвен, О. Голдрайх и А. Лемпель, «Рандомизированный протокол для подписания контрактов»,Сообщения ACM, том 28, выпуск 6, стр. 637–647, 1985.Бумага на странице Катушии Паламидесси
• ^ 3. Клод Крепо. «Равнозначность двух вкусов не обращающего внимания на передачу». В достижениях в криптологии: CRYPTO '87, том 293 конспектов лекций по информатике, страницы 350–354. Спрингер, 1988 г.
• ^ 4. Джо Килиан. «Основы криптографии для забвения передачи», Труды, 20-й ежегодный симпозиум ACM по теории вычислений (STOC), 1988.Статья на портале ACM (требуется подписка)
• ^ 5. Жиль Брассар,Клод КрепоиЖан-Марк Робер. «Раскрытие секретов по принципу« все или ничего »». В достижениях в криптологии: CRYPTO '86, том 263 LNCS, страницы 234–238. Спрингер, 1986.
• ^ 6. Мони НаориБенни Пинкас. «Забывающая передача с адаптивными запросами». В достижениях в криптологии: CRYPTO '99, том 1666 LNCS, страницы 573–590. Спрингер, 1999.
• ^ 7. Юваль Ишай и Эял Кушилевиц. «Частные протоколы одновременных сообщений с приложениями». В Proc. ISTCS'97, Компьютерное общество IEEE, страницы 174–184, 1997.
• ^ 8. Бхавани Шанкар, Каннан Шринатан и Ч. Панду Ранган. «Альтернативные протоколы для обобщенного неявного переноса». В Proc. ICDCN'08, LNCS 4904, страницы 304–309, 2008 г.
• ^ 9. Тамир Тасса. «Обобщенная неявная передача путем разделения секрета». Проекты, коды и криптография, том 58: 1, страницы 11–21, январь 2011 г.Статья на openu.ac.il
• ^ 10. Мони НаориБенни Пинкас(1990). Незаметная полиномиальная оценка31-го STOC
• ^ 11. Уильям Айелло,Юваль ИшаииОмер Рейнгольд(2001).Неявная передача по цене: как продавать цифровые товарыEUROCRYPT '01 Труды Международной конференции по теории и применению криптографических методов: достижения в криптологии, стр. 119–135
• ^ 12. Свен Лаур и Хельгер Липмаа (2007). «Новый протокол для условного разглашения секретов и его применения». Джонатан Кац и Моти Юнг, редакторыACNS,Lecture Notes in Computer Science 4521: 207–225. Спрингер, Гейдельберг.
• ^ 13. Владимир Колесников, Ранджит Кумаресан, Майк Росулек и Ни Триё (2017). «Эффективный пакетный не обращающий внимания PRF с приложениями для пересечения частных наборов». В Эдгаре Р. Вейпле, Стефане Катценбайссере, Кристофере Крюгеле, Эндрю К. Майерс и Шай Халеви, редакторах, ACM CCS 16, страницы 818–829. ACM Press, октябрь 2016 г.
• ^ 14. Джованни Ди Крещенцо, Таль Малкин, Рафаил Островский: Поиск частной информации из единой базы данных подразумевает незаметную передачу. ЕВРОКРИПТ 2000: 122-138
• ^ 15. Эял Кушилевиц, Рафаил Островский: Репликация НЕ нужна: ЕДИНАЯ база данных, вычислительно-частный поиск информации. FOCS 1997: 364-373

Внешние ссылки [ править ]

• Коллекция веб-ссылок Хельгера Липмаа по этой теме