Вопрос о вредоносной безопасности в протоколе с использованием OT

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

Предположим, у нас есть протокол P, который использует OT в качестве подпротокола. Предположим, что ОТ используется $N$ раз. Каждый ОТ имеет вход $x_{0,i}$, $x_{1,i}$, куда $я$ обозначает $я-$позиция ОТ, от 1 до $N$. Разумно предположить, что для каждого положения получатель выбирает бит $0$ или же $1$ в соответствии с его входом (это, например, случай протокола Yao, где для каждого вентиля приемник запрашивает 0, если его вход равен 0 или 1 в противном случае).

Теперь предположим, что отправитель в ОТ злонамерен и априори решает изменить $x_{0,N}$ с чем-то другим. Это может быть случайное значение, значение $x_{1,N}$ или что-то еще. У нас есть три возможности

1. Прерывание протокола. Тогда отправитель знает, что во время последнего ОТ получатель запросил 0.
2. Протокол не прерывается, и ввод действительно правильный. Теперь отправитель знает, что во время последнего ОТ получатель запросил 1.
3. Протокол не прерывается, ввод неверен, и стороны могут это обнаружить. Теперь отправитель знает, что во время последнего OT получатель запросил 0.
4. Протокол не прерывается, ввод неверный, но стороны не могут его обнаружить. Затем отправитель может произвольно заставить протокол выводить значения, отличные от заданного.

Если поведение является одним из первых трех, отправитель может изменить таким образом все OT, и это $\фракция{1}{2^N}$ вероятность изучения всего запроса без обнаружения, что, поскольку $N$ является фиксированным параметром, не является незначительным (тем более, если $N$ маленький). В других случаях получатель узнает, что отправитель злонамерен, но это не мешает получателю что-то узнать.

Если поведение является последним, я не понимаю, как такой протокол может считаться «безопасным», поскольку злоумышленнику очень легко выполнить атаку «DoS», где каждый вывод не имеет смысла.

В случае протокола Yao предположим, что отправитель устанавливает последний OT $X_{0,N}, X_{0,N}$. Как мы можем предотвратить это? Если протокол «идет не так», то отправитель знает, что последний бит Боба равен 0. Это огромно, не так ли?

И я не рассматриваю симметричный случай: что произойдет, если получатель вместо того, чтобы спрашивать по правилу, будет спрашивать случайным образом? Насколько я понимаю, это поведение не учитывается при проверке безопасности, я ошибаюсь?

Я что-то пропустил? Являются ли эти соображения выходящими за рамки, и мы допускаем такое поведение? Может быть, мы предполагаем, что отправитель всегда устанавливает $x_0$ и $x_1$ в правильном направлении?

Здесь собрано множество вопросов — для полного ответа на все из них потребуется полное руководство по вредоносным безопасным MPC. Я постараюсь просто сосредоточиться на общей картине.

В общем, если есть «правильное значение», которое отправитель OT «должен» использовать в качестве входных данных OT, тогда да, протокол должен быть очень осторожным. Обычно существует «правильное значение», потому что любое другое значение приведет к прерыванию работы приемника. Таким образом, «неправильные» значения в OT приведут к прерыванию работы на основе входных данных OT получателя — утечке информации об этих входных данных OT!

Есть несколько способов справиться с этим. Вот самые простые для понимания:

• Классический протокол 2PC с искаженной схемой Линделл-Пинкас 2007 г. делает следующее. Предположим, мы действительно хотим сделать OT, чтобы выбрать одну из двух меток проводов. $x_0, x_1$ на основе входа схемы приемника $b$. Предположим, получатель может проверить, действительна ли метка провода. Когда приемник прерывает работу из-за того, что видит недопустимую метку провода, происходит утечка входной схемы! Линделл и Пинкас решили эту проблему, изменив искаженную схему таким образом, чтобы получатель вводил совместное использование секрета. $b = b_1 \oplus \cdots \oplus b_\lambda$ его истинного вклада $b$. Искаженная схема затем выполнит операцию XOR для восстановления этих общих ресурсов. $b$ а дальше как обычно. Так что теперь вместо одного ВТ на этот входной провод схемы есть $\лямбда$ ОТ, потому что мы искусственно увеличили количество входов схемы. Предположим, что отправитель ОТ мошенничает в первом $к <\лямбда$ ОЦ. Входы приемника в эти первые $к$ OT представляют собой набор секретных долей, но меньше порогового количества долей, поэтому они распределяются независимо от частного входа $b$! В этом случае приемник просто прервется с вероятностью $1 - 2^{-к}$, независимо от их входа. Если отправитель ОТ мошенничает во всех $\лямбда$ OTs, то приемник прерывает работу с вероятностью 1 или $1-2^{-\лямбда}$, с вероятностью, зависящей от их личного ввода! -- но так как они пренебрежимо близки, это фактически не представляет собой утечку информации.

• Протокол ЗК Явурек, Кершбаум, Орланди также основан на искаженных цепях. Они выполняют типичный OT с метками проводов, где вход получателя OT является их личным свидетелем ZK. Они тщательно структурируют протокол, чтобы отправитель OT мог публично раскрыть обе входных данных ОТ в какой-то более поздний момент --- для этого требуется вариант ОТ, называемый "завершенным ОТ". По сути, верификатор вычисляет некий «окончательный ответ» об искаженной схеме, которая приводит к утечке информации об их личном входе, если в ОТ имело место какое-либо мошенничество. Поэтому вместо того, чтобы просто отправить этот окончательный ответ, он совершает к этому. Затем отправитель ОТ раскрывает все свои входные данные ОТ, чтобы доказать, что обмана не было. Если получатель ОТ убежден, он может открыть свое обязательство перед «окончательным ответом».

• Иногда вы можете разработать протокол таким образом, чтобы не было такой вещи, как неправильный ввод ОТ. Вот простой способ проверить, являются ли две частные строки $x = x_1 \cdots x_n$ и $y = y_1 \cdots y_n$ равны (вдохновленные протоколом PSI Пинкас-Шнайдер-Зонер). Бег $n$ OTS случайных значений, поэтому $я$у OT есть входы $r_{i,0}$ и $r_{i,1}$. Приемник OT использует биты своего входа $х$ как биты выбора OT, и изучает значения формы $r_{я, х_я}$. Они могут вычислить значение $R_x = H(x, r_{1,x_1}, r_{2,x_2}, \ldots, r_{n,x_n})$, куда $Ч$ это случайный оракул. Отправитель OT имеет свой собственный вход $у$, и знает все $r_{i,b}$ ценности. Таким образом, они могут вычислить значение $R_y = H( y, r_{1,y_1}, r_{2,y_2}, \ldots, r_{n,y_n})$ и отправьте его получателю OT. Если $R_x = R_y$ тогда $х$ и $у$ были равны; в противном случае $х$ и $у$ были разными (и $R_y$ выглядит случайным для получателя). Как может мошенничать коррумпированный отправитель OT? Они могли отправить $Ч$ некоторых Другие вещи (т. е. включать что-то, не равное какому-либо $r_{i,b}$ в качестве вклада в $Ч$). Но это было бы просто гарантия что получатель сделает вывод, что «строки не совпадают» — независимо от того, что $х$ они держат. С этим легко справляется симулятор.

Итак, у нас есть три разных высокоуровневых подхода к проблеме, о которой вы спрашивали:

• Этот протокол делает так, чтобы биты выбора OT получателя были эффективно независимы от их частных данных, поэтому, если мошенничество приводит к прерыванию, вероятность этого прерывания не зависит от частного ввода получателя OT.

• Получателю OT предоставляется способ обнаружить мошенничество, чтобы он мог остановить протокол до того, как станут видны какие-либо плохие последствия мошенничества.

• Другие части протокола просто не имеют каких-либо плохих последствий, если отправитель OT решит действовать несовместимо со своими входными данными OT.

Наверняка есть и другие умные подходы, но это первое, что пришло на ум.

что произойдет, если получатель вместо того, чтобы спрашивать по правилу, будет спрашивать случайным образом? Насколько я понимаю, это поведение не учитывается при проверке безопасности, я ошибаюсь?

В большинстве протоколов на основе OT биты выбора OT получателя представляют собой прямое кодирование их ввода в основной протокол. Это, безусловно, имеет место в 3 приведенных выше примерах. Использование «неправильных» битов выбора OT в точности эквивалентно выбору другого входа для основного протокола, и это не считается атакой на злонамеренную безопасность.