Не обращающий внимания трансфер

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

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

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

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

Забывчивый протокол передачи Рабина

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

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

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

1–2 невнимательных передачи

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

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

1. У Алисы есть два сообщения: $m_{0},m_{1}$ и хочет отправить Бобу ровно один из них. Боб не хочет, чтобы Алиса знала, какой из них он получит.
2. Алиса генерирует пару ключей RSA, содержащую модуль $N$, публичный представитель $e$ и частный показатель $d$.
3. Она также генерирует два случайных значения: $x_{0},x_{1}$ и отправляет их Бобу вместе с ее общедоступным модулем и показателем степени.
4. Боб выбирает $b$ быть либо 0, либо 1, и выбирает $x_{b}$.
5. Боб генерирует случайное значение $k$ использует его, чтобы ослепить $x_{b}$ путем вычисления $v=(x_{b}+k^{e}){\bmod {N}}$, который он отправляет Алисе.
6. Алиса комбинирует $v$ с обоими ее случайными значениями, чтобы получить: $k_{0}=(v-x_{0})^{d}{\bmod {N}}$ и $k_{1}=(v-x_{1})^{d}{\bmod {N}}$. Сейчас $k_{b}$ будет равен $k$ а другой будет бессмысленной случайной величиной. Однако, поскольку Алиса не знает значения $b$ что выбрал Боб, она не может определить, какой из $k_{0}$ и $k_{1}$ равно $k$.
7. Она объединяет два секретных сообщения с каждым из возможных ключей. $m'_{0}=(m_{0}+k_{0}){\bmod {N}}$ и $m'_{1}=(m_{1}+k_{1}){\bmod {N}}$и отправляет их обоих Бобу.
8. Боб знает $k$, поэтому он может вычислить $m_{b}=(m'_{b}-k){\bmod {N}}$. Однако, поскольку он не знает $d$, он не может вычислить $k_{1-b}=(v-x_{1-b})^{d}{\bmod {N}}$ и поэтому не могу определить $(m_{1-b}){\bmod {N}}$.

Передача с забвением 1 из n и k из n передача с забвением

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

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

Протокол забывчивой передачи «один из n» с сублинейной связью был впервые построен (как обобщение односерверного PIR) Эялем Кушилевицем и Рафаилом Островским . Более эффективные конструкции предложили Мони Наор и Бенни Пинкас . Уильям Айелло , Юваль Ишай и Омер Рейнгольд , Свен Лаур и Хельгер Липмаа . In 2017, Kolesnikov et al. , предложил эффективный протокол 1-n забывчивой передачи, который требует примерно в 4 раза больше стоимости 1-2 забывчивой передачи в амортизированных условиях.

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

Обобщенный перенос без внимания

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

Происхождение

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

Квантовый перенос без внимания

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

См. также

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

Внешние ссылки

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