Искаженная цепь

Искаженная цепь — это криптографический протокол для организации двустороннего конфидециального вычисления, в котором вычисляемая функция представляется в виде Булевой цепи.

Далее участников протокола будем называть Алиса и Боб.

Алиса имеет свои секретные входные данные x, Боб имеет секретные входные данные y. Протокол двустороннего конфидециального вычисления используется для того, чтобы совместно вычислить некую функцию f(x, y) таким образом, чтобы никто не узнал чужих входных данных.

• Проблема миллионеров Яо. Два миллионера хотят узнать, кто из них богаче, не разглашая при этом свое состояние.

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

• Начала протокола: Отправитель имеет два сообщения ${\displaystyle S_{0}}$ и ${\displaystyle S_{1}}$, получатель имеет бит ${\displaystyle i\in \{0,1\}}$.
• Конец протокола: получатель узнает сообщение ${\displaystyle S_{i}}$, в то время как отправитель не узнает ничего.

Протокол состоит из 6 шагов:

1. Вычисляемая функция (например, в проблеме миллионеров это функция сравнения) представляется в виде Булевой цепи с двумя входами. Вид цепи известен обеим сторонам. Этот шаг может быть сделан заренее третьей стороной.
2. Алиса искажает (зашифровывает) цепь. Алису называют искажатель.
3. Алиса отправляет искаженную цепь Бобу вместе с ее зашифрованными входными данными.
4. Боб, с помощью забывчивой передачи данных, получает свои зашифрованные входные данные от Алисы.
5. Боб восстанавливает (расшифровывает) цепь и получает зашифрованные результаты вычисления.
6. Алиса и Боб связываются чтобы узнать результат вычисления

Далее эти шаги будут описаны более подробно.

Для небольших функций можно сгенерировать цепь вручную. При генерации цепи принято использовать логические вентели AND и XOR. При этом важно, чтобы сгенерированная цепь имела минимальное количество логических вентелей AND (см. оптимизации). Для этого существуют методы генерации оптимальной (в смысле минимального количества элементов AND) цепи, использующие логический синтез.

Протокол состоит из следующих шагов:

Алиса (искажатель) на этом шаге зашифровывает Булеву цепь, чтобы получить искаженную цепь. Каждому проводу в цепи (входы и выход) Алиса присваивает по паре рандомно сгенерированных строк, называемых метками: одна строка для булевой 1 и одна для 0. (Метки имеют размер k бит, где k - параметр безопасности, обычно равный 128.) Затем в таблице истинности цепи Алиса заменяет все нули и единицы на соответствующие метки. Таблица ниже показывает таблицу истинности для логического вентиля AND с двумя входами: w_a, w_b, и выходом w_c.

Алиса заменяет в таблице 0 и 1 соответствующими метками:

a	b	c
${\displaystyle X_{0}^{a}}$	${\displaystyle X_{0}^{b}}$	${\displaystyle X_{0}^{c}}$
${\displaystyle X_{0}^{a}}$	${\displaystyle X_{1}^{b}}$	${\displaystyle X_{0}^{c}}$
${\displaystyle X_{1}^{a}}$	${\displaystyle X_{0}^{b}}$	${\displaystyle X_{0}^{c}}$
${\displaystyle X_{1}^{a}}$	${\displaystyle X_{1}^{b}}$	${\displaystyle X_{1}^{c}}$

Затем Алиса зашифровывает метки выходных значений в таблице, используя соответствующие входные метки. Полученная зашифрованная таблица называется искаженная таблица. Шифрование проводится таким образом, чтобы расшифровать запись в таблице было возможно только имея две корректные входные метки, в противном случае запись при расшифровке должна давать какой-то случайный мусор.

Искаженная таблица
${\displaystyle Enc_{X_{0}^{a},X_{0}^{b}}(X_{0}^{c})}$
${\displaystyle Enc_{X_{0}^{a},X_{1}^{b}}(X_{0}^{c})}$
${\displaystyle Enc_{X_{1}^{a},X_{0}^{b}}(X_{0}^{c})}$
${\displaystyle Enc_{X_{1}^{a},X_{1}^{b}}(X_{1}^{c})}$

В конце Алиса случайным образом переставляет строки в таблице.

Пусть Алиса и Боб имеют входные данные ${\displaystyle x}$ и ${\displaystyle y}$. Алиса отправляет искаженную таблицу и метку ${\displaystyle X_{x}^{a}}$, соответствующую ее входным данным, Бобу. Далее осуществляется забывчивая передача:

• Алиса (отправитель) имеет ${\displaystyle X_{0}^{b}}$ и ${\displaystyle X_{1}^{b}}$

• Боб (получатель) имеет ${\displaystyle y\in \{0,1\}}$

Боб получает свою метку ${\displaystyle X_{y}^{b}}$.

• Протокол конфиденциального вычисления