Криптограф, который гарантирует, что мы можем доверять нашим компьютерам | Журнал Кванта

Яэль Тауман Калай — ученый-теоретик-новатор, завоевавший впечатляющие награды и изменивший представление людей об Интернете. Но в детстве она не была образцовой ученицей.

«Я была возмутительницей спокойствия, — сказала она. «Меня в основном — не совсем, но в основном — выгнали из средней школы».

Калай родился и вырос в Тель-Авиве, Израиль, в академической семье. Ее отец, Яир Тауман, экономист и теоретик игр. Уроки в старшей школе ей наскучили — в одном табеле было зафиксировано около 150 пропусков занятий, вспоминает она, поскольку она предпочитала проводить время, катаясь на водных лыжах и общаясь. Но ее аналитические способности всегда были рядом.

«Когда мои родители не отпускали меня гулять, часто единственным способом заставить отца согласиться было сказать ему: «Хорошо, задай мне математическую загадку. Как хочешь, но если решу, пойду». Обычно она шла.

Ее дремлющая любовь к математике окончательно пробудилась в колледже, когда она начала осознавать ее красоту. В конце концов, она обнаружила, что может использовать эту математику с компьютерами и, в частности, для защиты информации. Теперь ее работа охватывает области математики и информатики, и ее идеи легли в основу того, как мы защищаем и проверяем вычисления в эпоху цифровых технологий. Последние два десятилетия она работала над обеспечением целостности наших смартфонов, облачных подключений и даже криптовалют. В настоящее время исследователь в Microsoft и адъюнкт-профессор Массачусетского технологического института. Недавно она получила престижную премию ACM в области вычислительной техники Ассоциации компьютерных машин за «прорывы в поддающемся проверке делегировании вычислений и фундаментальный вклад в криптографию». Ее последняя работа также обращена в будущее, поскольку она рассматривает, как квантовые компьютеры могут повлиять на ландшафт безопасности.

Quanta поговорил с Калаи об утечке секретов, проверке облака и необычности квантовых вычислений. Интервью было сокращено и отредактировано для ясности.

Как вы прошли путь от школьного нарушителя спокойствия до академика?

Я всегда знал, что люблю математику, но математика в старшей школе совсем не была интересной. Потом я пошел изучать математику в бакалавриате и был потрясен. Это первый раз в моей жизни, когда я сидел и учился без остановки, с утра до ночи. Я был в эйфории. И должен сказать, я был немного расстроен, потому что подумал: «Не могу поверить, что мог получать удовольствие от этого, когда был намного моложе!»

Чем вас привлекла математика?

Он очень чистый, элегантный и абстрактный. И некоторые понятия в математике нелогичны; Помню, я чувствовал, что его изучение меняет меня как личность. Вы учитесь быть смиренным, потому что снова и снова понимаете, что ваша интуиция ошибочна.

Но когда я искал хороший исследовательский вопрос, все казалось постепенным. Так я начал двигаться в сторону информатики. И криптография была именно тем, чего мне не хватало, потому что она имеет дело с реальными проблемами. Сегодня криптография используется повсеместно. Он используется для обеспечения конфиденциальности и подлинности отправляемых нами сообщений. Когда я переписываюсь с кем-то, как я узнаю, что полученное сообщение является отправленным? Как я узнаю, что человек, утверждающий, что отправил сообщение, действительно его отправил? Что значит знать это? Концепции очень философские, и то, как мы моделируем их математически, действительно красиво. Это попало в точку для меня, как чистота математики, так и применимость.

Над какими криптографическими задачами вы работали?

Моя магистерская работа называлась «Как выдать секрет». Вот в чем проблема: мы знаем, как поставить цифровую подпись — сказать: «Это я написал это сообщение». Но, скажем, я хочу что-то подписать как профессор Массачусетского технологического института, но не хочу, чтобы люди знали, что это я? Таким образом, секрет действительно выдерживает критику, потому что вы знаете, что его подписал профессор Массачусетского технологического института, но вы не знаете, кто.

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

Кольцевые подписи похожи. В группе потенциальных утечек секрета вы можете думать о каждом человеке как о обладателе секретного ключа. И кольцевая подпись, по сути, доказывает, что это сообщение было подписано кем-то с помощью одного из секретных ключей, но не раскрывает, какой секретный ключ ему известен. Он скрывает, чей секретный ключ был использован.

Будет ли учреждение когда-либо использовать эту систему?

Это прекрасно и пугающе — я могу сделать это без чьего-либо участия. Я могу подписать как член группы без разрешения группы. Непонятно, фича это или баг, но ясно, что это научное открытие. Использовались кольцевые подписи — существует криптовалюта под названием monero, в которой говорится, что они используют ее для обеспечения конфиденциальности транзакций. Но, честно говоря, я действительно не знаю, кто использует нашу работу. Правда в том, что я слишком занят, чтобы следить за этим.

Как ваша работа превратилась в анализ безопасности наших устройств?

В начале 2000-х я заканчивал свою докторскую диссертацию, работая с Шафи Голдвассером в Массачусетском технологическом институте. Люди только начали говорить об облачных вычислениях, которые теперь мы используем каждый день. Раньше у вас был огромный рабочий стол, на котором все делалось. С увеличением сбора больших объемов данных вычисления стали более затратными, и их стали выполнять удаленно. Идея в том, что существует мощное облако, которое выполняет вычисления за вас. Но вы можете не доверять облачной платформе, так как же узнать, правильно ли они выполняют вычисления? Иногда может быть стимул к мошенничеству, потому что вычисления могут быть очень дорогостоящими. А то в некоторых настройках вас может беспокоить случайная ошибка. Итак, вам действительно нужно доказательство того, что это вычисление верно.

Но обычно доказательства очень длинные, а слабые устройства не могут проверить длинные доказательства. Даже для устройств, которые могут, это очень дорого. Так есть ли способ уменьшить доказательства? Информационно-теоретически нет. Но оказывается, что с помощью криптографических инструментов мы можем генерировать краткие сертификаты, которые очень и очень трудно подделать. Они называются краткими неинтерактивными аргументами или SNARG. Это не доказательство, на самом деле. Но пока вы не можете решить какую-то проблему, которую мы, криптографы, считаем очень сложной, например факторизацию больших чисел, вы не сможете подделать краткие доказательства.

Как появились эти доказательства?

Это началось в 1985 году с Шафи Голдвассера, Сильвио Микали и Чарльза Ракоффа, которые вместе ввели понятие интерактивных доказательств. Раньше, когда люди думали о доказательствах, они думали о записи строк данных, которые можно прочитать и проверить, верны они или нет. Гольдвассер, Микали и Ракофф представили совершенно иной способ доказательства чего-либо: использование взаимодействия. Есть доказывающий и проверяющий, и они обмениваются сообщениями туда и обратно. Затем проверяющий решает, убежден он или нет.

Позвольте мне привести вам пример интерактивного доказательства, которое легче сделать, чем классическое доказательство. Предположим, мы играем в шахматы. Теперь предположим, что я хочу доказать вам, что у меня есть выигрышная стратегия. Какие бы ходы ты ни делал, я все равно выиграю. Как мне вам это доказать?

Классически это огромное доказательство, потому что мне нужно доказать, что моя стратегия работает против всех возможных комбинаций ходов. Но, оказывается, через взаимодействие я могу сделать это очень лаконично. Если вы не верите, что у меня есть выигрышная стратегия, давайте просто поиграем. Я покажу тебе, что я выиграю. Конечно, это само по себе неубедительно — только потому, что я могу победить тебя один раз, не означает, что я могу победить кого угодно. Так дайте мне гроссмейстера. Я выиграю у гроссмейстера. Это начинает демонстрировать силу взаимодействия.

Но недостатком интерактивного доказательства является то, что оно не подлежит передаче. Допустим, вы даете мне стодолларовую купюру и доказываете посредством взаимодействия, что она действительно стоит 100 долларов. Я хочу иметь возможность передать это дальше. Я хочу отдать его кому-то другому, а тот отдает его кому-то еще. Но если бы у меня было только интерактивное доказательство, это ничего не значит; Я не могу отдать это кому-то другому. Так что в SNARG хорошо то, что вы можете передать их кому-то другому.

Как сертификат подлинности?

Точно. Блокчейны — это основное место, где они используются сегодня, для проверки транзакций. Когда появился блокчейн, я сказал своим студентам, что мы должны отправить разработчику биткойнов, Сатоши Накамото, цветы и конфеты, потому что он действительно сделал нашу работу такой актуальной.

Так как же удалить взаимодействие для создания этих передаваемых сертификатов?

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

А оказывается, что да, можем. Сегодня это делается постоянно. Если у вас есть iPhone или Android, вы используете парадигму Fiat-Shamir, когда ваш телефон подключается к удаленным серверам, что может происходить часто в течение дня. И именно эту парадигму мы используем для создания кратких доказательств, подтверждающих правильность удаленных вычислений.

Вы говорили о том, что машины должны быть «постквантово безопасными». Что это значит?

Квантовые компьютеры, если они действительно появятся в больших масштабах, будут гораздо более мощными, чем классические компьютеры. Классические компьютеры работают с битами, которые равны либо 0, либо 1. В квантовых компьютерах у вас есть квантовые биты, которые находятся в суперпозиции между 0 и 1. И эти кубиты запутаны, что означает, что они влияют друг на друга. Это то, что действительно дает квантовым компьютерам их силу.

В будущем, возможно, не у всех будет квантовый рабочий стол. Там может быть несколько дорогих квантовых устройств, которые делают для вас удаленные вычисления. Предположим, вы хотите делегировать дорогостоящие вычисления одному из этих квантовых устройств, и вам нужен сертификат, подтверждающий правильность вывода — как вы подтверждаете правильность квантовых компьютеров? Теперь, когда мы хотим использовать квантовые биты, а не классические биты, все меняется, особенно когда я хочу, чтобы верификатор был классическим компьютером.

В 2018 году был прорыв результат студенткой Беркли Урмилой Махадев. Она была первой, кто представил классическое вычислительно безопасное доказательство для проверки квантовых вычислений.

Значит, вы можете использовать классический компьютер для проверки квантовых вычислений? Это звучит невозможно!

Разве это не удивительно? Я был в программном комитете, когда Урмила опубликовала свою статью, и всю ночь просматривал ее — сколько кофеина я выпил! Я был потрясен. В тот момент я был полным квантовым манекеном. Я понял криптографическую часть, но мне потребовалось некоторое время, чтобы понять, как она сочетается с квантовой частью. И это было красиво.

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

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