Прорывы Яэль Тауман Калаи обеспечивают безопасность цифрового мира — от облачных вычислений до квантового будущего. Комментарий Сохранить статью Прочитать позже
Яэль Тауман Калай, криптограф из Центра исследований и разработок Microsoft в Новой Англии, фокусируется на способах защиты вычислений.
Введение
Яэль Тауман Калай — пионер в области теоретической информатики, завоевавшая внушительные награды и изменившая представление людей об интернете. Однако в детстве она не была образцовой ученицей.
«Я была хулиганкой», — сказала она. «Меня фактически — не совсем, но фактически — выгнали из школы».
Калай родилась и выросла в Тель-Авиве, Израиль, в семье учёных. Её отец, Яир Тауман, экономист и специалист по теории игр. Уроки в старших классах были для неё скучными — в одном табеле успеваемости, по её воспоминаниям, было зафиксировано около 150 пропусков, поскольку она предпочитала проводить время за катанием на водных лыжах и общением. Однако её аналитические способности всегда были на её стороне.
«Когда родители не отпускали меня гулять, единственным способом добиться согласия отца было сказать ему: „Ладно, загадай мне математическую загадку. Какую угодно сложную, но если я её решу, то пойду“». Обычно она так и делала.
Её дремлющая любовь к математике наконец пробудилась в колледже, когда она начала осознавать её красоту. В конце концов, она обнаружила, что может использовать эти математические знания на практике, работая с компьютерами и, в частности, для защиты информации. Сейчас её работа охватывает области математики и информатики, а её идеи легли в основу того, как мы защищаем и проверяем вычисления в цифровую эпоху. Последние два десятилетия она работала над обеспечением целостности наших смартфонов, облачных подключений и даже криптовалют. Сейчас она исследователь в Microsoft и адъюнкт-профессор в Массачусетском технологическом институте. Недавно она стала обладательницей престижной премии Ассоциации вычислительной техники (ACM Prize) в области вычислительной техники за «прорывы в проверяемом делегировании вычислений и фундаментальный вклад в криптографию». Её последняя работа также обращена в будущее, поскольку она рассматривает, как квантовые компьютеры могут повлиять на сферу безопасности.
Quanta поговорила с Калаем об утечке секретов, проверке облачных технологий и особенностях квантовых вычислений. Интервью было сокращено и отредактировано для ясности.
Нажимая кнопку просмотра этого видео, вы соглашаетесь с нашей политикой конфиденциальности.Видео : Калай обсуждает значение криптографии и ее важность в нашей повседневной жизни.
Как вы прошли путь от школьного хулигана до учёного?
Я всегда знала, что люблю математику, но в старших классах она меня совершенно не интересовала. Потом я пошла изучать математику в бакалавриат, и меня это просто поразило. Впервые в жизни я сидела и училась без передышки, с утра до вечера. Я была в эйфории. И, должна сказать, немного расстроилась, потому что подумала: «Не могу поверить, что мне это нравилось, когда я была намного моложе!»
Что именно увлекало вас в математике?
Она очень чёткая, элегантная и абстрактная. Некоторые концепции в математике противоречат здравому смыслу; я помню, как чувствовал, что её изучение меняет меня как личность. Учишься смирению, потому что снова и снова убеждаешься, что твоя интуиция ошибается.
Но когда я искал хороший исследовательский вопрос, всё казалось постепенным. Поэтому я начал двигаться в сторону компьютерных наук. И криптография оказалась именно тем, чего мне не хватало, ведь она решает реальные проблемы. Сегодня криптография используется повсеместно. Она гарантирует конфиденциальность и подлинность отправляемых нами сообщений. Когда я переписываюсь с кем-то, как я могу быть уверен, что полученное мной сообщение – это то, что было отправлено? Как я могу быть уверен, что человек, который утверждает, что отправил сообщение, действительно его отправил? Что значит знать это? Эти концепции очень философские, и то, как мы их математически моделируем, действительно прекрасно. Она поразила меня как чистотой математики, так и применимостью.
Калай сравнивает силу интерактивных доказательств с игрой в шахматы: вместо того, чтобы теоретически доказывать, что у вас есть выигрышная стратегия, вы можете просто последовательно выигрывать.
Над какими видами криптографических проблем вы работали?
Моя магистерская диссертация называлась «Как раскрыть секрет». Проблема вот в чём: мы умеем ставить цифровую подпись — например, «Это я написал это сообщение». Но что, если я хочу подписать что-то как профессор Массачусетского технологического института, но не хочу, чтобы кто-то узнал, что это я? В таком случае секрет всё же остаётся под вопросом, потому что вы знаете, что его подписал профессор Массачусетского технологического института, но не знаете, кто именно.
Мы решили эту проблему с помощью так называемых кольцевых подписей, которые были вдохновлены понятием в информатике, называемым доказательствами, неразличимыми свидетелями. Допустим, есть утверждение и два разных способа его доказательства. Мы говорим, что есть два «свидетельства» истинности утверждения — каждое из доказательств. Доказательство, неразличимое свидетелями, выглядит одинаково, независимо от того, какое из них вы используете: оно скрывает, с какого свидетеля вы начали.
Кольцевые подписи похожи. В группе потенциальных разоблачителей можно считать, что у каждого человека есть секретный ключ. Кольцевая подпись, по сути, доказывает, что сообщение было подписано кем-то, владеющим одним из секретных ключей, но не раскрывает, какой именно секретный ключ известен этому человеку. Она скрывает, чей секретный ключ был использован.
Будет ли учреждение когда-либо использовать эту систему?
В этом и заключается прелесть и одновременно ужас — я могу делать это без участия других. Я могу подписаться как участник группы без её разрешения. Неясно, фича это или баг, но ясно, что это научное открытие. Использовались кольцевые подписи — есть криптовалюта Monero, которая, как говорят, использует их для конфиденциальности транзакций. Но, честно говоря, я не знаю, кто пользуется нашей работой. Честно говоря, я слишком занят, чтобы за этим следить.
В юности Калай была посредственной ученицей, но позже осознала силу математики и информатики для решения важных задач.
Как ваша работа превратилась в анализ безопасности наших устройств?
В начале 2000-х я заканчивал докторскую диссертацию, работая с Шафи Голдвассером в Массачусетском технологическом институте. Люди только начали говорить об облачных вычислениях, которыми мы теперь пользуемся каждый день. Раньше у вас был огромный рабочий стол, где всё выполнялось. С ростом объёма сбора больших объёмов данных вычисления стали дороже, и их начали выполнять удалённо. Идея заключается в том, что есть мощное облако, которое выполняет вычисления за вас. Но вы можете не доверять облачной платформе, так как же вы можете быть уверены, что вычисления выполняются правильно? Иногда может возникнуть соблазн схитрить, поскольку вычисления могут быть очень затратными. Кроме того, в некоторых ситуациях вы можете беспокоиться о случайных ошибках. Поэтому вам действительно нужно доказательство того, что эти вычисления верны.
Но обычно доказательства очень длинные, и слабые устройства не могут их проверить. Даже для устройств, которые могут, это очень затратно. Так есть ли способ сократить доказательства? Теоретически, нет. Но оказывается, что, используя криптографические инструменты, мы можем генерировать краткие сертификаты, которые очень и очень сложно подделать. Они называются краткими неинтерактивными аргументами, или SNARG. На самом деле, это не доказательство. Но пока вы не можете решить какую-то задачу, которую мы, криптографы, считаем очень сложной, например, разложение больших чисел на множители, краткие доказательства подделать невозможно.
Как появились эти доказательства?
Всё началось в 1985 году с Шафи Голдвассера, Сильвио Микали и Чарльза Ракоффа, которые совместно предложили концепцию интерактивных доказательств. Раньше, когда люди думали о доказательствах, они представляли себе запись строк данных, которые можно было прочитать и проверить, верны они или нет. Голдвассер, Микали и Ракофф предложили совершенно иной способ доказательства: интерактивный. Есть доказывающий и есть проверяющий, и они обмениваются сообщениями. Затем проверяющий решает, убеждён ли он в своей правоте или нет.
Калай объясняет принципы криптографии докторантам (слева направо) Спенсеру Питерсу, Сурье Матиалагану и Лали Девадас.
Позвольте мне привести пример интерактивного доказательства, которое проще реализовать, чем классическое. Предположим, мы играем в шахматы. Теперь предположим, что я хочу доказать вам, что у меня есть выигрышная стратегия. Какие бы ходы вы ни сделали, я всё равно выиграю. Как мне это доказать?
С классической точки зрения, это весомое доказательство, ведь мне нужно доказать, что моя стратегия работает против всех возможных комбинаций ходов. Но, как оказалось, благодаря взаимодействию я могу сделать это очень лаконично. Если вы не верите, что у меня выигрышная стратегия, давайте просто сыграем. Я покажу вам, что выиграю. Конечно, одно это неубедительно — то, что я смог выиграть у вас один раз, не означает, что я смогу выиграть у кого угодно. Так что дайте мне гроссмейстера. Я выиграю у гроссмейстера. Это начинает демонстрировать силу взаимодействия.
Но недостаток интерактивного доказательства в том, что его невозможно передать. Допустим, вы даёте мне стодолларовую купюру и доказываете посредством взаимодействия, что она действительно стоит 100 долларов. Я хочу иметь возможность передать её другому. Я хочу передать её кому-то другому, кто, в свою очередь, передаст её ещё кому-то. Но если бы у меня было только интерактивное доказательство, это ничего не значило бы; я не смог бы передать его кому-то ещё. Поэтому преимущество SNARG в том, что их можно передать кому-то ещё.
Калай работал над обеспечением безопасности облачных вычислений и теперь изучает, как квантовые компьютеры влияют на эту безопасность.
Вам нужен сертификат подлинности?
Именно. Блокчейны — это основное место, где они используются сегодня для подтверждения транзакций. Когда появился блокчейн, я сказал своим студентам, что нам нужно отправить разработчику биткоина, Сатоши Накамото, цветы и шоколад, потому что он действительно сделал нашу работу такой актуальной.
Так как же устранить взаимодействие при создании этих передаваемых сертификатов?
С криптографией. Позвольте мне попытаться объяснить вам, как это работает. В наших интерактивных доказательствах проверяющий обычно просто отправляет доказывающему случайные числа — можно представить это так, будто проверяющий выборочно проверяет доказательство. Затем у Амоса Фиата и Ади Шамира возникла идея: зачем нужен этот проверяющий, если он только и делает, что отправляет случайные числа? Возможно, мы заменим его какой-нибудь функцией, например, хэш-функцией — это функция, которая выглядит случайной и является очень важным строительным блоком в криптографии.
И оказывается, да, можем. Сегодня это происходит постоянно. Если у вас iPhone или Android, вы используете парадигму Фиата-Шамира, когда ваш телефон подключается к удалённым серверам, что может происходить часто в течение дня. И именно эту парадигму мы используем для построения кратких доказательств, подтверждающих корректность удалённых вычислений.
Вы говорили о том, что машины должны быть «постквантово безопасными». Что это значит?
Квантовые компьютеры, если они действительно появятся в больших масштабах, будут гораздо мощнее классических. Классические компьютеры работают с битами, которые могут быть либо 0, либо 1. В квантовых компьютерах есть квантовые биты, находящиеся в суперпозиции между 0 и 1. И эти кубиты запутаны, то есть влияют друг на друга. Именно это и делает квантовые компьютеры такими мощными.
«Криптография — это именно то, чего мне не хватало, ведь она решает реальные проблемы», — сказал Калай. «Сегодня криптография используется повсеместно».
В будущем квантовый компьютер, возможно, будет доступен не у каждого. Возможно, появятся несколько дорогостоящих квантовых устройств, которые будут выполнять удалённые вычисления за вас. Предположим, вы хотите поручить выполнение дорогостоящего вычисления одному из этих квантовых устройств и вам нужен сертификат, подтверждающий корректность результата. Как можно подтвердить корректность квантовых компьютеров? Теперь, когда мы хотим использовать квантовые биты, а не классические, всё меняется, особенно когда я хочу, чтобы верификатором был классический компьютер.
В 2018 году студентка Беркли Урмила Махадев добилась новаторского результата. Она первой представила классическое, вычислительно безопасное доказательство для проверки квантовых вычислений.
То есть можно использовать классический компьютер для проверки квантовых вычислений? Звучит невероятно!
Разве это не потрясающе? Я был в программном комитете, когда Урмила опубликовала свою статью, и провёл всю ночь, разглядывая её — сколько же кофеина я выпил! Я был просто ошеломлён. В тот момент я был полным кретином в квантовой механике. Я понимал криптографическую часть, но мне потребовалось время, чтобы понять, как это согласуется с квантовой. И это было прекрасно.
Переход от классических к квантовым вычислениям кажется сложным и трудоемким процессом обучения.
Знаю. Я на самом деле ничего не знаю о физике, и тут задействована большая часть квантово-физической интуиции. Я не понимаю даже самых базовых понятий, таких как энергия и температура. Иногда я работаю со студентами, и как только мы говорим о квантовых вычислениях, я становлюсь студентом. У меня начинает появляться немного больше интуиции. И, должен сказать, мне это очень нравится — сидеть с учебником по квантовой информации. Нет ничего лучше, чем быть студентом.
Источник: www.quantamagazine.org
