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

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

Введение

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

Двустороннее конфидециальное вычисление

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

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

Примеры

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

Забывчивая передача данных

Основная статья: Забывчивая передача

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

• Начала протокола: Отправитель имеет два сообщения $S_{0}$ и $S_{1}$, получатель имеет бит $i\in \{0,1\}$.
• Конец протокола: получатель узнает сообщение $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.

Провода и их метки для вентиля

a	b	c
0	0	0
0	1	0
1	0	0
1	1	1

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

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

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

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

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

Передача данных

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

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

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

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

См. также

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