Коли хтось думає про шифрування, перше, що спадає на думку, це шифрування в стані спокою та шифрування під час транспортування. Перший дозволяє зберігати деякі дані на зашифрованих жорстких дисках, знімних пристроях або навіть хмарних базах даних і пропонує гарантію, що лише законний власник може бачити або редагувати вміст відкритого тексту. Шифрування під час транспортування гарантує, що дані, що передаються через Інтернет, доступні лише призначеним одержувачам, навіть якщо вони проходять через загальнодоступні маршрутизатори або канали. Обидва сценарії покладаються на шифрування з додатковою гарантією цілісності, що дані також не були підроблені зловмисником. Це відоме як автентифікаційне шифрування: після того, як дані зашифровані, ніхто в ланцюжку не може зробити висновок про будь-який біт даних (конфіденційність), і ніхто не може змінити зашифрований текст без його виявлення (цілісність/автентичність).

Деякі випадки спільного використання вимагають, щоб навіть для шифротекстів була дозволена деяка нетривіальна обробка. Це сфера методів збереження конфіденційності, або шифрування при використанні, одним з яких є повністю гомоморфне шифрування (FHE). Одним із прикладів є електронне голосування в хмарі: виборці можуть, наприклад, зашифрувати свій бюлетень, тоді якась організація посередині аггреГейт усіх бюлетенів підрахує кількість голосів, і буде опубліковано лише остаточний результат. На жаль, при автентифікованому шифруванні суб'єкту посередині потрібно буде розшифрувати всі бюлетені, щоб виконати такі обчислення, і він побачить окремі голоси у відкритому вигляді, що є досить громіздким. Теоретично ми могли б перетасувати бюлетені (деякі протоколи електронного голосування насправді покладаються на це), але, на відміну від паперових бюлетенів, традиційні криптографічні механізми, які гарантують цілісність, також значно ускладнюють від'єднання зашифрованого бюлетеня від особи його відправника. У схемі електронного голосування можна було б додати апаратну стіну навколо суб'єкта, який підраховує голоси. Це, наприклад, мета довірених анклавів страти. Такі анклави значно ускладнять зловмиснику взаємодію з сутністю. Але тоді збій в апаратному забезпеченні може призвести до витоку ключа дешифрування, і, на відміну від програмних помилок, уразливості конструкції апаратного забезпечення не можна легко виправити.

Для вирішення цього та інших подібних випадків використовується повністю гомоморфне шифрування (FHE). FHE - це спеціальна форма шифрування, яка дозволяє обчислювати функцію над криптотекстами без їх розшифрування та безпосередньо отримувати шифрування виходу функції.

Більшість часу функція f для оцінки є публічною, тому послідовність кроків обробки для перетворення шифрування f(x) є загальнодоступними знаннями і можуть бути виконані в хмарі без використання будь-якої таємниці.

На цьому малюнку зображено 3 сценарії голосування: на крайньому лівому зображенні довірена особа тасує та розшифровує окремі голоси, перш ніж опублікувати їх додавання. Ми повинні довіряти суб'єкту, який проводить обчислення, щоб зберегти конфіденційність виборців і правильно підрахувати голоси. На центральному зображенні для виконання тих самих обчислень використовується довірений анклав, якому довірено забезпечувати цілісність та гарантії конфіденційності. На правому зображенні використовується гомоморфне шифрування: зашифровані голоси можуть бути додані (публічно) до того, як результат буде розшифрований. E( ) означає операцію шифрування, а D( ) означає дешифрування.

Повністю гомоморфне шифрування також компактне, що означає, що розмір вихідного шифротексту та зусилля для його розшифрування залежать лише від кількості бітів у результаті вихідного тексту. Воно не залежить від ланцюга обчислень, які були застосовані. Це виключає тривіальні некомпактні криптосистеми, які просто конкатенують шифрований вхідний текст x з вихідним кодом f та дозволяють одержувачу виконувати всю роботу, розшифровуючи x, а потім застосовуючи f.

Аутсорсинг FHE часто представляється як альтернатива безпечним анклавам, заснований на складності математичної проблеми, а не на практичних бар'єрах. Таким чином, FHE абсолютно невразливий до пасивних атак на сторонньому каналі або інших пошкоджень хмарного хоста. Уявіть, що комусь потрібно віддати деякі обчислення на аутсорсинг, але дані дійсно конфіденційні. Ця людина, ймовірно, не захоче використовувати хмарну віртуальну машину, якщо хтось інший може бути root-користувачем на машині. Вони, ймовірно, також не наважилися б запускати його в такому анклаві, як SGX, знаючи, що процесор і пам'ять хмарних хостів постійно контролюються на предмет навантаження, потужності, температури. Можливо, з цих вимірювань можна витягти якусь інформацію. Цю людину може заспокоїти обіцянка PHE, що для вилучення будь-якого біту інформації потрібно розв'язати постквантову математичну задачу, незалежно від будь-якого виду вимірювань, які ми можемо зібрати.

Якщо конфіденційність, надана схемою, перешкоджає зловмиснику читати будь-який окремий біт інформації без секретного ключа, універсальна модифікованість FHE, з іншого боку, дозволяє зловмиснику перевертати будь-який обчислений біт: в схемі це було б еквівалентом активних атак з боковим каналом, де зловмисник отримує магічний лазерний промінь, який може націлюватися на будь-який біт. На перший погляд це може звучати дуже лякаюче, але в FHE ці атаки відповідають нечесним виконанням гомоморфних операцій. Їх можна уникнути за допомогою додавання реплікації або зайвості в обчисленні.

Повністю гомоморфне шифрування часто представляється у вигляді відкритого ключа. Є:

1. Ключ дешифрування: Це головний ключ криптосистеми, з якого можуть бути отримані всі інші ключі. Ключ дешифрування зазвичай генерується локально і ніколи не передається, і єдину особу, яка може розшифрувати FHE-шифротекст, є власник ключа дешифрування.
2. Ключ шифрування: У режимі відкритого ключа, коли сторона, яка надає початковий криптотекст, не є власником ключа дешифрування, цей середній розмір ключа зазвичай складається з випадкових шифрувань нуля. Оскільки FHE підтримує афінні функції, цього достатньо для шифрування будь-якого повідомлення.
3. Ключ оцінки: Цей ключ слід надавати будь-якій стороні, яка буде оцінювати функцію на зашифрованих текстах. Цей ключ також безпечно публікувати або передавати, як будь-який публічний ключ. Розмір ключа оцінки може варіюватися від порожнього до дуже великого, в залежності від того, чи є функція для оцінки лінійною, чи довільною.

Власник ключа розшифрування є власником найбільш чутливої таємниці криптосистеми. Ця особа відповідальна за те, щоб переконатися в легітимності ланцюжка гомоморфних операцій, які були виконані, і того, що кінцевий криптотекст безпечний для розшифрування, а потім розшифрувати результат. Якщо у ланцюжок введуть зловмисні операції, ключ розшифрування може бути витік в момент розшифрування. На щастя, гомоморфні операції можуть бути виконані публічно і перевірені.

Сценарії повністю гомоморфного шифрування

У цьому розділі ми описуємо кілька сценаріїв, в яких можна використовувати ПШГ, а також деякі переваги та недоліки кожного налаштування.

Режим віддаленого зайнятості

На цій фігурі помаранчевий ключ символізує ключ розшифрування (і його власник). FHE-шифротексти представлені замками того ж кольору, що й ключ розшифрування. Сторони, які вносять приватні дані, представлені циліндром: тут лише Елліс вносить приватні дані. На стороні Боба функція оцінки та ключ оцінки є публічними, і обчислення, зображене зеленою рамкою, може бути зроблено детерміновано. Кожен може простежити обчислення та виявити, якщо наданий вихідний шифротекст неправильний.

Історично склалося так, що це перший варіант використання, який був опублікований для FHE. Він спрямований на перетворення хмарних обчислень на приватні обчислення, аналогічні безпечному анклаву, але засновані на криптографічній безпеці, а не на апаратній. У такій обстановці Аліса володіє деякими особистими даними, але має обмежені обчислювальні можливості. Боб імітує хмарний екземпляр із набагато більшою обчислювальною потужністю. Боб не надає жодних додаткових особистих даних. Аліса може передати обчислення на аутсорсинг, шифруючи вхідні дані, потім Боб обчислює потрібну (публічну) функцію гомоморфно і відправляє зашифрований результат назад Алісі.

Зі сучасними можливостями апаратного забезпечення, режим віддаленого виконання все ще дещо повільний для повного застосування на практиці - зазвичай ми можемо порахувати надмірні витрати часу на виконання у 1 мільйон разів та надмірні витрати пам'яті у 1 тисячу разів у нелінійних випадках використання. Однак, з'являється апаратне забезпечення FHE, яке має на меті зменшити цю різницю, як, наприклад, у випадку з проект Darpa DPRIVEабоCryptoLight.

Зараз у практиці для випадків використання PIR (Private Information Retrieval) використовується режим зовнішнього замовлення, де сервер (Боб) має велику загальнодоступну базу даних, клієнт (Аліса) видає запит, а індекс, на який видається запит, повинен залишатися конфіденційним. Такі схеми PIR отримують велику користь від лінійності та компактності гомоморфних зашифрованих операцій, при цьому малий мультиплікативний глибини схем зберігає витрати на обчислення в прийнятних межах.

Ця таблиця узагальнює переваги та недоліки режиму аутсорсингу.

Режим обчислення для двох сторін

Ця фігура використовує ту саму колірну кодировку, що й раніше. На цей раз Боб вносить свій внесок у обчислення з деякими приватними даними. Обчислення з боку Боба вже не є публічно перевіреним, що символізується червоною рамкою, цей режим повинен бути обмежений використанням для чесно-цікавих випадків.

У цьому новому налаштуванні єдине відмінність полягає в тому, що Боб вносить свої приватні дані до обчислення. У цьому випадку FHE є хорошим рішенням для двохстороннього обчислення, з мінімальним обміном даними, і забезпечує міцні гарантії з боку запитувача: Боб нічого не дізнається про дані Еліс, а Еліс дізнається результат обчислення.

Потенційним застосуванням для цього сценарію була б проблема мільйонера, де Еліс і Боб - це два мільйонери, які хочуть знати, хто багатший, не розголошуючи своє багатство іншій стороні. Рішення цієї проблеми використовуються в додатках електронної комерції.

Режим агрегації

Це уточнення режиму зовнішнього використання, де дані від багатьох учасників можуть бути агреговані компактним (в тому сенсі, що обсяг виводу не зростає з кількістю учасників) та публічно перевіряемим способом. Типові використання включають федеративне навчання та електронне голосування.

Режим клієнт-сервер

Ця настройка є удосконаленням режиму обчислення для двох сторін, де обчислювальна сторона тепер надає безпечну обчислювальну послугу для кількох клієнтів, які мають власний секретний ключ. Наприклад, Повністю гомоморфне шифрування може використовуватися як приватна служба передбачення моделі (наприклад, служба машинного навчання з приватною моделлю та введеннями): сервер має приватну модель (приватну, але у текстовому форматі), і кожен клієнт має власні дані та бажає виконати передбачення. У результаті кожен клієнт отримує власне зашифроване передбачення зі своїм власним секретним ключем.

Як гомоморфне шифрування забезпечує легітимність обчисленої функції?

Завжди простіше використовувати FHE у спільних сценаріях, де кожен учасник має стимул чесно слідувати протоколу. Наприклад, FHE можна використовувати для обчислення статистики між двома юридичними особами однієї групи у двох різних країнах: такі правила, як GDPR, дозволяють публікувати деякі статистичні дані, але забороняють загалом збирати всі індивідуальні дані в одному місці. У цьому випадку використання FHE можливе і всі учасники мають стимул чесно слідувати протоколу. У сценарії, не пов'язаному зі спільною роботою, найпростіший спосіб переконатися, що відповідна функція була обчислена, — це ввести надмірність. Наприклад, у сценаріях аутсорсингу та агрегації гомоморфні обчислення є повністю публічними і можуть бути детерміновані. До тих пір, поки дві або більше незалежних сутностей в кінцевому підсумку отримують один і той же вихідний шифротекст, тоді обчислення є правильним, а результат безпечним для розшифровки. Чим більше резервування, тим вищу впевненість ми можемо мати в результаті, що, звичайно, є компромісом з ефективністю.

Крім того, коли обчислювальна сторона підтверджує результат FHE, цифровим підписом вводу та виводу шифротекстів, кожен може повторити те ж саме FHE обчислення та перевірити, чи є доказ дійсним. Будь-яка спроба шахрайства з боку обчислювальної сторони FHE може бути публічно виявлена і пов'язана з публічно перевіреною сертифікацією, яка розкриває шахрайство та шахрая – ми називаємо таку модель сильною прихованою моделлю безпеки.

Повністю гомоморфні підписи - це ще один спосіб перевірки правильності обчислень без необхідності незалежного перевірника, але, як правило, вимагає набагато більше ресурсів.

Як FHE забезпечує, що кінцевий отримувач розшифровує лише кінцевий результат, а не проміжні змінні?

Найпростіший спосіб зробити це - забезпечити, щоб власник ключа дешифрування не мав доступу до проміжного шифротексту.

У двосторонньому сценарії, або в клієнт-серверному, Аліса шифрує вхідні дані, Боб виконує обчислення над криптографічними текстами та передає зашифрований вихід назад до Аліси, зрозуміло, що Аліса зможе розшифрувати результат, але вона не має доступу до будь-якої іншої змінної.

У сценарії об'єднання в хмару, наприклад, при електронному голосуванні, де багато учасників надсилають зашифровані бюлетені на загальну хмару, використовується ще одна техніка: ключ розшифрування, в загальному випадку, не надається одному одержувачу, але замість цього таємно ділиться між різними учасниками органу розшифрування. У цьому випадку розшифрування може бути запущено лише на одному конкретному шифротексті шляхом виконання мультипартійного обчислення, яке передбачає онлайн-комунікацію між учасниками органу. Якщо один з учасників відмовляється розшифрувати шифротекст, розшифрування неможливе. Це забезпечує те, що розшифрувати можна лише шифротексти, затверджені всіма членами органу.

Будівельні блоки гомоморфного шифрування

Існує три види гомоморфного шифрування: часткове гомоморфне шифрування (PHE), вирівняне гомоморфне шифрування (LHE) і повністю гомоморфне шифрування (FHE). Часткове гомоморфне шифрування дозволяє нам обчислювати лише обмежений набір функцій (наприклад, лише суму, лише лінійні функції, лише білінійні функції), тоді як вирівняне та повністю гомоморфне шифрування може оцінювати довільні схеми, або, що еквівалентно, функції, потоки керування якими не залежать від даних. Для LHE криптографічні параметри залежать від функції і зростають зі складністю схеми, що, в свою чергу, призводить до більших шифротекстів і ключів. Схеми FHE дозволяють для заданого набору параметрів, а отже, і для заданого ключа і розміру шифротексту, обчислити будь-яку функцію, яка може бути представлена у вигляді схеми з арифметичними або двійковими вентилями. Тобто, на відміну від ЛПГ, навіть якщо схема для оцінки зростає все більше і більше, параметри схеми (і ключі, і шифротексти) не стають більшими.

Іншими словами, коли ставиться питання, чи може дана схема відкритого тексту бути виконана гомоморфно, і якою ціною (у часі та накладних витратах на пам'ять), PHE is може відповісти «ні» на запитання. LHE відповідає ствердно, але може встановити довільну високу вартість для складних схем. FHE також відповідає ствердно, і, крім того, надає ключі, алгоритми шифрування та дешифрування, а також те, як гомоморфно оцінити універсальний набір Gates ще до того, як буде вказано схему відкритого тексту. Таким чином, FHE є єдиним режимом, який гарантує, що пам'ять і час виконання гомоморфної оцінки залишаються пропорційними вихідній схемі відкритого тексту. Для цього всі відомі сьогодні схеми FHE мають справу із зашумленими шифротекстами, які стають все більш і більш шумними в міру виконання обчислень. Щоб уникнути переповнення шуму під час обчислень і призводить до помилок дешифрування, ці схеми регулярно виконують досить дорогу операцію, яка називається початковим завантаженням, яка зменшує шум до керованого рівня. Більше про специфіку кожного виду схеми, про початкове завантаження, а також про те, як мінімізувати шум та інші витрати за допомогою компіляторів PHE, у другому блозі цієї серії!

Disclaimer：

1. Ця стаття передрукована з [cryptographycaffe], Всі авторські права належать оригінальному автору [Ніколяс Гама і Сандра Гуаш]. Якщо є заперечення стосовно цього повторного друку, будь ласка, зв'яжіться з Gate Learnкоманди, і вони негайно з цим впораються.
2. Відмова від відповідальності: Погляди та думки, висловлені в цій статті, належать виключно автору і не становлять жодної інвестиційної поради.
3. Переклади статті на інші мови виконуються командою Gate Learn. Якщо не зазначено інше, копіювання, поширення або плагіат перекладених статей заборонені.