Я не вижу нигде на этой странице описания забывчивого переноса так, как вы описали.
Непонятная передача:
- Алиса держит две струны $x_0, x_1$
- Боб держит немного $b$
- Боб учится $x_b$ но ничего не узнает о $x_{1-b}$
- Алиса ничего не узнает о $b$
Искаженная схема:
- Когда Алиса искажения логическая схема $f$, она получает большую коллекцию зашифрованных текстов $F$ («искаженная цепь»), а также запоминает по два ключа (метки) на каждом проводе цепи. На проводе #$я$ она учится $W_i^0$ что представляет false на этом проводе, и $W_i^1$ что соответствует истине на этом проводе.
- Если Боб знает искаженную схему $F$ и для каждого вход провод $я$ схемы он точно знает одну из $\{W_i^0, W_i^1\}$ тогда он может оценивать искаженную схему, чтобы узнать ровно одну метку на каждом проводе схемы (а не только на входных проводах). Он узнает «правильную» метку провода (т. е. ту, которая соответствует поведению $f$) на каждом проводе, в зависимости от того, с какой из входных меток он начинается.
- Когда Боб оценивает искаженную схему, он не узнает, держит ли он $W_i^0$ или же $W_i^1$ для любого провода $я$. Другими словами, он не знает, является ли какой-либо провод в цепи истинным или ложным. Он оценивает схему «вслепую».
Если Алиса и Боб хотят оценить функцию, используя искаженные схемы, Алиса искажает схему и отправляет искаженную схему. $F$ к Бобу.
Но Бобу также нужно учиться, для каждого вход провод $я$ в цепи ровно один из $\{W_i^0, W_i^1\}$.
И Алиса, и Боб вносят свой вклад в это вычисление.
Если номер провода$я$ является одним из входных проводов Алисы, то она может просто отправить «правильный» из $\{W_i^0, W_i^1\}$, так как она знает и то, и другое, и она знает свой входной бит на этом проводе.
Если номер провода$я$ является одним из входных проводов Боба, у Боба должен быть способ выберите выучить ровно один из $\{W_i^0, W_i^1\}$.
Поскольку Боб выбирает между этими значениями в соответствии со своими входными данными, Алиса не должна знать, какое из них он выбрал.
Именно для этого шага используется забывчивый перенос.
Для входного провода #$я$ принадлежащий вводу Боба, Алиса предоставляет $W_i^0$ и $W_i^1$ к случаю забывчивого переноса, и Боб выбирает, какой из них изучать.
Есть варианты забывчивого переноса, где у Алисы $N$ строки, и Боб выбирает одну из них для изучения.
Если Алиса и Боб хотят вычислить очень простую функцию $ф(а,б)$, где есть только $N$ возможные входные данные для Боба ($b \in \{1, \ldots, N\}$), тогда да, они могут использовать забывчивую передачу для вычисления функции напрямую, как вы предлагаете, без каких-либо искаженных схем.
Алиса использует $f(a,1), f(a,2), \ldots, f(a,N)$ как входы для забывчивого переноса.
Боб решает изучить $b$й из них, который $ф(а,б)$.
Это работает только тогда, когда $N$ очень мала, потому что требует связи и вычислений, пропорциональных $N$.
Помните, что $N$ это количество возможных входов для Боба.
Если есть схема, в которой Боб $к$ вводные провода, то у него есть $N=2^k$ возможные входы.
Следовательно, обычно у Боба слишком много входных данных, чтобы использовать этот подход.
Ответ на отредактированное сообщение:
Ваш подход к проблеме миллионера не совсем ясен, так что я должен догадаться о нескольких вещах.
Не работает раскрытие частичной информации о входах во время протокола.
Если у Алисы есть вход 1, она не сможет отличить Боба от входа 2. $2^{20}$ -- но эти два входа выглядели бы совершенно по-разному, если бы результаты сравнений были раскрыты в явном виде.
Имея это в виду, вы предлагаете как-то шифровать вещи. Но вы по сути предлагаете бинарный поиск. Бинарный поиск требует, чтобы вы знали результат предыдущих сравнений, чтобы решить, какое сравнение сделать следующим. Если вы шифруете результат сравнений, то непонятно, как действовать в следующих раундах.
Большая проблема с вашим предложением заключается в том, что оно по своей сути является последовательным. Стороны не могут знать свои входные данные для следующего раунда, пока не получат выходные данные из предыдущего раунда.
Таким образом, для $к$ сравнения, которые вам нужны $\Тета(к)$ раунды общения.
Сравните это с подходом на основе GC, который всегда использует постоянное количество раундов связи.
Я думаю, что у вас хорошая концептуальная связь.
Представьте себе функцию $f$ очень мала, так что можно записать всю таблицу истинности $f$.
скажем $f : \{1,2,3,4\}^2 \к \{0,1\}$.
Алиса выбирает случайные ключи шифрования $A_1, \ldots, A_4$ и $B_1, \ldots, B_4$.
Она также шифрует таблицу истинности $f$ как
$$\textsf{Enc}( A_1 \| B_1, f(1,1)), ~~
\textsf{Enc}( A_1 \| B_2, f(1,2)), ~~\ldots,
\textsf{Enc}( A_i \| B_j, f(i,j)), ~~\ldots$$
Оценить $f$ на своих личных входах Алиса может отправить все эти зашифрованные тексты Бобу.
Она может отправить правильный $A_i$ значение, и они могут использовать OT 1 из 4, чтобы дать Бобу возможность научиться правильному $B_j$ стоимость.
Теперь Боб может расшифровать ровно один из этих зашифрованных текстов, который будет содержать правильный вывод $f$.
Искаженные схемы — это как раз то, что вы получаете, когда берете эту простую конструкцию, но вместо того, чтобы шифровать окончательный вывод функции, вы шифруете ключи к другому гаджету того же типа.
