Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Протокол конфіденційного обчислення



В криптографії протокол конфіденційного обчислення (також безпечне / захищене / таємне багатостороннє обчислення, англ. secure multi-party computation ) - криптографічний протокол дозволяє декільком учасникам виробити обчислення залежне від таємних вхідних даних кожного з них, таким чином, щоб жоден учасник не зміг отримати жодної інформації про чужих таємних вхідних даних. Вперше завдання конфіденційного обчислення була піднята Ендрю Яо ( англ. Andrew Yao ) В 1982 році в статті [1]. Два мільйонера Аліса і Боб хочуть з'ясувати, хто ж з них багатше, при цьому вони не хочуть розголошувати точну суму свого добробуту. Яо запропонував у своїй статті оригінальний спосіб вирішення цього завдання. Набагато пізніше, в 2004 році Йехуда Лінделл (Yehuda Lindell) і Бенні Пінкас (Benny Pinkas) надали математично строге доведення коректності протоколу Яо в статті [2]. Завдання конфіденційного обчислення тісно пов'язана з завданням поділу секрету.


Формалізована постановка задачі

У конфіденційному обчисленні беруть участь N учасників p 1, p 2..., p N, у кожного учасника є таємні вхідні дані d 1, d 2,..., d N відповідно. Учасники хочуть знайти значення F (d 1, d 2,..., d N), де F - відома всім учасникам обчислювана функція від N аргументів. Допускається, що серед учасників будуть получестние порушники, тобто ті які вірно слідують протоколу, але намагаються отримати додаткову інформацію з будь-яких проміжних даних.


Опис протоколу

Для простоти припустимо, що в обчисленні беруть участь 2 учасники, тобто N = 2.

  • Уявимо функцію F у вигляді логічного контуру. На вхід логічного контуру подаються біти всіх аргументів функції F, сам контур складається з логічних гейтов AND, OR u NOT, і на виході видає результат функції F в двійковому форматі.
  • Учасник p 1 генерує для кожного проводу логічної схеми два різних випадкових числа k 0 u k 1: вони представляють нуль і одиницю в цьому дроті відповідно.
  • Учасник p 1 створює для кожного контуру зашифрування таблицю обчислення. Для бінарного гейта OR така таблиця буде виглядати наступним чином:
Вхідний провід w 1 Вхідний провід w 2 Вихідний провід w 3 Зашифрування таблиця обчислення
k_1 ^ 0k_2 ^ 0k_3 ^ 0c_1 = E_ {k_1 ^ 0} (E_ {k_2 ^ 0} (k_3 ^ 0))
k_1 ^ 0k_2 ^ 1k_3 ^ 1c_2 = E_ {k_1 ^ 0} (E_ {k_2 ^ 1} (k_3 ^ 1))
k_1 ^ 1k_2 ^ 0k_3 ^ 1c_3 = E_ {k_1 ^ 1} (E_ {k_2 ^ 0} (k_3 ^ 1))
k_1 ^ 1k_2 ^ 1k_3 ^ 1c_4 = E_ {k_1 ^ 1} (E_ {k_2 ^ 1} (k_3 ^ 1))

Тут E_ {k} (x) означає результат шифрування значення x ключем k, а D_ {k} (y) - Відповідно розшифровка шіфротекста y ключем k. Слід вибрати симетричну схему шифрування, що володіє одним додатковим властивістю: при спробі розшифрувати з неправильним ключем алгоритм повертає помилку. Сенс цієї таблиці такий: якщо ми знаємо зашифрування значення сигналу k 1 u k 2 на вхідних проводах гейта w 1 u w 2 відповідно, то ми можемо обчислити зашифрування ж значення сигналу обчисливши для всіх i = 1 ... 4 значення d_i = D_ {k_2} (D_ {k_1} (c_i)) . У трьох випадках з чотирьох повинна виникнути помилка, а в останньому четвертому ми отримаємо зашифрування значення k 3 сигналу на виході гейта.

  • Учасник p 1 передає логічний контур і зашифрування таблиці обчислення для всіх контурів учаснику p 2.
  • Учасник p 1 передає учаснику p 2 зашифрування значення сигналів вхідних проводів для тих входів, які відповідають вхідним даним учасника p 1.
  • Для кожного вхідного дроти w i відповідного вхідним даним p 2, учасник p 1 передає учаснику p 2 за допомогою протоколу забудькуватій передачі число k_i ^ {b_i} , Де b i - значення біта таємних вхідних даних p 2. При такій передачі p 1 не дізнається значення b i '.
  • Тепер у учасника p 2 є зашифрування логічна схема і зашифрування значення всіх вхідних проводів. Він обчислює в зашифрування вигляді як було описано вище все гейти схеми один-за-одним, і потім передає зашифрування результат p 1.
  • Учасник p 1 розшифровує результат і повідомляє його p 2.

Примітки

  1. Andrew Chi-Chih Yao: Protocols for Secure Computations (Extended Abstract) FOCS 1982: 160-164
  2. Yehuda Lindell, Benny Pinkas: A Proof of Yao's Protocol for Secure Two-Party Computation, Cryptology ePrint Archive, Report 2004/175

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Обчислення
Обчислення
Протокол
Паралельні обчислення
Відкладені обчислення
Сверхтьюрінговие обчислення
М'які обчислення
Хмарні обчислення
Обчислення процесів
© Усі права захищені
написати до нас
Рейтинг@Mail.ru