Повністю гомоморфне шифрування: технологія, що обчислює секрети

Крейг Джентрі довів, що це можливо у 2009 році, після приблизно трьох десятиліть роздумів криптографів про те, чи може таке взагалі існувати. Ідея така: ви шифруєте свої дані, передаєте їх комусь іншому, вони виконують обчислення над ними, повертають результат, і коли ви розшифровуєте цей результат, він є правильним. Людина, яка виконувала обчислення, так і не побачила ваших даних. Не очищену версію. Не хеш. Фактичні базові значення — ніколи не розкриті, навіть на мікросекунду. Це й є повністю гомоморфне шифрування — форма шифрування, яка дозволяє третій стороні виконувати обчислення над вашими даними без їх розшифровки.

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

Чому альтернативи не справляються

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

Стандартний підхід: шифрувати дані у стані спокою та під час передачі, розшифровувати перед обробкою. Ваш хмарний провайдер, ваш постачальник аналітики, ваш ML-сервіс — усі вони потребують відкритого тексту для виконання своєї роботи. Ви змушені довіряти їм. Це працює — до того моменту, коли перестає: злом, судова повістка, внутрішня загроза, неправильно налаштована політика доступу.

Довірені середовища виконання (TEE), як-от Intel SGX, створюють захищену область пам'яті, яку навіть операційна система не може зчитати. Конфіденційні обчислення відбуваються всередині анклаву. Це справді корисно, але ви довіряєте постачальнику апаратного забезпечення та покладаєтеся на те, що реалізація анклаву не має уразливостей. У SGX їх було декілька.

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

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

Механіка, коротко

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

Дві операції звучить обмежено. Але це не так. Додавання та множення над двійковими полями дають вентилі AND і XOR, які дають довільні цифрові схеми. Будь-яку функцію, яку може обчислити комп'ютер, можна виразити через ці дві операції. Це і є міст від «арифметики над зашифрованими числами» до «довільних обчислень над зашифрованими даними».

Структурна проблема — це шум. Кожна операція FHE вносить невелику похибку до шифротексту. Похибки накопичуються. Виконайте достатньо операцій — і шум поглине сигнал: шифротекст стане нерозшифровуваним. Прозріння Джентрі полягало у бутстрапінгу: гомоморфному обчисленні схеми розшифровки над зашумленим шифротекстом для отримання нового шифротексту з низьким рівнем шуму та тим самим значенням відкритого тексту. Іншими словами, ви запускаєте розшифровку всередині шифрування. Шум скидається без будь-якого розкриття даних.

Схеми, що обробляють обмежену кількість операцій до того, як шум стає критичним, називаються рівневими або частково гомоморфними. Бутстрапінг — це те, що дає право на слово «повністю» у FHE.

Де це застосовується зараз

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

Приватний ML-інференс є найбільш очевидним варіантом використання. Клієнт має конфіденційні вхідні дані. Сервер має власницьку модель. FHE дозволяє серверу обчислювати модель на зашифрованих вхідних даних і повертати зашифрований результат. Жодна зі сторін не розкриває те, що захищає. Zama реалізує це для певних архітектур моделей. Глибина схеми є передбачуваною та керованою.

Приватний геномний аналіз є еталонним робочим навантаженням з тих пір, як iDASH розпочав проведення змагань із зашифрованої геноміки у 2014 році. Оцінка ризику захворювань, загальногеномні асоціативні дослідження та вирівнювання послідовностей — усі вони мають конструкції на основі FHE. Геномні дані є одним із небагатьох типів даних, де ризик для приватності є одночасно постійним і поширюється на людей, які ніколи не давали згоди на розголошення будь-чого.

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

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

Основи безпеки

Безпека FHE зводиться до складності задачі навчання з похибками (LWE) та її кільцевого варіанту (RLWE). Ці задачі ставлять питання: маючи багато наближених лінійних рівнянь над кільцем або ґраткою, відновіть секрет. Для жодної з них не відомо жодного поліноміального алгоритму — ні на класичному, ні на квантовому апаратному забезпеченні.

Це відносить FHE до сімейства постквантової криптографії. Постквантова стандартизація NIST побудована на задачах сімейства LWE, що забезпечує додаткову перевірку та впевненість у базових припущеннях. Тим не менш, LWE перебуває під серйозними атаками менше 20 років. За RSA та еліптичними кривими стоїть понад 40 років невдалого криптоаналізу. Рівень довіри є високим, але не ідентичним.

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

Конкурентний контекст

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

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

Докази з нульовим розголошенням (ZKP) дозволяють одній стороні довести істинність твердження, не розкриваючи свідка. ZKP доводять; FHE обчислює. Вони є взаємодоповнюючими, і реальні системи використовують обидва: FHE — для приватних обчислень, ZKP — для перевірки правильності виконаних обчислень.

Гібридні протоколи, що поєднують FHE та MPC, є активною областю досліджень. Жодна з технологій окремо не задовольняє всі вимоги; їх поєднання може забезпечити кращу продуктивність і надійніші гарантії, ніж кожна з них незалежно.