Нещодавно я пройшов курс CS355 (Advanced Cryptography) у Стенфорді. Нас викладали троє аспірантів Дена: Діма Коган, Флоріан Трамер і Саба Ескандарян. Кожен із трьох докторів філософії має свої особливості, а їхні напрямки досліджень також дуже різні. Діма зосереджується на технології захисту конфіденційності PIR (Private Information Retri), Флоріан зосереджується на ML і дослідженні блокчейну, а Саба зосереджується на захисті нульових знань.
Курс CS355 охоплює майже весь контент у сфері криптографії від давніх часів до сучасності. Від найдавнішої односторонньої функції (One-way Function), до еліптичних рівнянь (ECC) і Pairing, і, нарешті, до деяких із більш популярних MPC, нульового знання, приватного пошуку інформації (PIR), повністю гомоморфних алгоритмів тощо. в останні роки. Оскільки урок закінчився лише два дні тому, я організував серію нотаток, поки зміст знань був ще в моїй дрібній пам’яті. Зміст курсу дуже цікавий. Я поділюся з вами рештою вмісту пізніше, коли матиму час ~
У цьому випуску ми поговоримо про нещодавно популярне повністю гомоморфне шифрування (FHE) і супутню технологію шифрування на основі решітки.
Що таке повністю гомоморфне шифрування?
Я думаю, що багато друзів чули про назву Повністю гомоморфне шифрування (FHE). Останніми роками з’являється все більше тем про захист особистої конфіденційності, а також широко популяризуються низка технологій застосування криптографії, включаючи гомоморфне шифрування.
Щоб краще зрозуміти цю тему, я хотів би коротко представити визначення повністю гомоморфного шифрування.
Огляд системи шифрування
Перш ніж почати, давайте розглянемо найбільш традиційну систему шифрування.
Ми всі знаємо, що якщо ви хочете створити систему шифрування, вам часто потрібен ключ. За допомогою цього ключа ми можемо зашифрувати інформацію відкритого тексту в зашифрований текст на одному кінці, а потім за допомогою ключа змінити початковий вигляд зашифрованого тексту на іншому кінці. Без цього ключа іншим людям було б важко дізнатися, яку інформацію ми передали.
Ілюстрація вище показує загальну картину всіх поширених систем шифрування. Усі системи шифрування, якщо ми використовуємо більш формальний метод опису, безсумнівно, роблять три речі:
[wfpu2nagxamjfdbucmjav8e1oa4mminnrkcjznq7.png] (https://img-cdn.gateio.im/resocized-social/moments-40baef27dd-3af0f1dfb6-dd1a6f-69ad2 MS точно дізнається загальні алгоритми шифрування, такі як AES, RSA тощо. Кожен повинен також знати, що загалом системи шифрування поділяються на два типи: симетричні системи шифрування та асиметричні системи шифрування. Три кроки, які ми тут описуємо, фактично застосовні до будь-якої системи шифрування. Якщо він симетричний, то ключ, що використовується для шифрування та дешифрування, однаковий. Якщо це асиметрична система, то відкритий ключ використовується для шифрування, а інший приватний ключ використовується для дешифрування.
У дослідженнях криптографії, коли ми бачимо визначення нової системи, нам часто доводиться вказувати властивості, якими повинна володіти система.
Основне значення семантичної безпеки полягає в тому, що глядач не може розрізнити два зашифрованих повідомлення. Отже, якщо зловмисник підслуховує мережу та бачить зашифровану інформацію, яку я надсилаю, якщо система шифрування, яку я використовую, є семантично безпечною, я можу бути впевнений, що зловмисник не зможе отримати жодної інформації про зашифрований вміст із зашифрованого тексту.
Після задоволення двох вищезазначених властивостей система шифрування стає справною.
### Гомоморфне шифрування: випадкові особливі властивості
Зрозумівши, що таке система шифрування, ми можемо звернути увагу на цей зашифрований текст, який виглядає як випадково згенерований спотворений код. Ми всі знаємо, що ми не отримаємо жодної інформації, просто подивившись на сам зашифрований текст. Але чи означає це, що якщо немає ключа, а є лише зашифрований текст, ми нічого не можемо зробити?
Ми всі знаємо відповідь: ні.
Цю властивість ми називаємо адитивним гомоморфізмом. Це означає, що зашифрований шифртекст підтримує тонкий алгебраїчний зв’язок із попереднім вихідним текстом. Якщо ми складемо зашифрований текст, ми зможемо отримати новий зашифрований текст, додавши вихідний текст. Таким же чином можна зробити висновок, що також існують адитивні гомоморфні алгоритми шифрування. Ми можемо помножити зашифрований текст, згенерований мультиплікативно-гомоморфним алгоритмом, а потім отримати зашифрований текст, який відповідає результату перемноження оригінальних текстів. У всьому процесі нам не потрібно знати жодної інформації, пов’язаної з ключем, ми просто об’єднуємо зашифрований текст, який виглядає як випадковий спотворений код.
Наприклад: система анонімного голосування
Далі наведемо приклад, щоб яскраво описати практичність гомоморфного шифрування.
Ми всі знаємо, що таке онлайн-голосування: якщо керівник компанії хоче ініціювати хвилю голосування, виберіть, чи повинна компанія прийняти систему 996. Тоді керівник може попросити ІТ-спеціалістів налаштувати сервер і дозволити працівникам надати свій вибір: проголосуйте 0, щоб означати, що вони не хочуть, і проголосуйте 1, щоб означати, що вони хочуть. Після останнього періоду голосування бос може підсумувати всі голоси. Якщо підсумкова сума всіх голосів перевищить половину кількості співробітників, компанія почне 996.
Цей механізм голосування здається дуже простим, але є велика проблема конфіденційності: якщо бос хоче, щоб усіх працівників було 996, але він навмисно ініціює це голосування лише для того, щоб вивудити правоохоронних органів, щоб побачити, який працівник не бажає працювати понаднормово, тоді бос може спокійно Він довірив своєму молодшому братові підслуховувати Інтернет, записувати варіанти, подані кожним працівником, і, нарешті, дивитися, хто проголосував 0. В результаті співробітники дуже бояться і не сміють висловлювати свої почуття.
Якщо ми можемо використовувати адитивний гомоморфний алгоритм шифрування, то цю проблему можна легко вирішити.
Звичайно, ця система ще дуже недосконала, наприклад, ІТ-відділ може безпосередньо допомогти начальнику розшифрувати голоси всіх і записати їх у документ. Існують інші криптографічні інструменти, які можуть допомогти нам вирішити цю проблему. З міркувань простору тут не буде надано додаткових пояснень.
Але на цьому етапі ми повинні відчути силу гомоморфного алгоритму шифрування. Ми можемо зрозуміти це так: за допомогою гомоморфного алгоритму шифрування користувачі можуть виконувати певні безпечні обчислення через проксі (Secure Delegated Computation) з ненадійним віддаленим сервером (хмарою). Користувачі можуть використовувати технологію гомоморфного шифрування, щоб зашифрувати свій конфіденційний приватний вхід і довірити його хмарі. Потім хмара може виконати певний ступінь обчислення зашифрованих даних і, нарешті, отримати зашифрований результат, який хоче користувач, і повернути його до хмара користувач. Нарешті, користувач може використовувати ключ дешифрування, щоб відкрити результат. Протягом усієї угоди делегована сторона (хмара) ніколи не зможе побачити будь-яку корисну інформацію, пов’язану з приватним введенням.
### Класифікація гомоморфних систем шифрування
Після приблизного розуміння двох найосновніших гомоморфних властивостей стає дуже легко зрозуміти інші поняття. З систематичної точки зору гомоморфні системи шифрування умовно поділяються на чотири категорії: частковий гомоморфізм, наближений гомоморфізм, повний гомоморфізм кінцевих рядів і повний гомоморфізм.
Далі по черзі розглянемо конкретні визначення кожної категорії.
Частково гомоморфне шифрування
Найбільш елементарний етап гомоморфного шифрування називається частково гомоморфним шифруванням, яке визначається як зашифрований текст, що має лише одну гомоморфну характеристику. Цей етап включає два режими адитивного гомоморфізму та мультиплікативного гомоморфізму, які ми описали вище.
Ми отримуємо зашифрований текст, відповідний множенню цих двох повідомлень! Це властивість мультиплікативного гомоморфізму. Ми можемо продовжувати накладати нові зашифровані тексти поверх цього зашифрованого тексту, щоб ми могли отримати будь-яке множення між зашифрованими текстами.
Дещо гомоморфне шифрування
Як ми сказали в попередньому абзаці, якщо ми хочемо помножити приватні вхідні дані та отримати лінійну комбінацію між ними, простий частково гомоморфний алгоритм шифрування (RSA, ElGamal) не може бути виконаний. Тому нам потрібно переходити до наступного етапу.
Наступним етапом частково гомоморфного шифрування є приблизно гомоморфне шифрування, яке на крок ближче до повністю гомоморфного шифрування, якого ми хочемо досягти. Якщо у нас є приблизно гомоморфний алгоритм шифрування, ми можемо обчислити додавання та множення на зашифрованому тексті одночасно. Однак слід зазначити, що оскільки цей етап є приблизно гомоморфним (дещо гомоморфним), кількість додавань і множень, які можна виконати, дуже обмежена, а функція F, яку можна обчислити, також знаходиться в обмеженому діапазоні.
На даному етапі існує не так багато поширених прикладів приблизно гомоморфного шифрування. Якщо говорити про найкраще зрозумілий приклад, то це має бути циклічний груповий алгоритм шифрування, заснований на створенні пар.
Вище ми коротко розглянули алгоритм шифрування ElGamal, заснований на звичайних циклічних групах. Ми всі знаємо, що цей алгоритм є адитивно гомоморфним, що означає, що він може отримувати лінійні комбінації між довільними зашифрованими текстами. Фактично, в деяких спеціальних циклічних групах ми також можемо знайти деякі слабкі мультиплікативні властивості гомоморфізму.
Це обмеження доводить, що система приблизно гомоморфна, оскільки ми не можемо обчислити функцію F довільної логіки та глибини.
Повністю рівневе гомоморфне шифрування
Після досягнення наступного етапу ми на крок наблизилися до мети повного гомоморфізму.
Цей етап називається повністю гомоморфним шифруванням кінцевих рядів. На цьому етапі ми вже можемо виконувати будь-яку комбінацію додавання і множення на зашифрованому тексті без будь-яких обмежень щодо кількості разів.
Повністю гомоморфне шифрування (FHE)
Після багатьох викликів ми нарешті дійшли до повністю гомоморфного шифрування (FHE), якого ми чекаємо.
Як випливає з назви, повністю гомоморфна система шифрування не має обмежень щодо методів обчислення. Ми можемо довільно комбінувати зашифровані тексти, щоб сформувати нові зашифровані тексти без ключа, і новий зашифрований текст, незалежно від складності обчислення, може бути ідеально відновлений до оригінального тексту.
Коли ми досягаємо цього етапу, згадане раніше обчислення безпечного агента стає можливим. Якщо ми зможемо знайти більш ефективну повністю гомоморфну систему шифрування, ми зможемо безпечно проксі-серверити всі локальні обчислення в хмару без витоку даних!
Визначення повністю гомоморфної системи шифрування
Перш ніж почати обговорення історії повністю гомоморфних систем нижче, ми можемо систематично визначити формальне визначення повністю гомоморфних систем. Повністю гомоморфна система шифрування має чотири алгоритми:
## Історичний огляд повністю гомоморфного шифрування
Перш ніж почати вивчати, як реалізований повністю гомоморфний алгоритм шифрування, ми могли б поглянути на те, як виникла концепція повністю гомоморфного шифрування.
Концепція FHE (повністю гомоморфна) була фактично запропонована наприкінці 1970-х років. У 1978 році Рівест, Адлеман і Дертузос, кілька великих імен у криптографії, вперше згадали у своїй статті «Про банки даних і гомоморфізми конфіденційності» ідею системи, яка може виконувати певні обчислення над зашифрованим текстом і опосередковано працювати з оригінальним текстом. Пізніше ця ідея була повторно узагальнена і названа повністю гомоморфним шифруванням.
Можна побачити, що концепція повністю гомоморфного шифрування була запропонована протягом тривалого часу. Дивно, але в 1976 році, за два роки до публікації статті, був запропонований протокол обміну ключами Діффла-Хеллмана! Це свідчить про те, що фантазія експертів з криптографії ще дуже багата.
Коли була запропонована концепція FHE, уся наукова спільнота була зворушена нею і почала десятиліттями пошук, намагаючись знайти ідеальний алгоритм із повністю гомоморфними властивостями. Але за останні кілька десятиліть люди випробували всі можливі варіанти, але вони не могли знайти варіант, який задовольняв би всі умови повної гомоморфності та безпеку якого можна легко довести.
До 2009 року доктор філософії Крейг Гентрі, який навчався в Стенфордському університеті, раптом придумав ідею і прорвався через труднощі алгоритму FHE. У своїй докторській дисертації він вперше дав розумну та безпечну повністю гомоморфну систему шифрування! Ця система заснована на припущенні ідеальної решітки. Повністю гомоморфну систему, запропоновану Gentry09, часто називають повністю гомоморфною системою шифрування першого покоління.
У статті Гентрі він також згадав важливу концепцію під назвою Bootstrapping. Бутстрапінг — це спеціальна техніка обробки зашифрованого тексту. Після обробки вона може «оновити» зашифрований текст із шумом, близьким до критичного значення, у новий зашифрований текст із дуже низьким рівнем шуму. Через Bootstrapping шум системи скінченних рядів ніколи не може перевищити критичне значення, таким чином стаючи повністю гомоморфною системою. Таким чином ми можемо гомоморфно обчислити F будь-якого розміру.
Після великого прориву Гентрі все коло криптографії знову впало в божевілля, і всі почали намагатися знайти більш ефективну та універсальну повністю гомоморфну систему, засновану на ідеях, запропонованих Гентрі.
У 2011 році двоє великих хлопців, Бракерскі та Вайкуннатан, запропонували нову повністю гомоморфну систему шифрування, яка базується на Learning With Errors (LWE), ще одному припущенні ґратчастого шифрування. Того ж року Бракерскі, Джентрі та Вайкуннатан завершили систему та офіційно опублікували її. Повністю гомоморфну систему, яку вони винайшли, скорочено називають системою BGV. Система BGV є гомоморфною системою шифрування обмеженого рівня, але її можна перетворити на повністю гомоморфну систему за допомогою Bootstrapping. У порівнянні із системою, запропонованою Gentry09, система BGV використовує більш реалістичне припущення LWE. Загалом, ми називаємо систему BGV повністю гомоморфною системою шифрування другого покоління.
У 2013 році Гентрі повернувся. Джентрі, Сахай і Уотерс запустили нову повністю гомоморфну систему шифрування GSW. Система GSW подібна до BGV тим, що вона має повністю гомоморфні властивості скінченних рядів. Вона заснована на простішому припущенні LWE і може бути повністю гомоморфною через Bootstrapping. Зазвичай ми називаємо систему GSW третьим поколінням повністю гомоморфної системи шифрування.
Після 2013 року криптосфера в основному процвітала. На основі оригінальної повністю гомоморфної системи трьох поколінь з’явилися різні нові конструкції, спрямовані на оптимізацію та прискорення ефективності роботи систем BGV і GSW. IBM розробила повністю гомоморфну обчислювальну бібліотеку з відкритим вихідним кодом HElib на основі системи BGV і успішно трансплантувала її на основні мобільні платформи. Водночас є ще один проект з відкритим кодом TFHE, який також вартий уваги. TFHE базується на системі GSW із додаванням різноманітних оптимізацій та прискорень, і тепер вона дуже відома.
Окрім розробки традиційних повністю гомоморфних бібліотек, багато команд також вивчають, як краще прискорити обчислення повністю гомоморфних алгоритмів шифрування за допомогою гетерогенного обладнання, такого як GPU, FPGA та ASIC. Наприклад, cuFHE — добре відома повністю гомоморфна система шифрування на основі CUDA з прискоренням GPU.
З сьогоднішньої точки зору минуло 11 років відтоді, як Гентрі постукав у двері повністю гомоморфної системи. Зараз дослідження FHE процвітають у галузі, і багато людей вивчають повністю гомоморфні системи з різних точок зору та вимог до застосування. На сьогоднішній день ми вже маємо безліч можливих методів впровадження FHE, але те, що все ще шукає, це ефективність роботи системи FHE. Взявши як приклад поточну передову бібліотеку FHE, гомоморфне обчислення деякої відносно простої логіки на мобільній платформі може зайняти щонайменше десятки мілісекунд і навіть десятки секунд. Ці одиниці часу є надзвичайно повільними для комп’ютерних систем.
Як змусити систему FHE працювати ефективніше на гетерогенних платформах, досі залишається нерозгаданою загадкою. Якщо цю проблему одного разу вирішити, то перетворити всі комп’ютерні обчислення на повністю гомоморфні та залучити агентів до виконання обчислень у сторонніх хмарах буде легким майбутнім.
Зв'язок між FHE і MPC
Перш ніж закінчити статтю, я хотів би додати кілька слів про зв'язок між FHE і MPC. MPC означає Secure Multi-Party Computation, що є надійним багатостороннім обчисленням. Зазвичай це означає, що кілька сторін мають власні приватні вхідні дані та не хочуть розголошувати їх іншим, але вони хочуть використовувати власні вхідні дані для спільного обчислення функції F і обміну результатами обчислень.
Насправді MPC - це дуже добре відома галузь, яка вивчається протягом тривалого часу. З тих пір, як криптограф Яо Ціджі запустив свою Garbled Circuits у минулому столітті, галузь MPC отримала широке визнання та відбулося багато проривів. Зараз ми вже маємо багато бібліотек MPC, які можна використовувати, і вони також мають певну ефективність роботи.
Друзі, які знають MPC, можуть мати багато запитань після того, як побачать складну історію повністю гомоморфних систем шифрування: чому повністю гомоморфне шифрування не можна замінити безпосередньо протоколом MPC?
Дійсно, протокол MPC може повністю замінити протокол FHE. Нам потрібно лише використовувати дані користувача та приватні дані як сторони в протоколі, а потім використовувати віддалений проксі-сервер як іншу сторону, яка відповідає умовам для виконання протоколу MPC. Лише за допомогою певних взаємодій проксі-обчислення можуть бути І сервер не може бачити приватний вхід.
Але є дуже важливий момент, який ми не помітили: оскільки MPC є інтерактивним, користувач і сервер повинні обчислювати та спілкуватися разом, щоб завершити протокол. Це суперечить найфундаментальнішій вимогі агентних обчислень FHE. Якщо користувачеві потрібно весь час залишатися онлайн, щоб завершити угоду, а також сплатити частину обчислювальної потужності, тоді фактично обчислення взагалі не є «проксі», і обидві сторони лише роблять більше обчислень заради інформаційної безпеки. . Це також пояснює, чому сфера MPC зробила серйозні прориви, але сфера FHE досі невідома, оскільки дві системи вирішують абсолютно різні проблеми.
## Наступна зупинка: повністю гомоморфна система шифрування GSW
Бачачи це, кожен повинен мати дуже глибоке розуміння повністю гомоморфної системи шифрування.
Наступною зупинкою ми можемо дізнатися про повністю гомоморфну систему шифрування GSW, згадану вище. Хоча це третє покоління повністю гомоморфних систем, я думаю, що серед трьох систем Gentry09, BGV і GSW, GSW є системою з найменшою кількістю припущень, найпростішою структурою та найлегшою для розуміння. Зараз існує багато бібліотек з відкритим кодом (таких як TFHE), створених на основі системи GSW.
З міркувань простору ми закінчимо цю статтю на цьому. У наступній статті ми можемо спочатку дізнатися про основи системи GSW: систему шифрування на основі решітки та проблему LWE. Як тільки проблема LWE зрозуміла, проблема, яку вирішує GSW, стає дуже зрозумілою.
Переглянути оригінал
Ця сторінка може містити контент третіх осіб, який надається виключно в інформаційних цілях (не в якості запевнень/гарантій) і не повинен розглядатися як схвалення його поглядів компанією Gate, а також як фінансова або професійна консультація. Див. Застереження для отримання детальної інформації.
Попереднє дослідження повністю гомоморфного шифрування: визначення та історичний огляд FHE
Автор: Стівен Юе
Нещодавно я пройшов курс CS355 (Advanced Cryptography) у Стенфорді. Нас викладали троє аспірантів Дена: Діма Коган, Флоріан Трамер і Саба Ескандарян. Кожен із трьох докторів філософії має свої особливості, а їхні напрямки досліджень також дуже різні. Діма зосереджується на технології захисту конфіденційності PIR (Private Information Retri), Флоріан зосереджується на ML і дослідженні блокчейну, а Саба зосереджується на захисті нульових знань.
Курс CS355 охоплює майже весь контент у сфері криптографії від давніх часів до сучасності. Від найдавнішої односторонньої функції (One-way Function), до еліптичних рівнянь (ECC) і Pairing, і, нарешті, до деяких із більш популярних MPC, нульового знання, приватного пошуку інформації (PIR), повністю гомоморфних алгоритмів тощо. в останні роки. Оскільки урок закінчився лише два дні тому, я організував серію нотаток, поки зміст знань був ще в моїй дрібній пам’яті. Зміст курсу дуже цікавий. Я поділюся з вами рештою вмісту пізніше, коли матиму час ~
У цьому випуску ми поговоримо про нещодавно популярне повністю гомоморфне шифрування (FHE) і супутню технологію шифрування на основі решітки.
Що таке повністю гомоморфне шифрування?
Я думаю, що багато друзів чули про назву Повністю гомоморфне шифрування (FHE). Останніми роками з’являється все більше тем про захист особистої конфіденційності, а також широко популяризуються низка технологій застосування криптографії, включаючи гомоморфне шифрування.
Щоб краще зрозуміти цю тему, я хотів би коротко представити визначення повністю гомоморфного шифрування.
Огляд системи шифрування
Перш ніж почати, давайте розглянемо найбільш традиційну систему шифрування.
Ми всі знаємо, що якщо ви хочете створити систему шифрування, вам часто потрібен ключ. За допомогою цього ключа ми можемо зашифрувати інформацію відкритого тексту в зашифрований текст на одному кінці, а потім за допомогою ключа змінити початковий вигляд зашифрованого тексту на іншому кінці. Без цього ключа іншим людям було б важко дізнатися, яку інформацію ми передали.
[wfpu2nagxamjfdbucmjav8e1oa4mminnrkcjznq7.png] (https://img-cdn.gateio.im/resocized-social/moments-40baef27dd-3af0f1dfb6-dd1a6f-69ad2 MS точно дізнається загальні алгоритми шифрування, такі як AES, RSA тощо. Кожен повинен також знати, що загалом системи шифрування поділяються на два типи: симетричні системи шифрування та асиметричні системи шифрування. Три кроки, які ми тут описуємо, фактично застосовні до будь-якої системи шифрування. Якщо він симетричний, то ключ, що використовується для шифрування та дешифрування, однаковий. Якщо це асиметрична система, то відкритий ключ використовується для шифрування, а інший приватний ключ використовується для дешифрування.
У дослідженнях криптографії, коли ми бачимо визначення нової системи, нам часто доводиться вказувати властивості, якими повинна володіти система.
Основне значення семантичної безпеки полягає в тому, що глядач не може розрізнити два зашифрованих повідомлення. Отже, якщо зловмисник підслуховує мережу та бачить зашифровану інформацію, яку я надсилаю, якщо система шифрування, яку я використовую, є семантично безпечною, я можу бути впевнений, що зловмисник не зможе отримати жодної інформації про зашифрований вміст із зашифрованого тексту.
Після задоволення двох вищезазначених властивостей система шифрування стає справною.
Зрозумівши, що таке система шифрування, ми можемо звернути увагу на цей зашифрований текст, який виглядає як випадково згенерований спотворений код. Ми всі знаємо, що ми не отримаємо жодної інформації, просто подивившись на сам зашифрований текст. Але чи означає це, що якщо немає ключа, а є лише зашифрований текст, ми нічого не можемо зробити?
Ми всі знаємо відповідь: ні.
Цю властивість ми називаємо адитивним гомоморфізмом. Це означає, що зашифрований шифртекст підтримує тонкий алгебраїчний зв’язок із попереднім вихідним текстом. Якщо ми складемо зашифрований текст, ми зможемо отримати новий зашифрований текст, додавши вихідний текст. Таким же чином можна зробити висновок, що також існують адитивні гомоморфні алгоритми шифрування. Ми можемо помножити зашифрований текст, згенерований мультиплікативно-гомоморфним алгоритмом, а потім отримати зашифрований текст, який відповідає результату перемноження оригінальних текстів. У всьому процесі нам не потрібно знати жодної інформації, пов’язаної з ключем, ми просто об’єднуємо зашифрований текст, який виглядає як випадковий спотворений код.
Наприклад: система анонімного голосування
Далі наведемо приклад, щоб яскраво описати практичність гомоморфного шифрування.
Ми всі знаємо, що таке онлайн-голосування: якщо керівник компанії хоче ініціювати хвилю голосування, виберіть, чи повинна компанія прийняти систему 996. Тоді керівник може попросити ІТ-спеціалістів налаштувати сервер і дозволити працівникам надати свій вибір: проголосуйте 0, щоб означати, що вони не хочуть, і проголосуйте 1, щоб означати, що вони хочуть. Після останнього періоду голосування бос може підсумувати всі голоси. Якщо підсумкова сума всіх голосів перевищить половину кількості співробітників, компанія почне 996.
Цей механізм голосування здається дуже простим, але є велика проблема конфіденційності: якщо бос хоче, щоб усіх працівників було 996, але він навмисно ініціює це голосування лише для того, щоб вивудити правоохоронних органів, щоб побачити, який працівник не бажає працювати понаднормово, тоді бос може спокійно Він довірив своєму молодшому братові підслуховувати Інтернет, записувати варіанти, подані кожним працівником, і, нарешті, дивитися, хто проголосував 0. В результаті співробітники дуже бояться і не сміють висловлювати свої почуття.
Якщо ми можемо використовувати адитивний гомоморфний алгоритм шифрування, то цю проблему можна легко вирішити.
Звичайно, ця система ще дуже недосконала, наприклад, ІТ-відділ може безпосередньо допомогти начальнику розшифрувати голоси всіх і записати їх у документ. Існують інші криптографічні інструменти, які можуть допомогти нам вирішити цю проблему. З міркувань простору тут не буде надано додаткових пояснень.
Але на цьому етапі ми повинні відчути силу гомоморфного алгоритму шифрування. Ми можемо зрозуміти це так: за допомогою гомоморфного алгоритму шифрування користувачі можуть виконувати певні безпечні обчислення через проксі (Secure Delegated Computation) з ненадійним віддаленим сервером (хмарою). Користувачі можуть використовувати технологію гомоморфного шифрування, щоб зашифрувати свій конфіденційний приватний вхід і довірити його хмарі. Потім хмара може виконати певний ступінь обчислення зашифрованих даних і, нарешті, отримати зашифрований результат, який хоче користувач, і повернути його до хмара користувач. Нарешті, користувач може використовувати ключ дешифрування, щоб відкрити результат. Протягом усієї угоди делегована сторона (хмара) ніколи не зможе побачити будь-яку корисну інформацію, пов’язану з приватним введенням.
Після приблизного розуміння двох найосновніших гомоморфних властивостей стає дуже легко зрозуміти інші поняття. З систематичної точки зору гомоморфні системи шифрування умовно поділяються на чотири категорії: частковий гомоморфізм, наближений гомоморфізм, повний гомоморфізм кінцевих рядів і повний гомоморфізм.
Далі по черзі розглянемо конкретні визначення кожної категорії.
Частково гомоморфне шифрування
Найбільш елементарний етап гомоморфного шифрування називається частково гомоморфним шифруванням, яке визначається як зашифрований текст, що має лише одну гомоморфну характеристику. Цей етап включає два режими адитивного гомоморфізму та мультиплікативного гомоморфізму, які ми описали вище.
Ми отримуємо зашифрований текст, відповідний множенню цих двох повідомлень! Це властивість мультиплікативного гомоморфізму. Ми можемо продовжувати накладати нові зашифровані тексти поверх цього зашифрованого тексту, щоб ми могли отримати будь-яке множення між зашифрованими текстами.
Дещо гомоморфне шифрування
Як ми сказали в попередньому абзаці, якщо ми хочемо помножити приватні вхідні дані та отримати лінійну комбінацію між ними, простий частково гомоморфний алгоритм шифрування (RSA, ElGamal) не може бути виконаний. Тому нам потрібно переходити до наступного етапу.
Наступним етапом частково гомоморфного шифрування є приблизно гомоморфне шифрування, яке на крок ближче до повністю гомоморфного шифрування, якого ми хочемо досягти. Якщо у нас є приблизно гомоморфний алгоритм шифрування, ми можемо обчислити додавання та множення на зашифрованому тексті одночасно. Однак слід зазначити, що оскільки цей етап є приблизно гомоморфним (дещо гомоморфним), кількість додавань і множень, які можна виконати, дуже обмежена, а функція F, яку можна обчислити, також знаходиться в обмеженому діапазоні.
На даному етапі існує не так багато поширених прикладів приблизно гомоморфного шифрування. Якщо говорити про найкраще зрозумілий приклад, то це має бути циклічний груповий алгоритм шифрування, заснований на створенні пар.
Вище ми коротко розглянули алгоритм шифрування ElGamal, заснований на звичайних циклічних групах. Ми всі знаємо, що цей алгоритм є адитивно гомоморфним, що означає, що він може отримувати лінійні комбінації між довільними зашифрованими текстами. Фактично, в деяких спеціальних циклічних групах ми також можемо знайти деякі слабкі мультиплікативні властивості гомоморфізму.
Це обмеження доводить, що система приблизно гомоморфна, оскільки ми не можемо обчислити функцію F довільної логіки та глибини.
Повністю рівневе гомоморфне шифрування
Після досягнення наступного етапу ми на крок наблизилися до мети повного гомоморфізму.
Цей етап називається повністю гомоморфним шифруванням кінцевих рядів. На цьому етапі ми вже можемо виконувати будь-яку комбінацію додавання і множення на зашифрованому тексті без будь-яких обмежень щодо кількості разів.
Повністю гомоморфне шифрування (FHE)
Після багатьох викликів ми нарешті дійшли до повністю гомоморфного шифрування (FHE), якого ми чекаємо.
Як випливає з назви, повністю гомоморфна система шифрування не має обмежень щодо методів обчислення. Ми можемо довільно комбінувати зашифровані тексти, щоб сформувати нові зашифровані тексти без ключа, і новий зашифрований текст, незалежно від складності обчислення, може бути ідеально відновлений до оригінального тексту.
Коли ми досягаємо цього етапу, згадане раніше обчислення безпечного агента стає можливим. Якщо ми зможемо знайти більш ефективну повністю гомоморфну систему шифрування, ми зможемо безпечно проксі-серверити всі локальні обчислення в хмару без витоку даних!
Визначення повністю гомоморфної системи шифрування
Перш ніж почати обговорення історії повністю гомоморфних систем нижче, ми можемо систематично визначити формальне визначення повністю гомоморфних систем. Повністю гомоморфна система шифрування має чотири алгоритми:
Перш ніж почати вивчати, як реалізований повністю гомоморфний алгоритм шифрування, ми могли б поглянути на те, як виникла концепція повністю гомоморфного шифрування.
Концепція FHE (повністю гомоморфна) була фактично запропонована наприкінці 1970-х років. У 1978 році Рівест, Адлеман і Дертузос, кілька великих імен у криптографії, вперше згадали у своїй статті «Про банки даних і гомоморфізми конфіденційності» ідею системи, яка може виконувати певні обчислення над зашифрованим текстом і опосередковано працювати з оригінальним текстом. Пізніше ця ідея була повторно узагальнена і названа повністю гомоморфним шифруванням.
Можна побачити, що концепція повністю гомоморфного шифрування була запропонована протягом тривалого часу. Дивно, але в 1976 році, за два роки до публікації статті, був запропонований протокол обміну ключами Діффла-Хеллмана! Це свідчить про те, що фантазія експертів з криптографії ще дуже багата.
Коли була запропонована концепція FHE, уся наукова спільнота була зворушена нею і почала десятиліттями пошук, намагаючись знайти ідеальний алгоритм із повністю гомоморфними властивостями. Але за останні кілька десятиліть люди випробували всі можливі варіанти, але вони не могли знайти варіант, який задовольняв би всі умови повної гомоморфності та безпеку якого можна легко довести.
До 2009 року доктор філософії Крейг Гентрі, який навчався в Стенфордському університеті, раптом придумав ідею і прорвався через труднощі алгоритму FHE. У своїй докторській дисертації він вперше дав розумну та безпечну повністю гомоморфну систему шифрування! Ця система заснована на припущенні ідеальної решітки. Повністю гомоморфну систему, запропоновану Gentry09, часто називають повністю гомоморфною системою шифрування першого покоління.
У статті Гентрі він також згадав важливу концепцію під назвою Bootstrapping. Бутстрапінг — це спеціальна техніка обробки зашифрованого тексту. Після обробки вона може «оновити» зашифрований текст із шумом, близьким до критичного значення, у новий зашифрований текст із дуже низьким рівнем шуму. Через Bootstrapping шум системи скінченних рядів ніколи не може перевищити критичне значення, таким чином стаючи повністю гомоморфною системою. Таким чином ми можемо гомоморфно обчислити F будь-якого розміру.
Після великого прориву Гентрі все коло криптографії знову впало в божевілля, і всі почали намагатися знайти більш ефективну та універсальну повністю гомоморфну систему, засновану на ідеях, запропонованих Гентрі.
У 2011 році двоє великих хлопців, Бракерскі та Вайкуннатан, запропонували нову повністю гомоморфну систему шифрування, яка базується на Learning With Errors (LWE), ще одному припущенні ґратчастого шифрування. Того ж року Бракерскі, Джентрі та Вайкуннатан завершили систему та офіційно опублікували її. Повністю гомоморфну систему, яку вони винайшли, скорочено називають системою BGV. Система BGV є гомоморфною системою шифрування обмеженого рівня, але її можна перетворити на повністю гомоморфну систему за допомогою Bootstrapping. У порівнянні із системою, запропонованою Gentry09, система BGV використовує більш реалістичне припущення LWE. Загалом, ми називаємо систему BGV повністю гомоморфною системою шифрування другого покоління.
У 2013 році Гентрі повернувся. Джентрі, Сахай і Уотерс запустили нову повністю гомоморфну систему шифрування GSW. Система GSW подібна до BGV тим, що вона має повністю гомоморфні властивості скінченних рядів. Вона заснована на простішому припущенні LWE і може бути повністю гомоморфною через Bootstrapping. Зазвичай ми називаємо систему GSW третьим поколінням повністю гомоморфної системи шифрування.
Після 2013 року криптосфера в основному процвітала. На основі оригінальної повністю гомоморфної системи трьох поколінь з’явилися різні нові конструкції, спрямовані на оптимізацію та прискорення ефективності роботи систем BGV і GSW. IBM розробила повністю гомоморфну обчислювальну бібліотеку з відкритим вихідним кодом HElib на основі системи BGV і успішно трансплантувала її на основні мобільні платформи. Водночас є ще один проект з відкритим кодом TFHE, який також вартий уваги. TFHE базується на системі GSW із додаванням різноманітних оптимізацій та прискорень, і тепер вона дуже відома.
Окрім розробки традиційних повністю гомоморфних бібліотек, багато команд також вивчають, як краще прискорити обчислення повністю гомоморфних алгоритмів шифрування за допомогою гетерогенного обладнання, такого як GPU, FPGA та ASIC. Наприклад, cuFHE — добре відома повністю гомоморфна система шифрування на основі CUDA з прискоренням GPU.
З сьогоднішньої точки зору минуло 11 років відтоді, як Гентрі постукав у двері повністю гомоморфної системи. Зараз дослідження FHE процвітають у галузі, і багато людей вивчають повністю гомоморфні системи з різних точок зору та вимог до застосування. На сьогоднішній день ми вже маємо безліч можливих методів впровадження FHE, але те, що все ще шукає, це ефективність роботи системи FHE. Взявши як приклад поточну передову бібліотеку FHE, гомоморфне обчислення деякої відносно простої логіки на мобільній платформі може зайняти щонайменше десятки мілісекунд і навіть десятки секунд. Ці одиниці часу є надзвичайно повільними для комп’ютерних систем.
Як змусити систему FHE працювати ефективніше на гетерогенних платформах, досі залишається нерозгаданою загадкою. Якщо цю проблему одного разу вирішити, то перетворити всі комп’ютерні обчислення на повністю гомоморфні та залучити агентів до виконання обчислень у сторонніх хмарах буде легким майбутнім.
Зв'язок між FHE і MPC
Перш ніж закінчити статтю, я хотів би додати кілька слів про зв'язок між FHE і MPC. MPC означає Secure Multi-Party Computation, що є надійним багатостороннім обчисленням. Зазвичай це означає, що кілька сторін мають власні приватні вхідні дані та не хочуть розголошувати їх іншим, але вони хочуть використовувати власні вхідні дані для спільного обчислення функції F і обміну результатами обчислень.
Насправді MPC - це дуже добре відома галузь, яка вивчається протягом тривалого часу. З тих пір, як криптограф Яо Ціджі запустив свою Garbled Circuits у минулому столітті, галузь MPC отримала широке визнання та відбулося багато проривів. Зараз ми вже маємо багато бібліотек MPC, які можна використовувати, і вони також мають певну ефективність роботи.
Друзі, які знають MPC, можуть мати багато запитань після того, як побачать складну історію повністю гомоморфних систем шифрування: чому повністю гомоморфне шифрування не можна замінити безпосередньо протоколом MPC?
Дійсно, протокол MPC може повністю замінити протокол FHE. Нам потрібно лише використовувати дані користувача та приватні дані як сторони в протоколі, а потім використовувати віддалений проксі-сервер як іншу сторону, яка відповідає умовам для виконання протоколу MPC. Лише за допомогою певних взаємодій проксі-обчислення можуть бути І сервер не може бачити приватний вхід.
Але є дуже важливий момент, який ми не помітили: оскільки MPC є інтерактивним, користувач і сервер повинні обчислювати та спілкуватися разом, щоб завершити протокол. Це суперечить найфундаментальнішій вимогі агентних обчислень FHE. Якщо користувачеві потрібно весь час залишатися онлайн, щоб завершити угоду, а також сплатити частину обчислювальної потужності, тоді фактично обчислення взагалі не є «проксі», і обидві сторони лише роблять більше обчислень заради інформаційної безпеки. . Це також пояснює, чому сфера MPC зробила серйозні прориви, але сфера FHE досі невідома, оскільки дві системи вирішують абсолютно різні проблеми.
Бачачи це, кожен повинен мати дуже глибоке розуміння повністю гомоморфної системи шифрування.
Наступною зупинкою ми можемо дізнатися про повністю гомоморфну систему шифрування GSW, згадану вище. Хоча це третє покоління повністю гомоморфних систем, я думаю, що серед трьох систем Gentry09, BGV і GSW, GSW є системою з найменшою кількістю припущень, найпростішою структурою та найлегшою для розуміння. Зараз існує багато бібліотек з відкритим кодом (таких як TFHE), створених на основі системи GSW.
З міркувань простору ми закінчимо цю статтю на цьому. У наступній статті ми можемо спочатку дізнатися про основи системи GSW: систему шифрування на основі решітки та проблему LWE. Як тільки проблема LWE зрозуміла, проблема, яку вирішує GSW, стає дуже зрозумілою.