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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Универсальные системы 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, построены на алгебраических группах — в частности, на эллиптических кривых, которые очень эффективны. Их безопасность основана на предположении, что определенные математические задачи над этими группами вычислительно сложны. Однако предпосылка постквантовой криптографии заключается в том, что квантовые компьютеры могут решить эти предположительно сложные задачи. Наиболее интуитивное решение — заменить эллиптические кривые на постквантовую альтернативу. Фактически, криптографы работали над заменой в течение ряда лет: CSIDH. 

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

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

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

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

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

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

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

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

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

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

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

Стандартная защита от этой атаки заключается в требовании к пользователю доказать с нулевым разглашением, что точка, которую он просит подписать, является слепым выходом указанной хеш-функции. Однако доказательство прообразов хеша приводит к той же проблеме, что и в общей работе по постквантовому 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-корреляция используется как криптографическое обязательство (коммитмент) на вход доказывающего. Система предоставляет доказательство с нулевым разглашением, потому что доказывающий связан этой корреляцией и не может подделать решение, не зная секретного дельта. Верификатор, в свою очередь, должен лишь проверить, что итоговое уравнение выполняется при раскрытии коммитмента. Эта система является линейно гомоморфной, что означает, что два коммитмента можно комбинировать. Это свойство идеально для парадигмы зафиксируй-и-докажи, где доказывающий сначала фиксирует свидетелей (witnesses), а затем доказывает валидность схемы вентиль за вентилем. Основной компромисс заключается в том, что доказательства линейны по размеру схемы, но они предлагают существенно лучшее время выполнения. Мы также используем доказательства линейного размера для ARC и ACT.

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

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

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

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

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

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

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

Заключение

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

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

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