Анонимность в цифровую эпоху: как защитить личные данные от квантовых атак

Интернет переживает один из самых сложных переходов в своей истории: миграцию на постквантовую (PQ) криптографию. Обеспечение безопасности системы от квантовых атак — это не просто замена эллиптических кривых и RSA на PQ-аналоги, такие как ML-KEM и ML-DSA. Эти алгоритмы имеют более высокую стоимость по сравнению с их классическими аналогами, что делает их непригодными в качестве прямой замены во многих ситуациях.

Тем не менее, мы уверенно продвигаемся в работе над самыми важными системами. На момент написания около 50% TLS-соединений с периферией Cloudflare защищены от атак "собрать сейчас, расшифровать позже". Квантово-безопасная аутентификация находится на более отдаленном этапе, поскольку потребует более значительных изменений в работе сертификатов. Тем не менее, в этом году мы сделали крупный шаг к возможности масштабного развертывания TLS с PQ-сертификатами.

Несмотря на это, TLS — это лишь самый очевидный и легкий для решения элемент. Существует гораздо больше способов, с помощью которых мы стали полагаться на криптографию, помимо обмена ключами и аутентификации, и которые не так просто мигрировать. В этой записи блога мы рассмотрим Анонимные Удостоверения (Anonymous Credentials, ACs).

АУ решают распространенную дилему конфиденциальности: как доказать конкретный факт (например, что у человека есть действующие водительские права более трех лет), не раскрывая излишнюю личную информацию (такую как место рождения)? Такие проблемы являются фундаментальными для ряда случаев использования, и АУ могут обеспечить основу, необходимую для максимальной конфиденциальности этих приложений.

Как и в случае с TLS, ключевой вопрос для АУ заключается в том, существуют ли прямые PQ-замены для их классических примитивов, которые будут работать в требуемом масштабе, или же потребуется перепроектировать приложение, чтобы нивелировать стоимость PQ.

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

Сначала мы исследуем текущую ситуацию с внедрением классических АУ в технологической индустрии и государственном секторе. Затем мы обсудим, что в настоящее время исследуют криптографы в постквантовой области. Наконец, мы посмотрим, что потребуется для преодоления разрыва между теорией и реальными приложениями.

Хотя анонимные удостоверения начали реально внедряться лишь в последние годы, критически важно уже сейчас параллельно задуматься о постквантовой проблеме. Это не теоретическая, преждевременная проблема, учитывая угрозу "собрать сейчас, расшифровать позже". Если мы дождемся массового внедрения, прежде чем решить проблему постквантовых анонимных удостоверений, АУ рискуют оказаться мертворожденными. К счастью, наш обзор состояния дел в этой области показывает, что она близка к практическому решению. Давайте начнем с рассмотрения реальных случаев использования АУ.

В 2026 году Европейский Союз планирует запустить свой цифровой кошелек удостоверений личности — систему, которая позволит гражданам, резидентам и предприятиям ЕС в цифровой форме подтверждать свои личные атрибуты. Это позволит им, например, показывать свои водительские права на телефоне или проходить проверку возраста. Варианты использования АУ в Cloudflare несколько иные и вращаются вокруг защиты наших клиентов, например, путем ограничения частоты запросов от ботов и людей, как мы уже делаем с Privacy Pass. Кошелек ЕС — это масштабный проект в области предоставления удостоверений личности, а наша работа ведется в огромных масштабах обработки трафика. Обе инициативы работают над решением общей фундаментальной проблемы: позволить субъекту доказать конкретный атрибут о себе, не ставя под угрозу свою конфиденциальность, раскрывая больше, чем необходимо.

Цель ЕС — полностью мобильное, безопасное и удобное для пользователя цифровое удостоверение личности. Текущий технический план амбициозен, как изложено в Архитектурном справочном фреймворке (Architecture Reference Framework, ARF). В нем определяются ключевые цели конфиденциальности — не связуемость (unlinkability), гарантирующая, что если пользователь предъявляет атрибуты несколько раз, получатели не могут связать эти отдельные предъявления, чтобы сделать вывод, что они относятся к одному и тому же пользователю. Однако предлагаемые в настоящее время решения не позволяют достичь этого. Фреймворк правильно определяет основную проблему: аттестации содержат уникальные, фиксированные элементы, такие как хеш-значения, […], открытые ключи и подписи, которые взаимодействующие стороны могут хранить и сравнивать для отслеживания individuals.

В своей нынешней форме рекомендация ARF для смягчения межсессионной связуемости — это аттестации с ограниченным сроком действия. Фреймворк признает в тексте, что это лишь частично смягчит связуемость со стороны Проверяющей стороны (Relying Party). Альтернативное предложение, которое могло бы снизить риски связуемости, — это одноразовые удостоверения. В настоящее время они не рассматриваются из-за сложности и накладных расходов на управление. Поэтому фреймворк полагается на организационные и правоприменительные меры для сдерживания сговора, а не на предоставление более сильной гарантии, обеспеченной криптографией.

Эта зависимость от предположений о доверии может стать проблематичной, особенно в таком чувствительном контексте, как цифровая идентичность. Когда их попросили дать обратную связь, криптографы-исследователи согласились, что правильным решением было бы внедрение анонимных удостоверений. Однако это решение представляет собой долгосрочную проблему. Хорошо изученные методы для анонимных удостоверений, такие как основанные на подписях BBS, уязвимы для квантовых компьютеров. Хотя некоторые анонимные схемы являются PQ-несвязуемыми (PQ-unlinkable), что означает сохранение конфиденциальности пользователя даже при существовании криптографически значимых квантовых компьютеров, новые удостоверения могут быть подделаны. Это может быть привлекательной целью для, скажем, государственного актора.

Новая криптография также сталкивается с проблемами развертывания: в ЕС можно использовать только одобренные криптографические примитивы, перечисленные в каталоге SOG-IS. На момент написания этот каталог ограничен устоявшимися алгоритмами, такими как RSA или ECDSA. Но когда дело доходит до постквантовой криптографии, SOG-IS оставляет проблему широко открытой.

Первое развертывание кошелька не будет квантово-безопасным. Однако, учитывая, что переход на постквантовые алгоритмы еще впереди (уже к 2030 году для случаев использования с высоким риском согласно дорожной карте ЕС), исследования совместимой с постквантовой эрой альтернативы для анонимных удостоверений имеют критическое значение. Это будет включать стандартизацию большего количества криптографии.

Что касается существующих крупномасштабных развертываний, США разрешили использование цифрового удостоверения личности на смартфонах с 2024 года. Их, например, можно использовать на контрольно-пропускных пунктах TSA. Министерство внутренней безопасности США разместило на своем сайте информацию о финансировании шести кошельков и верификаторов цифровых удостоверений с сохранением конфиденциальности. Это раннее исследование и вовлеченность — положительный знак, который подчеркивает необходимость планирования презентаций с сохранением конфиденциальности.

Наконец, текущие усилия Рабочей группы инженерного совета Интернета (IETF)направленына создание более приватного Интернета путем стандартизации передовых криптографических методов. Активные индивидуальные проекты (т.е. еще не принятые рабочей группой), такие как Longfellow и Анонимные Кредитные Токены (ACT), и принятые проекты, такие как Анонимные Кредиты с Ограничением Частоты (ARC), предлагают более гибкие многоразовые анонимные учетные данные, включающие разработки последних лет. На IETF 117 в 2023 году постквантовые анонимные учетные данные и развертываемые универсальные анонимные учетные данные были представлены как исследовательская возможность. Подробности смотрите в нашем посте об агентах ограничения частоты.

Прежде чем мы перейдем к современному состоянию PQ, позвольте нам попытаться сформулировать набор требований для реальных приложений.

Учитывая разнообразие случаев использования, внедрение AC будет облегчено тем, что их можно построить из небольшого количества мощных примитивов. (Подробнее об этом в нашем параллельном посте.) Как мы увидим в следующем разделе, у нас пока нет готовых PQ-альтернатив для таких примитивов. «Строительные блоки» PQ AC, вероятно, будут выглядеть совсем иначе, и нам нужно понимать, к чему мы стремимся.

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

Ключевое различие между AC и слепыми подписями заключается в том, что во время предъявления AC клиент представляет в открытом виде только часть сообщения; остальная часть сообщения сохраняется в секрете. Обычно сообщение состоит из трех компонентов:

1. Приватное состояние, например, счетчик, который отслеживает количество предъявлений учетных данных. Клиент доказывал бы серверу, что состояние «действительно», например, что счетчик имеет значение $0 leq C leq N$, не раскрывая $C$. Во многих ситуациях желательно позволить серверу обновлять это состояние после успешного предъявления, например, уменьшая счетчик. В контексте ограничения частоты запросов это число оставшихся запросов для учетных данных.

2. Случайное значение, называемое нуллификатором, которое раскрывается серверу во время предъявления. При ограничении частоты нуллификатор предотвращает возможность пользователя использовать учетные данные с заданным состоянием более одного раза.

3. Публичные атрибуты, известные как клиенту, так и серверу, которые привязывают AC к некоторому контексту приложения. Например, это может представлять окно времени, в течение которого учетные данные действительны (не раскрывая точного времени их выпуска).

Такие AC хорошо подходят для ограничения частоты запросов, выполняемых клиентом. Идея заключается в том, чтобы предотвратить выполнение клиентом более определенного максимального количества запросов в течение времени жизни учетных данных. Например, если лимит предъявлений составляет 1000, а окно действительности — один час, то клиенты могут выполнять в среднем до 0,27 запроса в секунду до того, как их ограничат.

Обычно желательно применять ограничения частоты на основе происхождения (per-origin). Это означает, что если лимит предъявлений составляет 1000, то клиент может сделать не более 1000 запросов к любому веб-сайту, который может проверить учетные данные. Более того, он может делать это безопасно, т.е. не нарушая несливаемость между этими сайтами.

Текущее поколение AC, рассматриваемых для стандартизации в IETF, являются только приватно проверяемыми, что означает, что сервер, выпускающий учетные данные (эмитент), должен делиться закрытым ключом с сервером, проверяющим учетные данные (происхождение). Этого будет достаточно для некоторых сценариев развертывания, но многим потребуется публичная проверяемость, когда происхождению нужен только открытый ключ эмитента. Это возможно, например, с учетными данными на основе BBS.

Наконец, скажем несколько слов о сложности раундов. AC является оптимальным по раундам, если выпуск и предъявление завершаются за один HTTP-запрос и ответ. В нашем обзоре PQ AC мы обнаружили ряд статей, в которых найдены изящные приемы, снижающие пропускную способность (общее количество битов, передаваемых между клиентом и сервером) ценой дополнительных раундов. Однако для случаев использования, подобных нашему, оптимальность по раундам абсолютно необходима, особенно для предъявления. Множественные раунды не только сильно влияют на задержки, но и значительно усложняют реализацию.

В рамках этих ограничений наша цель — разработать PQ AC с максимально низкой стоимостью связи (т.е. потреблением пропускной способности) и временем выполнения в контексте ограничения частоты.

Академическое сообщество создало ряд перспективных постквантовых AC. В нашем обзоре современного состояния мы оценили несколько ведущих схем, оценив их по базовым примитивам и производительности, чтобы определить, какие из них действительно готовы для Интернета. Чтобы понять проблемы, необходимо сначала усвоить криптографические строительные блоки, используемые в AC сегодня. Теперь мы обсудим некоторые основные концепции, которые часто встречаются в этой области.

Доказательства с нулевым разглашением (ZKP) — это криптографический протокол, который позволяет доказывающему убедить проверяющего в истинности утверждения, не раскрывая секретную информацию, или свидетельство. ZKP играют центральную роль в AC: они позволяют доказывать утверждения о секретной части состояния учетных данных, не раскрывая само состояние. Это достигается путем преобразования утверждения в математическое представление, такое как набор полиномиальных уравнений над конечным полем. Доказывающий затем генерирует доказательство, выполняя сложные операции над этим представлением, которые могут быть корректно завершены только при наличии действительного свидетельства.

Универсальные системы ZKP, такие как Масштабируемые Прозрачные Аргументы Знания (STARK), могут доказывать целостность любого вычисления до определенного размера. В системе на основе STARK вычислительный след представляется в виде набора полиномов. Доказывающий затем строит доказательство, вычисляя эти полиномы и фиксируя их с помощью криптографических хэш-функций. Проверяющий может затем выполнить быструю вероятностную проверку этого доказательства, чтобы подтвердить, что исходное вычисление было выполнено правильно. Поскольку само доказательство — это просто набор хэшей и выборочных значений полиномов, оно защищено от квантовых компьютеров, обеспечивая статистически достоверную гарантию того, что заявленный результат действителен.

«Разделяй и властвуй» (Cut-and-choose) — это криптографический метод, предназначенный для обеспечения честного поведения доказывающего путем проверки проверяющим случайного подмножества его работы. Доказывающий сначала фиксирует несколько экземпляров вычисления, после чего проверяющий случайным образом выбирает часть для вскрытия путем раскрытия лежащих в основе секретов для проверки. Если этот раскрытый поднабор корректен, проверяющий получает высокую статистическую уверенность в том, что оставшиеся невскрытые экземпляры также корректны.

Эта техника важна, потому что, будучи универсальным инструментом для построения протоколов, защищенных от злоумышленников, она также служит crucial case study. Ее безопасность нетривиальна; например, практические атаки на схемы «разделяй и властвуй», построенные с помощью (постквантового) гомоморфного шифрования, успешно осуществлялись путем атаки на алгебраическую структуру кодирования, а не на само шифрование. Это подчеркивает, что даже универсальные конструкции должны быть тщательно проанализированы в их конкретной реализации, чтобы предотвратить тонкие уязвимости и утечки информации.

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

^{Изображение потока Сигма-протокола, где доказывающая сторона фиксирует своё свидетельство $w$, проверяющая сторона требует от доказывающей стороны доказать знание о $w$, и доказывающая сторона отвечает математическим утверждением, которое проверяющая сторона может принять или отклонить.}

На практике доказывающая и проверяющая стороны не выполняют этот интерактивный протокол. Вместо этого они делают его неинтерактивным, используя технику, известную как преобразование Фиата-Шамира. Идея заключается в том, что доказывающая сторона генерирует вызов самостоятельно, выводя его из собственного коммитмента. Это может показаться немного странным, но работает вполне хорошо. Фактически, это основа таких подписей, как ECDSA, и даже постквантовых подписей, таких как ML-DSA.

Многосторонние вычисления (MPC) — это криптографический инструмент, позволяющий нескольким сторонам совместно вычислять функцию над своими входными данными, не раскрывая свои индивидуальные данные другим сторонам. MPC в голове (MPCitH) — это техника генерации доказательств с нулевым разглашением путем моделирования многостороннего протокола в голове доказывающей стороны.

Доказывающая сторона моделирует состояние и коммуникацию для каждой виртуальной стороны, фиксирует эти моделирования и показывает коммитменты проверяющей стороне. Затем проверяющая сторона требует от доказывающей стороны открыть подмножество этих виртуальных сторон. Поскольку протоколы MPC безопасны даже если меньшинство сторон нечестны, раскрытие этого подмножества не разглашает секрет, но при этом убеждает проверяющую сторону в корректности общего вычисления.

Эта парадигма особенно полезна для нас, поскольку представляет собой гибкий способ построения постквантово безопасных ZKP. Конструкции MPCitH строят свою безопасность на симметрично-ключевых примитивах (таких как хеш-функции). Этот подход также является прозрачным, не требующим доверенной настройки. Хотя STARK разделяют эти постквантовые и прозрачные свойства, MPCitH часто предлагает более быстрое время работы доказывающей стороны для многих вычислений. Однако его основной компромисс заключается в том, что размер доказательств масштабируется линейно с размером доказываемой схемы, в то время как STARK являются краткими, то есть их размер доказательств растет гораздо медленнее.

Когда источник случайности смещен или выдает числа вне желаемого диапазона, выборочное отклонение может скорректировать распределение. Например, представьте, что вам нужно случайное число от 1 до 10, но ваш компьютер выдает только случайные числа от 0 до 255. (Действительно, так и есть!) Алгоритм выборочного отклонения вызывает ГСЧ до тех пор, пока он не выдаст число меньше 11 и больше 0:

Многократный вызов генератора может показаться немного расточительным. Эффективная реализация может быть достигнута с помощью расширяемой выходной функции (XOF). XOF принимает входные данные, например, сид, и вычисляет выход произвольной длины. Примером является семейство SHAKE (часть стандарта SHA3) и недавно предложенная версия SHAKE с уменьшенным числом раундов под названием TurboSHAKE.

Представьте, что вам нужно три числа от 1 до 10. Вместо многократного вызова XOF, вы можете запросить у XOF несколько байт вывода. Поскольку каждый байт имеет вероятность 3,52% попасть в диапазон, запрос 174 байт у XOF достаточен для того, чтобы с вероятностью более 99% найти как минимум три пригодных числа. На самом деле, мы можем быть еще умнее: 10 помещается в четыре бита, поэтому мы можем разделить выходные байты на младшие и старшие полубайты. Вероятность того, что полубайт окажется в желаемом диапазоне, теперь составляет 56,4%:

^{Выборочное отклонение путем пакетной обработки запросов.}

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

Классические анонимные учетные данные (AC), такие как ARC и ACT, построены на алгебраических группах — specifically, эллиптических кривых, которые очень эффективны. Их безопасность основана на предположении, что определенные математические задачи над этими группами вычислительно сложны. Однако предпосылка постквантовой криптографии заключается в том, что квантовые компьютеры могут решить эти предположительно сложные задачи. Наиболее интуитивное решение — заменить эллиптические кривые на постквантовую альтернативу. Фактически, криптографы работали над заменой в течение ряда лет: CSIDH.

Это поднимает ключевой вопрос: можем ли мы просто адаптировать схему, такую как ARC, заменив ее эллиптические кривые на CSIDH? Короткий ответ — нет, из-за критического препятствия в построении необходимых доказательств с нулевым разглашением. Хотя мы можем, теоретически, построить требуемые Сигма-протоколы или доказательства MPC-в-голове (MPCitH) на основе CSIDH, у них есть предварительное условие, которое делает их непригодными на практике: они требуют доверенной настройки для обеспечения невозможности обмана со стороны доказывающей стороны. Это требование является неприемлемым, поскольку не существует алгоритма выполнения доверенной настройки в CSIDH. Доверенная настройка для сигма-протоколов может быть заменена комбинацией общих техник из многосторонних вычислений и протоколов "разрезания и выбора", но это добавляет значительные вычислительные затраты к уже вычислительно дорогим операциям изогении.

Эта конкретная трудность подчеркивает более общий принцип. Высокая эффективность классических учетных данных, таких как ARC, тесно связана с богатой алгебраической структурой эллиптических кривых. Замена этого компонента на постквантовую альтернативу или переход к общим конструкциям фундаментально изменяет дизайн и его компромиссы. Поэтому мы должны принять, что постквантовые анонимные учетные данные не могут быть простым "поднятием и переносом" современных схем. Они потребуют новых конструкций, построенных из различных криптографических примитивов, таких как решетки или хеш-функции.

В Cloudflare мы исследовали постквантовую конструкцию Privacy Pass в 2023 году, которая очень напоминает функциональность, необходимую для анонимных учетных данных. Основной результат — это общая конструкция, которая комбинирует отдельные, квантово-безопасные строительные блоки: схему цифровой подписи и систему доказательств с нулевым разглашением общего назначения:

На рисунке показан криптографический протокол, разделенный на две основные фазы: (1.) Выпуск: Пользователь фиксирует сообщение (не раскрывая его) и отправляет коммитмент серверу. Сервер подписывает коммитмент и возвращает этот подписанный коммитмент, который служит токеном. Пользователь проверяет подпись сервера. (2.) Использование: Чтобы использовать токен, пользователь предъявляет его и строит доказательство. Это доказательство демонстрирует, что у него есть действительная подпись на коммитмент, и раскрывает коммитмент, чтобы показать исходное сообщение. Если сервер проверяет доказательство, пользователь и сервер продолжают (например, для доступа к ограниченному по частоте источнику).

Основная привлекательность этого модульного дизайна — его гибкость. Экспериментальная реализация использует модифицированную версию подписей ML-DSA и STARK, но компоненты можно легко заменить. Дизайн обеспечивает сильные, композиционные гарантии безопасности, полученные непосредственно из базовых частей. Значительное ускорение для конструкции было достигнуто за счет замены хеш-функции SHA3 в ML-DSA на дружественную к нулевому разглашению Poseidon.

Однако модульность нашей постквантовой конструкции Privacy Pass влечет значительные накладные расходы на производительность, что демонстрирует явный компромисс между временем генерации доказательства и его размером: быстрая генерация доказательства за 300 мс требует большой подписи размером 173 КБ, в то время как время генерации в 4,8 с сокращает размер подписи почти вдвое. Сбалансированный набор параметров, который служит хорошим ориентиром для любой специализированной системы, занял 660 мс для подписания и привел к подписи размером 112 КБ. Данная реализация в настоящее время является доказательством концепции, и, возможно, есть некоторый простор для оптимизации. В качестве альтернативы, другая подпись, такая как FN-DSA, может предложить улучшение скорости: хотя её выпуск сложнее, её верификация гораздо проще, сводясь к простому вычислению хеша в решётку и проверке нормы.

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

Решётки — это естественная отправная точка при обсуждении потенциальных кандидатов в постквантовые анонимные учетные данные (AC). NIST стандартизировал ML-DSA и ML-KEM в качестве алгоритмов подписи и KEM соответственно, и оба основаны на решётках. Так являются ли решётки ответом на проблему постквантовых анонимных учетных данных?

Ответ неоднозначен. Хотя явные схемы анонимных учетных данных на основе решёток существуют, у них есть недостатки, препятствующие развертыванию в реальном мире: например, недавняя схема жертвует оптимальностью по раундам ради меньшего размера коммуникации, что неприемлемо для такой службы, как Privacy Pass, где важна каждая секунда. Учитывая, что наша RTT составляет 100 мс или менее для большинства пользователей, каждый дополнительный коммуникационный раунд добавляет ощутимую задержку, особенно для тех, у кого медленное интернет-соединение. Когда итоговый размер учетных данных все еще превышает 100 КБ, компромиссы трудно оправдать. Таким образом, наш поиск продолжается. Мы расширяем горизонты, рассматривая слепые подписи и возможность их адаптации для анонимных учетных данных.

Значимой парадигмой в решёточных подписях является конструкция хеш-и-подпись. Здесь сообщение сначала хешируется в точку решётки. Затем подписывающий использует свой секретный ключ, решёточный люк, для генерации вектора, который при умножении на приватный ключ дает хешированную точку в решётке. Это основной механизм, лежащий в основе таких схем подписи, как FN-DSA.

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

Стандартная защита от этой атаки — требовать от пользователя доказательства с нулевым разглашением (ZK), что точка, которую он просит подписать, является слепым выходом указанной хеш-функции. Однако доказательство прообразов хеша приводит к той же проблеме, что и в общей статье о постквантовом Privacy Pass: доказательство обычной хеш-функции (такой как SHA3) внутри ZKP вычислительно дорого и имеет высокую коммуникационную сложность.

Этот сложный компромисс лежит в основе последних академических работ. Передовая статья представляет две схемы слепых подписей на основе решёток с малым размером подписи: 22 КБ для подписи и 48 КБ для протокола с приватной верификацией, который может быть более полезен в таком сценарии, как анонимные учетные данные. Однако этот фокус на итоговом размере подписи достигается ценой непрактичного выпуска. Пользователь должен предоставить ZKP для корректного хеша и решёточных отношений, которые, по собственному анализу статьи, могут добавлять несколько сотен килобайт и занимать 20 секунд на генерацию и 10 секунд на верификацию.

Хотя эти результаты ценны для развития области, такой компромисс является серьезным препятствием для любой крупномасштабной практической системы. Для нашего случая использования протокол, который умеренно увеличивает итоговый размер подписи в обмен на более эффективный и легковесный процесс выпуска, был бы более подходящим и перспективным направлением.

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

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

Схема полностью реализована, и учетные данные с доказательствами атрибутов составляют чуть менее 80 КБ, а подписи — менее 7 КБ. Схема занимает менее 400 мс для выпуска и 500 мс для показа учетных данных. Протокол также имеет множество функций, необходимых для анонимных учетных данных, позволяя пользователям доказывать отношения между атрибутами и запрашивать псевдонимы для разных экземпляров.

Это исследование представляет собой убедительный шаг к возможности развертывания в реальном мире, комбинируя передовые техники для достижения гораздо более здорового баланса между производительностью и безопасностью. Хотя лежащая в основе математика несколько сложнее, схема полностью реализована, и с доказательством знания подписи размером 40 КБ и временем доказывающего менее секунды, схема выделяется как сильный претендент. Однако для практического развертывания эти показатели, вероятно, потребуют значительного ускорения, чтобы быть пригодными для систем реального времени. Улучшение кажется возможным, учитывая недавние достижения в решёточных сэмплерах. Хотя точный масштаб, которого мы можем достичь, неясен. Тем не менее, мы считаем, что стоит немного приблизить базовую парадигму проектирования к нашим случаям использования.

В то время как решёточная схема хеш-и-подпись с отказами предоставляет один путь к постквантовым подписям, альтернативный подход возникает из варианта MPCitH под названием VOLE-in-the-Head (VOLEitH).

Эта схема основана на Векторном oblivious линейном вычислении (VOLE) — интерактивном протоколе, где входной вектор одной стороны обрабатывается с секретным значением дельта другой стороны, создавая корреляцию. Эта VOLE-корреляция используется как криптографический коммитмент на вход доказывающего. Система предоставляет доказательство с нулевым разглашением, потому что доказывающий связан этой корреляцией и не может подделать решение, не зная секретной дельты. Верификатор, в свою очередь, просто должен проверить, что итоговое уравнение выполняется, когда коммитмент раскрывается. Эта система является линейно гомоморфной, что означает, что два коммитмента можно комбинировать. Это свойство идеально для парадигмы commit-and-prove, где доказывающий сначала совершает коммитмент к свидетелям, а затем доказывает валидность схемы вентиль за вентилем. Основной компромисс заключается в том, что доказательства линейны по размеру схемы, но они предлагают существенно лучшее время выполнения. Мы также используем доказательства линейного размера для ARC и ACT.

^{Пример оценки схемы вентиль за вентилем, сначала совершая коммитмент к каждому проводу, а затем доказывая композицию. Это легко для линейных вентилей.}

Этот подход commit-and-prove позволяет VOLEitH эффективно доказывать вычисление симметричных шифров, которые являются квантово-устойчивыми. Преобразование в неинтерактивный протокол следует стандартному методу MPCitH: доказывающий совершает коммитмент ко всем секретным значениям, для выбора подмножества, которое нужно раскрыть, используется вызов (challenge), и доказывающий доказывает согласованность.

Эффективные реализации работают одновременно в двух математических полях (бинарном и простом), что позволяет этим ZK-схемам эффективно обрабатывать как арифметические, так и побитовые функции (такие как XOR). На основе этого фундамента недавнее выступление намекнуло на потенциал слепых подписей из схемы многомерных квадратичных подписей MAYO с размерами всего 7,5 КБ и временем подписания/верификации менее 50 мс.

Подход VOLEitH, как система общего назначения, представляет собой перспективное новое направление для производительных конструкций. В конкурсе NIST на дополнительные схемы подписей существует ряд конкурирующих схем "in-the-head", включая основанную на VOLEitH. Современная литература по VOLEitH фокусируется на высокопроизводительных цифровых подписях, и явная конструкция для полной системы анонимных учетных данных еще не предложена. Это означает, что стандартные для AC функции, такие как неотслеживаемость при многократном показе или возможность доказывать отношения между атрибутами, пока не являются частью дизайна, тогда как в решеточной конструкции они явно поддерживаются. Однако предварительные результаты показывают огромный потенциал для производительности, и будет интересно увидеть продолжение криптоанализа и разработки функций в этой линии VOLEitH в области анонимных учетных данных, особенно учитывая, что конструкция общего назначения позволяет легко добавлять функции.

Моя (то есть Лены) стажировка была сосредоточена на ключевом вопросе: на что нам следует обратить внимание дальше, чтобы создавать AC для Интернета? Для нас "правильное направление" означает разработку протоколов, которые можно интегрировать с реальными приложениями и разрабатывать совместно в IETF. Чтобы сделать это реальностью, нам нужно, чтобы исследователи смотрели дальше слепых подписей; нам нужен полный протокол, сохраняющий конфиденциальность, который сочетает слепые подписи с эффективными доказательствами с нулевым разглашением и свойствами вроде учетных данных с многократным показом, имеющих внутреннее состояние. Выпуск также должен быть сублинейным по размеру коммуникации относительно количества предъявлений.

Итак, с учетом предстоящего перехода на постквантовую криптографию, каковы наши мысли о текущих предложениях IETF? Презентация NIST 2022 года о текущем состоянии анонимных учетных данных утверждает, что эффективные постквантово-безопасные решения практически отсутствуют. Мы утверждаем, что последние три года показали хорошие разработки в области решеточных и MPCitH анонимных учетных данных, но эффективные постквантовые протоколы все еще требуют доработки. Переход протоколов в постквантовый мир — это не просто замена старых алгоритмов на новые. Распространенный подход к построению постквантовых версий классических протоколов — замена строительных блоков на их квантово-безопасные аналоги. 

Мы считаем, что этот подход необходим, но не дальновиден. Помимо выявления того, как современные проблемы могут быть учтены в старых криптографических конструкциях, мы должны создавать новые, изначально постквантовые протоколы.

• Для ARC концептуальный путь к постквантовой конструкции кажется относительно прямым. Базовая криптография следует структуре, аналогичной решеточным анонимным учетным данным, или, при принятии протокола с меньшим количеством функций, универсальной постквантовой конструкции Privacy Pass. Однако нам необходимо поддерживать ограничение частоты запросов на источник (per-origin rate-limiting), что позволяет нам преобразовывать токен в источнике без утечки возможности связать его погашение с погашениями в других источниках — функция, которую ни один из постквантовых протоколов анонимных учетных данных или слепых подписей не поддерживает. Кроме того, ARC является сублинейным по размеру коммуникации относительно количества выпущенных токенов, чего пока достигает только решеточная схема "хешируй-и-подписывай с прерываниями", хотя понятие "ограниченного числа показов" отсутствует в текущем предложении. Кроме того, было бы полезно оценить эффективные реализации, особенно для слепых подписей, а также изучить эффективные доказательства с нулевым разглашением. 

• Для ACT нам нужны протоколы для ARC и дополнительное состояние. Даже для простейшего счетчика нам нужна возможность гомоморфно вычитать из этого баланса внутри самого учетного данных. Это гораздо более сложное криптографическое требование. Также было бы интересно увидеть постквантовую защиту от двойного расходования, обеспечивающую последовательный характер ACT. 

Работа над AC и другой криптографией, сохраняющей конфиденциальность, неизбежно упирается в главное узкое место: эффективные доказательства с нулевым разглашением или, если быть точнее, эффективное доказательство вычислений хеш-функций. В ZK-схеме умножения дороги. Каждый провод в схеме, выполняющий умножение, требует криптографического обязательства (commitment), что увеличивает коммуникационные накладные расходы. Напротив, другие операции, такие как XOR, могут быть практически "бесплатными". Это оказывает огромное влияние на производительность. Например, SHAKE (примитив, используемый в ML-DSA) может быть на порядки медленнее дружественных к арифметизации хеш-функций внутри ZKP. Вот почему исследователи и разработчики уже используют Poseidon или Poseidon2, чтобы ускорить свои протоколы.

В настоящее время Ethereum серьезно рассматривает возможность миграции Ethereum на хеш-функцию Poseidon и призывает к криптоанализу, но указаний на стандартизацию нет. Это проблема: в статьях все чаще используют разные варианты Poseidon, подходящие для их случая использования, и появляется все больше и больше дружественных-к-нулевому-разглашению хеш- функций , появляющихся , адаптированных к различным случаям использования. Мы хотели бы видеть как минимум одну XOF и одну хеш-функцию для простого поля и для бинарного поля, желательно с некоторыми уровнями безопасности. И также: является ли Poseidon лучшим или просто самым известным ZK-дружественным шифром? Всегда ли он безопасен против квантовых компьютеров (как мы считаем AES), и существуют ли другие атаки, подобные недавним атакам на версии с уменьшенным числом раундов?

Взгляд на алгебру и нулевое разглашение подводит нас к фундаментальным дебатам в современной криптографии. Представьте линию, представляющую спектр исследований: на одном конце у вас протоколы, построенные на очень хорошо изученных стандартных предположениях, таких как проблема SIS (Short Integer Solution) на решетках или стойкость к коллизиям SHA3. На другом конце у вас протоколы, которые получают огромный прирост эффективности за счет использования большей алгебраической структуры, что, в свою очередь, опирается на новые, более сильные криптографические предположения. Взлом новых хеш-функций находится где-то посередине. 

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

Как мы выяснили, криптографические свойства, которые делают классические AC эффективными, в частности богатая структура эллиптических кривых, не имеют прямых постквантовых эквивалентов. Наш обзор современных подходов — от универсальных композиций с использованием STARK до различных решеточных схем и перспективных направлений вроде MPC-in-the-head — показывает область, полную потенциала, но без явного лидера. Компромиссы между стоимостью передачи данных, вычислительной стоимостью и количеством раундов протокола остаются серьезным препятствием для практического масштабируемого развертывания, особенно по сравнению с конструкциями на эллиптических кривых.

Чтобы преодолеть этот разрыв, мы должны выйти за рамки простого создания постквантовых слепых подписей. Мы призываем наших коллег в академической среде и индустрии разрабатывать полные, изначально постквантовые протоколы, отвечающие реальным потребностям. Это включает поддержку таких важных функций, как ограничение частоты запросов для каждого источника, требуемое для ARC, или сложные состояния учетных данных, необходимые для ACT.

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