Гомоморфне шифрування: обчислення даних без їх розкриття

Що дозволяє робити шифрування подібністю

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

Частково гомоморфне шифрування проти повного гомоморфного шифрування

Не всі схеми гомоморфного шифрування однаково потужні. Частково гомоморфне шифрування підтримує лише один тип операції, яка виконується необмежену кількість разів над зашифрованими даними. Наприклад, криптосистема Пайєра є додатно гомоморфною: ви можете додавати разом зашифровані числа, що корисно для завдань, таких як підрахунок зашифрованих голосів або агрегація зашифрованих фінансових значень. На відміну від цього, незахищений RSA є множинно гомоморфним, дозволяючи множити разом зашифровані значення. Ці схеми ефективні та добре вивчені, але обмежені в обсязі, оскільки реальний обчислювальний процес зазвичай потребує більше одного типу операцій. Повне гомоморфне шифрування, або FHE, підтримує як додавання, так і множення разом над зашифрованими даними. Ця комбінація виявляється достатньою для побудови будь-якого обчислення, оскільки будь-який цифровий пристрій, а отже й будь-який алгоритм, можна побудувати лише з цих двох основних операцій, які діють як логічні будівельні блоки (приблизно аналогічно вентилям AND і XOR). Це робить FHE набагато більш амбітним, ніж часткові схеми: замість того, щоб дозволити одне вузьке завдання, воно теоретично дозволяє запускати будь-які програми повністю над зашифрованими вхідними даними, що й було причиною його довготривалої погоні як «святого Graila» криптографії.

Генті’s 2009 прорив та криптографія на основі латентності

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

Проблема шуму та закладення (bootstrapping)

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

Практична значущість та поточні обмеження

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

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Homomorphic Encryption: Computing on Data Without Ever Seeing It і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.