Програмована криптографія

Хоча шифрування існує вже тисячі років, програмована криптографія є сучасною технологією. Описується як «криптографія загального призначення … [або] експресивна мова для претензій», це ідея, що криптографічний примітив, як ZK-доказ, можна зробити достатньо гнучким і адаптивним, щоб розробник міг програмувати майже будь-яку функцію поверх нього. Що може існувати безперервний ланцюг логіки від того, хто натиснув кнопку на веб-сайті, до математичних доказів, які гарантують безпеку криптографічної операції.

https://youtu.be/qAfprVCBhdQ?t=1024

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

Докази ZK були вперше задумані в 1989 році, але залишалися в основному теоретичними до 2012 року, коли був відкритий тип доказів ZK під назвою zk-SNARK. Цей новий примітив дозволив доказам ZK довести чи підтвердити автентичність майже будь-якої функції чи довільного обчислення.

З тих пір, як zkSNARKS став можливим, ресурси та талант були спрямовані на створення zCash, zkRollups, zkEVM та безлічі інших програм, які починаються з літери z. Виявилося, що децентралізовані системи, як-от Ethereum, і блокчейни в цілому були ідеальною мотивацією зацікавити людей криптографією, перетворивши колись непрактичну область досліджень на активну екосистему з реальними додатками для кінцевих користувачів.

Немає жодних гарантій, що Multi-Party Computation (MPC), Fully Homomorphic Encryption (FHE) і Indistinguishable Obfuscation (iO) підуть тим самим шляхом, що й ZK, стаючи з часом більш практичними, оптимізованими та загальними. Але на цьому ранньому етапі це, звичайно, можливо.

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

Відносно інтуїтивні порівняння

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

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

Ви також можете розглядати кожну з цих систем як заміну уявного спільного друга. Вікіпедія називає цього друга «Тоні». Тоні непогрішимий, непідкупний і цілком заслуговує довіри. Робота Тоні - зберігати таємниці. У наведеній нижче таблиці подумайте про «Приватні елементи» як про те, які секрети Тоні можна довірити, про «Випадки використання» як про завдання, які Тоні міг виконувати достатньо добре, а про «Практичність» про те, наскільки майстерно Тоні міг би виконувати ці завдання сьогодні.

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

Багатостороннє обчислення (MPC)

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

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

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

Проблеми мільйонера

MPC був розроблений у 1982 році Ендрю Яо для вирішення мисленнєвого експерименту під назвою «Проблема мільйонера», коли два мільйонери хочуть знати, хто багатший, не повідомляючи один одному, скільки у них грошей. Рішення полягало у використанні спотворених схем, що, за словами Віталіка Бутеріна, частого пояснювача криптографічних концепцій, також є одним із найпростіших способів подумати про MPC.

[Перш ніж дізнатися про спотворену схему, вам потрібно знати, що таке арифметична схема взагалі. Якщо ви вперше знайомі зі схемами, тут є просте пояснення.]

MPC — це багатоступеневий інтерактивний процес, у якому мільйонер №1 (Аліса Смітник) повинна спочатку створити схему, ввести свій власний капітал, а потім перетворити її в спотворену або зашифровану форму перед тим, як передати її мільйонеру №2 (Боб Оцінювач ). Коли Боб отримує в руки схему, його завдання полягає в тому, щоб додати власний капітал, а потім оцінити або запустити схему, щоб переконатися, що вона правильна. Нарешті Боб розшифровує кінцевий результат і, наприклад, дізнається, що Аліса багатша, але ніколи не дізнається, що Аліса насправді набагато багатша, і йому не слід було робити припущення.

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

Повністю гомоморфне шифрування (FHE)

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

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

https://www.zama.ai/post/the-revolution-of-fhe

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

Якщо це спрацює, FHE стане однією з найпотужніших доступних технологій для збереження конфіденційності. А хто знає? Через 10 років ми навіть можемо мати FHE-EVM.

Управління шумом

Порівняно з MPC і ZK, FHE – на даний момент – на більш теоретичному або менш практичному кінці спектра. Технологію вважали можливою тільки в 2009 році, коли Крейг Гентрі зрозумів, як боротися з шумом.

Операції FHE дуже інтенсивні з точки зору обчислень, оскільки під час процесу шифрування додається «шум» для підвищення безпеки. Шум у FHE — це невелике випадкове значення, додане до відкритого тексту (незашифрованих даних) перед тим, як він перетворюється на зашифрований текст (зашифровані дані). Кожна операція збільшує шум. У той час як операції додавання та віднімання викликають незначне зростання шуму, множення є дорожчим з точки зору обчислень, що призводить до значного зростання шуму. Отже, коли складність програми зростає, накопичується шум – простір, необхідний для розміщення шуму, і обчислювальні ресурси, необхідні для обробки шуму.

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

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

Обфускація нерозрізнення (iO)

Якщо FHE перетворює всі елементи обчислення в чорний ящик, то iO перетворює саме обчислення в чорний ящик.

Обфускація нерозрізнення (iO) вважається найпотужнішою криптографічною системою в межах теоретичної можливості. В одній статті iO описується як «майстер-інструмент, з якого можна створити майже будь-який інший криптографічний протокол», а експерти з криптографії називають «перлиною в короні» та «одним криптографічним примітивом, який керує ними всіма».

За словами Аміта Сахаї, професора, відомого тим, що він пояснює дітям докази ZK, і одного з дослідників, які винайшли спосіб побудови iO на добре обґрунтованих припущеннях, iO працює за принципово іншою парадигмою, ніж попередні криптографічні системи. IO припускає, що супротивник уже може читати ваші думки (метафора для вашого комп’ютера). Ваші секрети вже відомі, тому їх не можна приховати. Єдине, що ви можете зробити, це затьмарити те, що вже бачить супротивник.

https://youtu.be/v2RR_c5hn1E

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

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

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

Обґрунтовані припущення

Ніхто не знав, як побудувати iO до 2013 року, коли багатолінійні карти були запропоновані Гаргом, Гентрі, Халеві, Райковою, Сахай, Уотерсом. Комп’ютерну програму можна розбити, як шматочки головоломки, а потім приховати за допомогою багатолінійних карт. Приховані фрагменти можна було зібрати заново, щоб досягти тієї ж функціональності, що й оригінальна програма, не розкриваючи її внутрішньої роботи.

Багатолінійні карти є узагальненням білінійних карт або пар, які використовуються в криптографії еліптичних кривих (ECC). Хоча білінійні карти є основою для існуючих криптографічних схем, таких як підписи BLS, вони недостатньо складні чи виразні для iO. І хоча багатолінійні карти могли працювати з iO, цю нещодавно розроблену алгебраїчну структуру було легко атакувати та не було безпечно, тому покладатися на багатолінійні карти, як правило, не задовольняло криптографів. Поле знову застрягло.

Тоді, у 2020 році, Джейн, Лін і Сахай запропонували рішення, яке, незвичайне та нове, було досить простим для міркувань криптографів, і замість того, щоб покладатися на нещодавно розроблені припущення, такі як багатолінійні карти, ця версія iO могла бути побудована на більшій основі. стандартні та добре обґрунтовані припущення, які вивчалися десятиліттями, такі як навчання з помилками (LWE). Завдяки цьому останньому прориву iO знову став можливим. Святий Грааль був ще під рукою.

Неприборкана пустеля

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

У презентації на iO Сахай описав поле як «неприручену пустелю», де навіть не було зрозуміло, що не зрозуміло і які проблеми потрібно вирішити.

Такі команди, як PSE, в основному працюють над практичною чи прикладною стороною програмованої криптографії, зосереджуючись на таких примітивах, як ZK і MPC із добре обґрунтованими припущеннями, які були перевірені в боях, відносно оптимізовані та вважаються безпечними та ефективними. Хоча залишилося багато оптимізацій, ZK тепер твердо входить у сферу практичності. Але був також час, коли ZK був обмежений неприборканою пустелею.

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

Презентація Сахаї містить цитату зі статті Стівена Вайнберга в журналі Nature 2003 року під назвою «Чотири золоті уроки», яка підкреслює ще одну причину працювати над тим, що зараз є непрактичним.

«Коли я викладав у Массачусетському технологічному інституті наприкінці 1960-х років, один студент сказав мені, що він хотів би зайнятися загальною теорією відносності, а не сферою, над якою я працював, фізикою елементарних частинок, оскільки принципи першої були добре відомі. , а останнє здавалося йому безладом. Мене вразило, що він щойно дав цілком вагому привід для того, щоб зробити протилежне… Моя порада: піти на безлад — ось де дія».

Програмована криптографія досліджується різними командами, включаючи PSE та 0xPARC, співорганізаторами 2-денної події під назвою Programmable Cryptography Conference, яка відбудеться в Стамбулі, Туреччина, 16 і 17 листопада 2023 року.

Приходь привітайся!

Або знайдіть PSE онлайн на Discord.

Відмова від відповідальності:

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