Криптограф, який гарантує, що ми можемо довіряти своїм комп’ютерам | Журнал Quanta

Яель Тауман Калай — піонер-теоретик-інформатик, який отримав вражаючі нагороди та змінив уявлення людей про Інтернет. Але в дитинстві вона не була зразковою ученицею.

«Я була проблемою, — сказала вона. «Мене фактично — не зовсім, але фактично — вигнали зі середньої школи».

Калай народився і виріс у Тель-Авіві, Ізраїль, в академічній родині. Її батько, Яір Тауман, є економістом і теоретиком ігор. Уроки в старшій школі набридли їй — один табель задокументував близько 150 пропусків у школі, згадує вона, оскільки вона воліла проводити час, катаючись на водних лижах і спілкуючись. Але її аналітичні здібності завжди були присутні.

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

Її приспана любов до математики остаточно прокинулася в коледжі, коли вона почала усвідомлювати її красу. Згодом вона виявила, що може застосувати цю математику для комп’ютерів і, зокрема, для захисту інформації. Зараз її робота стосується математики та інформатики, а її ідеї стали основою для того, як ми захищаємо та перевіряємо обчислення в епоху цифрових технологій. Протягом останніх двох десятиліть вона працювала над забезпеченням цілісності наших смартфонів, хмарних з’єднань і навіть криптовалют. Зараз вона є дослідником у Microsoft і ад’юнкт-професором Массачусетського технологічного інституту. Нещодавно вона отримала престижну премію ACM з обчислювальної техніки Асоціації комп’ютерних машин за «прорив у верифікованому делегуванні обчислень і фундаментальний внесок у криптографію». Її остання робота також спрямована в майбутнє, оскільки вона розглядає, як квантові комп’ютери можуть вплинути на ландшафт безпеки.

Quanta поговорив з Калаєм про витік секретів, перевірку хмари та цікавість квантових обчислень. Інтерв’ю було скорочено та відредаговано для ясності.

Як ви пройшли шлях від шкільного скандаліста до вченого?

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

Що вас захопило в математиці?

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

Але коли я шукав хороше дослідницьке запитання, усе здавалося поступовим. Тож я почав займатися інформатикою. І криптографія була саме тим, чого мені не вистачало, тому що вона має справу з проблемами реального світу. Сьогодні криптографія використовується повсюдно. Він використовується для забезпечення конфіденційності та автентичності повідомлень, які ми надсилаємо. Коли я спілкуюся з кимось, як я знаю, що повідомлення, яке я отримав, є тим, яке було надіслано? Як я можу дізнатися, що людина, яка стверджує, що надіслала повідомлення, насправді його надіслала? Що значить це знати? Концепції дуже філософські, і те, як ми це моделюємо математично, справді чудово. Мене це вразило як чистотою математики, так і застосовністю.

Над якими криптографічними проблемами ви працювали?

Моя магістерська робота називалася «Як розкрити секрет». Ось проблема: ми знаємо, як поставити цифровий підпис, щоб сказати: «Це я написав це повідомлення». Але скажімо, я хочу підписати щось як професор Массачусетського технологічного інституту, але я не хочу, щоб люди знали, що це я? Таким чином, секрет тримає воду, тому що ви знаєте, що його підписав професор MIT, але ви не знаєте, хто.

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

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

Чи скористається установа цією системою?

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

Як ваша робота перетворилася на аналіз безпеки наших пристроїв?

На початку 2000-х років я закінчував свою докторську роботу, працюючи з Шафі Голдвассером в MIT. Люди тільки почали говорити про хмарні обчислення, якими ми зараз користуємося щодня. Раніше у вас був величезний робочий стіл, де все робилося. Зі збільшенням збору великих даних обчислення стали дорожчими, і їх почали виконувати віддалено. Ідея полягає в тому, що існує потужна хмара, яка виконує обчислення за вас. Але ви можете не довіряти хмарній платформі, тож як ви знаєте, що вони роблять обчислення правильно? Іноді може виникнути стимул для шахрайства, оскільки обчислення можуть бути дуже дорогими. І тоді в деяких налаштуваннях ви можете турбуватися про випадкову помилку. Тож вам справді потрібен доказ того, що це обчислення правильне.

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

Як з’явилися ці докази?

Це почалося в 1985 році з Шафі Голдвассера, Сільвіо Мікалі та Чарльза Ракоффа, які разом представили поняття інтерактивних доказів. Раніше, коли люди думали про докази, вони думали про написання рядків даних, і ви можете прочитати та перевірити, чи вони правильні чи ні. Голдвассер, Мікалі та Ракофф представили зовсім інший спосіб доведення чогось: використання взаємодії. Є верифікатор і верифікатор, і вони обмінюються повідомленнями туди-сюди. Потім верифікатор вирішує, переконали вони чи ні.

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

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

Але недоліком інтерактивного доказу є те, що його неможливо передати. Скажімо, ви даєте мені стодоларову купюру і доводите, взаємодіючи, що вона справді коштує 100 доларів. Я хочу мати можливість це передати. Я хочу віддати це комусь іншому, хто віддає це комусь іншому. Але якби я мав лише інтерактивний доказ, це нічого не означає; Я не можу віддати його нікому іншому. Тож приємно в SNARG те, що ви можете подарувати їх комусь іншому.

Як сертифікат автентичності?

точно. Блокчейни є основним місцем, де вони сьогодні використовуються для перевірки транзакцій. Коли з’явився блокчейн, я сказав своїм студентам, що ми повинні відправити розробнику біткойнів Сатоші Накамото квіти та шоколад, тому що він дійсно зробив нашу роботу такою актуальною.

Отже, як усунути взаємодію для створення цих сертифікатів, які можна передавати?

З криптографією. Дозвольте мені спробувати зрозуміти, як це працює. У наших інтерактивних доказах верифікатор зазвичай просто надсилає довільність перевіряючому — ви можете подумати про це як верифікатор, який випадково вибірково перевіряє доказ. Потім у Амоса Фіата та Аді Шаміра виникла ідея: навіщо вам цей верифікатор, якщо все, що він робить, це надсилає випадкові дані? Можливо, ми можемо замінити цей верифікатор якоюсь функцією, як-от хеш-функцією — це функція, яка виглядає випадковою, і це дуже важливий будівельний блок у криптографії.

І виявляється, що так, ми можемо. Сьогодні це робиться постійно. Якщо у вас є iPhone або Android, ви використовуєте парадигму Fiat-Shamir, коли ваш телефон підключається до віддалених серверів, що може відбуватися часто протягом дня. І саме цю парадигму ми використовуємо для створення коротких доказів, які засвідчують, що віддалені обчислення правильні.

Ви говорили про те, що машини повинні бути «постквантово захищеними». Що це означає?

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

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

У 2018 році відбувся прорив результат студенткою Берклі Урмілою Махадев. Вона була першою, хто продемонстрував класичне обчислювально безпечне підтвердження для перевірки квантових обчислень.

Отже, ви можете використовувати класичний комп’ютер для перевірки квантових обчислень? Це звучить неможливо!

Хіба це не дивовижно? Я був у програмному комітеті, коли Урміла опублікувала свою статтю, і всю ніч дивився на неї — скільки кофеїну я випив! Я був ошелешений. На той момент я був повним квантовим манекеном. Я зрозумів крипточастину, але мені знадобився деякий час, щоб зрозуміти, як це поєднується з квантовою частиною. І це було красиво.

Перехід від класичних до квантових обчислень звучить як крута крива навчання.

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