Компьютерщики достигают ‘Жемчужины короны " криптографии
В 2018 году ааюш Джайн, аспирант Калифорнийского университета в Лос-Анджелесе, отправился в Японию, чтобы рассказать о мощном криптографическом инструменте, который он и его коллеги разрабатывали. Когда он подробно описал подход команды к запутыванию неразличимости (сокращенно ио), один из слушателей поднял руку в недоумении.
Оригинальная история перепечатана с разрешения журнала Quanta Magazine, редакционно независимого издания Фонда Саймонса, миссия которого состоит в том, чтобы улучшить общественное понимание науки, освещая научные разработки и тенденции в области математики, физики и естественных наук.
“Но я думал, что Ио не существует?- сказал он.
В то время подобный скептицизм был широко распространен. Неразличимость обфускации, если бы она могла быть построена, была бы в состоянии скрыть не только коллекции данных, но и внутреннюю работу самой компьютерной программы, создавая своего рода криптографический Мастер-Инструмент, из которого можно было бы построить почти любой другой криптографический протокол. Это “один криптографический примитив, чтобы управлять ими всеми", сказал Боаз Барак из Гарвардского университета. Но для многих компьютерных ученых сама эта сила заставляла ио казаться слишком хорошей, чтобы быть правдой.
Компьютерные ученые выдвигают кандидатские версии ио, начиная с 2013 года. Но сильное возбуждение, вызванное этими конструкциями, постепенно угасло, поскольку другие исследователи выяснили, как нарушить их безопасность. По мере того как атаки накапливались, “вы могли видеть много негативных флюидов”, - сказал Юваль Ишай из Техниона в Хайфе, Израиль. Исследователи задавались вопросом: "Кто победит: создатели или разрушители?”
“Были люди, которые были фанатиками, и они верили в [Ио] и продолжали работать над этим”, - сказал Шафи Голдвассер, директор Института теории вычислений Саймонса при Калифорнийском университете в Беркли. Но шли годы, и она говорила: “таких людей становилось все меньше и меньше.”
Теперь Джайн-вместе с Хуэйцзя Линем из Вашингтонского университета и Амитом Сахаи, советником Джайна в Калифорнийском университете в Лос—Анджелесе-установил флаг для создателей. В статье, опубликованной в интернете 18 августа, три исследователя впервые показывают, как построить неразличимость запутывания, используя только "стандартные" предположения безопасности.
Все криптографические протоколы основаны на предположениях-некоторые из них, такие как знаменитый алгоритм RSA, зависят от широко распространенного убеждения, что стандартные компьютеры никогда не смогут быстро разложить произведение двух больших простых чисел. Криптографический протокол так же безопасен, как и его предположения, и предыдущие попытки ввода-вывода были построены на непроверенных и в конечном счете шатких основаниях. Новый протокол, напротив, зависит от предположений безопасности, которые широко использовались и изучались в прошлом.
“За исключением действительно удивительного развития событий, эти предположения останутся в силе", - сказал Ишай.
Получите провод всего за 5 долларов. Подпишитесь Прямо Сейчас
Хотя протокол далек от готовности к развертыванию в реальных приложениях, с теоретической точки зрения он обеспечивает мгновенный способ создания массива криптографических инструментов, которые ранее были недоступны. Например, он позволяет создать” отрицаемое " шифрование, в котором вы можете правдоподобно убедить злоумышленника, что вы отправили совершенно другое сообщение, чем то, которое вы действительно отправили, и “функциональное” шифрование, в котором вы можете предоставить выбранным пользователям различные уровни доступа для выполнения вычислений с использованием ваших данных.
Новый результат должен окончательно заставить замолчать скептиков ио, сказал Ишай. “Теперь уже не будет никаких сомнений в существовании неразличимости обфускации”, - сказал он. - Похоже, это счастливый конец.”
драгоценность короны
В течение десятилетий ученые-компьютерщики задавались вопросом, существует ли безопасный, всеобъемлющий способ запутать компьютерные программы, позволяя людям использовать их, не раскрывая их внутренних секретов. Запутывание программы позволит использовать множество полезных приложений: например, вы можете использовать запутанную программу для делегирования определенных задач в рамках вашего банковского счета или счета электронной почты другим лицам, не беспокоясь о том, что кто-то может использовать программу таким образом, для которого она не предназначена, или считывать пароли ваших учетных записей (если только программа не предназначена для их вывода).
Но до сих пор все попытки построить практические обфускаторы терпели неудачу. “Те, которые вышли в реальной жизни, смехотворно сломаны ... обычно в течение нескольких часов после выхода в дикую природу”, - сказал Сахаи. В лучшем случае, они предлагают нападающим лежачий полицейский, сказал он.
В 2001 году Плохие новости пришли и на теоретическом фронте: самая сильная форма запутывания невозможна. Называемая "черным ящиком", она требует, чтобы злоумышленники не могли узнать абсолютно ничего о программе, кроме того, что они могут наблюдать, используя программу и видя, что она выводит. Некоторые программы, как показали Барак , Сахаи и пять других исследователей, раскрывают свои секреты настолько решительно, что их невозможно полностью запутать.
Эти программы, однако, были специально разработаны, чтобы избежать путаницы и иметь мало общего с реальными программами. Поэтому ученые-компьютерщики надеялись, что существует какой-то другой вид запутывания, достаточно слабый, чтобы быть осуществимым, но достаточно сильный, чтобы скрыть те секреты, которые действительно волнуют людей. Те же исследователи, которые показали, что обфускация черного ящика невозможна, предложили в своей работе одну возможную альтернативу: неразличимость обфускации.
На первый взгляд, ио не кажется особенно полезной концепцией. Вместо того чтобы требовать, чтобы секреты программы были скрыты, он просто требует, чтобы программа была достаточно запутана, чтобы, если у вас есть две разные программы, выполняющие одну и ту же задачу, вы не могли отличить, какая запутанная версия пришла от какой исходной версии.
Но ио сильнее, чем кажется. Например, предположим, что у вас есть программа, которая выполняет какую-то задачу, связанную с вашим банковским счетом, но программа содержит ваш незашифрованный пароль, что делает вас уязвимым для любого, кто завладеет программой. Затем—до тех пор, пока существует какая—то программа, которая может выполнять ту же задачу, сохраняя ваш пароль скрытым-неразличимый обфускатор будет достаточно сильным, чтобы успешно замаскировать пароль. В конце концов, если это не так, то если вы поместите обе программы через обфускатор, вы сможете сказать, какая обфускированная версия пришла из вашей первоначальной программы.
На протяжении многих лет компьютерные ученые доказали, что вы можете использовать iO в качестве основы почти для каждого криптографического протокола, который вы можете себе представить (за исключением запутывания черного ящика). Это включает в себя как классические криптографические задачи, такие как шифрование с открытым ключом (которое используется в онлайн-транзакциях), так и ослепительные новички, такие как полностью гомоморфное шифрование, в котором облачный компьютер может вычислять зашифрованные данные, ничего о них не узнав. И она включает в себя криптографические протоколы, которые никто не знал, как построить, такие как отрицаемое или функциональное шифрование.
” Это действительно своего рода жемчужина короны " криптографических протоколов, - сказал Рафаэль пасс из Корнельского университета. "Как только вы достигнете этого, мы сможем получить практически все.”
В 2013 году Сахаи и пять соавторов предложили протокол ввода-вывода, который разбивает программу на что-то вроде кусочков головоломки, а затем использует криптографические объекты, называемые многолинейными картами, чтобы исказить отдельные кусочки. Если части собраны вместе правильно, искажение отменяется, и программа функционирует так, как задумано, но каждая отдельная часть выглядит бессмысленной. Этот результат был воспринят как прорыв и вызвал десятки последующих публикаций. Но уже через несколько лет другие исследователи показали, что в мультилинейных картах используются в процессе искажения были небезопасны. Появились и другие кандидаты на Ио, которые, в свою очередь, были сломлены.
“Было некоторое беспокойство, что, может быть, это просто мираж, может быть, ио просто невозможно достать, - сказал Барак. Люди начали чувствовать, сказал он, что “возможно, все это предприятие обречено.”
Скрывать меньше, чтобы скрыть больше
В 2016 году Лин начал исследовать, можно ли обойти слабые стороны многолинейных карт, просто требуя от них меньше. Многолинейные карты-это, по сути, просто секретные способы вычисления с помощью полиномов-математических выражений, состоящих из сумм и произведений чисел и переменных, таких как 3xy + 2yz2. Эти карты, сказал Джайн, предполагают что-то вроде полиномиальной вычислительной машины, подключенной к системе секретных шкафчиков, содержащих значения переменных. Пользователь, который опускает полином, который принимает машина, получает возможность заглянуть в один последний шкафчик, чтобы узнать, делают ли скрытые значения полиномиальную оценку равной 0.
Чтобы схема была безопасной, пользователь не должен быть в состоянии выяснить что-либо о содержимом других шкафчиков или номерах, которые были сгенерированы по пути. “Мы хотели бы, чтобы это было правдой, - сказал Сахаи. Но во всех возможных многолинейных картах, которые люди могли придумать, процесс открытия последнего шкафчика раскрывал информацию о вычислениях, которая должна была оставаться скрытой.
Поскольку все предложенные многолинейные картографические машины имели слабые места в безопасности, Лин задался вопросом, существует ли способ построить iO с использованием машин, которые не должны вычислять так много различных видов полиномов (и поэтому могут быть проще построить безопасно). Четыре года назад она все поняла. как построить ио, используя только многолинейные карты, которые вычисляют полиномы, чья "степень" равна 30 или меньше (это означает, что каждый член является произведением не более чем 30 переменных, считая повторы). В течение следующих нескольких лет она, Сахаи и другие исследователи постепенно выяснили, как снизить градус еще ниже, пока они не смогли показать, как построить ио, используя только многолинейные карты степени-3.
На бумаге это выглядело огромным улучшением. Была только одна проблема: с точки зрения безопасности, “степень 3 была фактически сломана”, как машины, которые могут обрабатывать полиномы любой степени, сказал Джайн.
Единственными многолинейными картами, которые исследователи знали, как надежно строить, были те, которые вычисляли полиномы степени 2 или меньше. Лин объединил усилия с Джайном и Сахаем, чтобы попытаться выяснить, как построить ио из многолинейных карт степени 2. Но "мы застряли очень, очень надолго", - сказал Лин.
” Это было довольно мрачное время", - вспоминал Сахаи. - Есть кладбище, полное идей, которые не сработали.”
Однако в конце концов-вместе с Прабханджаном Анантом из Калифорнийского университета в Санта-Барбаре и Кристианом Мэттом из блокчейн-проекта Concordium—они пришли к идее своего рода компромисса: поскольку iO, казалось бы, нуждалась в картах степени-3, но у компьютерных ученых были только безопасные конструкции для карт степени-2, что, если было что—то среднее-своего рода карта степени-2,5?
Исследователи представили себе систему, в которой некоторые из шкафчиков имеют прозрачные окна, так что пользователь может видеть значения, содержащиеся внутри. Это освобождает машину от необходимости защищать слишком много скрытой информации. Чтобы найти баланс между мощностью полилинейных отображений более высокой степени и безопасностью отображений степени 2, машине разрешено вычислять с полиномами степени выше 2, но есть ограничение: полином должен быть степенью 2 по скрытым переменным. ” Мы стараемся не скрывать так много", как в общих многолинейных картах, - сказал Лин. Исследователи смогли показать, что эти гибридные системы шкафчиков могут быть построены надежно.
Но чтобы перейти от этих менее мощных мультилинейных карт к Ио, команде нужен был последний ингредиент: новый вид генератора псевдослучайности, что-то, что расширяет строку случайных битов в более длинную строку, которая все еще выглядит достаточно случайной, чтобы обмануть компьютеры. Это то, что Джайн, Лин и Сахай придумали, как сделать в своей новой статье. “В прошлом месяце или около того был замечательный случай, когда все сошлось в шквале телефонных звонков”, - сказал Сахаи.
Результатом является протокол ввода-вывода, который, наконец, позволяет избежать слабых мест безопасности многолинейных карт. “Их работы выглядят просто великолепно, - сказал пасс.
Безопасность схемы основывается на четырех математических допущениях, которые широко используются в других криптографических контекстах. И даже предположение, которое было изучено меньше всего, называемое “учение о четности с шумом”, связано с проблемой, которая изучалась с 1950-х годов.
Вероятно , есть только одна вещь, которая может сломать новую схему: квантовый компьютер, если он когда-либо будет построен на полную мощность. Одно из четырех предположений уязвимо для квантовых атак, но за последние несколько месяцев в трех отдельных статьях появилось отдельное направление работы by Pass и другие исследователи предлагают другой потенциальный маршрут к Ио, который может быть защищен даже от квантовых атак. Эти версии ио опираются на менее устоявшиеся предположения о безопасности, чем те, которые использовали Джайн, Лин и Сахай, заявили несколько исследователей. Но вполне возможно, сказал Барак, что эти два подхода могут быть объединены в ближайшие годы для создания версии iO, которая опирается на стандартные предположения безопасности и также сопротивляется квантовым атакам.
Конструкция Джайна, Лина и Сахая, вероятно, привлечет новых исследователей в эту область, чтобы работать над тем, чтобы сделать схему более практичной и разработать новые подходы, предсказал Ишай. “Как только вы знаете, что что-то возможно в принципе, это делает его психологически намного легче работать в этой области”, - сказал он.
Компьютерным ученым еще предстоит проделать большую работу, прежде чем протокол (или некоторые его вариации) можно будет использовать в реальных приложениях. Но это нормально для курса, сказали исследователи. "В криптографии есть много понятий, которые, когда они впервые появились, люди говорили:” Это просто чистая теория, [она] не имеет никакого отношения к практике", - сказал пасс. "Затем, 10 или 20 лет спустя, Google внедряет эти вещи.”
Путь от теоретического прорыва к практическому протоколу может быть долгим, сказал Барак. “Но вы можете себе представить, - сказал он, - что, возможно, через 50 лет учебники криптографии в основном скажут: “Хорошо, вот очень простая конструкция iO, и из этого мы теперь выведем все остальные криптографические данные.’”
Комментарии
Отправить комментарий