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

Введение

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

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

Алиса имеет свои секретные входные данные 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 .

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

Алиса заменяет в таблице 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}}$ .

Получение цепи?

Вычисление результата

Оптимизации

См. также

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

Примечания

Ссылки

Литература