CRYSTALS-Dilithium

CRYSTALS-Dilithium — один из алгоритмов постквантовой криптографии, основанный на задачах теории решёток. Представлен в 2018 на семинаре CHES, опубликован в 2021 году, авторы — Лео Дюкас (Léo Ducas), Айке Кильц (Eike Kiltz), Танскред Лепуан (Tancrède Lepoint), Вадим Любашевский, Петер Швабе (Peter Schwabe), Грегор Зайлер (Gregor Seiler), Дамиан Стеле (Damien Stehlé).

Причины создания

Основные причины создания алгоритма и цели, которых добивались создатели:

• простота безопасного осуществления (реализации) — алгоритм должен быть прост в реализации и обладать лучшими возможными временными константами при реализации, но при этом обладать достаточно серьёзными защитными свойствами;
• эффективность во введении параметров — параметры алгоритма должны быть выбраны таким способом, что реализация взлома задействует большие ресурсы для времени и памяти, таким образом, даже в наилучшей для взломщика ситуации задача взлома алгоритма будет слишком сложной, чтобы её решить;
• минимизировать размер комбинации «публичный ключ + подпись» — эта причина обусловлена тем, что многие алгоритмы и системы передают комбинацию публичного ключа и подписи, и было бы очень выгодно иметь минимальный размер этой комбинации в алгоритме;
• создать модульный алгоритм — для того, чтобы легко изменять параметры алгоритма и следить за их действием на результат работы алгоритма, сам алгоритм должен быть модульным.

Общая схема алгоритма

Генерация ключа

1. $A\longleftarrow {R_{q}}^{k\times l}$ — генерация матрицы, элементами которой являются полиномы в кольце $R_{q}=\mathbb {Z} _{q}[X]/(X^{n}+1)$, эта матрица — первая часть публичного ключа.
2. $(s_{1},s_{2})\leftarrow S_{\eta }^{l}\times S_{\eta }^{k}$ — случайные векторы, секретные ключи, размеров l и k соответственно, каждый коэффициент этих векторов — это элемент $R_{q}$, с малыми коэффициентами у многочленов: эти коэффициенты не больше $\eta$.
3. $t=As_{1}+s_{2}$ — вторая часть публичного ключа.
4. Публичный ключ — пара $(A,t)$, приватный ключ — набор $(A,t,s_{1},s_{2})$.

Подпись

1. $y\leftarrow S_{\gamma _{1}-1}^{l}$ — генерация вектора-маски $y$, состоящего из многочленов с коэффициентами меньше, чем $\gamma _{1}$. Выбор параметра — отдельная задача, так как $\gamma _{1}$ должен быть достаточно большим, чтобы подпись не раскрывала секретный ключ, но при этом достаточно маленьким, чтобы подпись было сложно подделать.
2. ${\boldsymbol {w_{1}}}=HighBits(Ay,2\gamma _{2})$ — вычисление $Ay$, и присваивание старших битов этого произведения ${\boldsymbol {w_{1}}}$. При этом каждый коэффициет $w$ в ${\boldsymbol {w_{1}}}$ может быть представлен в виде $w=w_{1}\cdot 2\gamma _{2}+w_{0}$, где $\mid w_{0}\mid \leq \gamma _{2}$; тогда ${\boldsymbol {w_{1}}}$- это вектор, включающий в себя все $w_{1}$.
3. $c\in B_{60}=H(M\mid \mid {\boldsymbol {w_{1}}})$ — создание «испытания» $c$ как хэш исходного сообщения $M$ и ${\boldsymbol {w_{1}}}$. На выходе $c$ — это многочлен в $R_{q}$, имеющий ровно 60 коэффициентов, которые равны $1$ или $-1$, остальные коэффициенты — нули. Причина такого распределения в том, что $c$ должен иметь малую норму и быть размером не меньше $2^{256}$. Для хэширования здесь удобно использовать вариацию алгоритма тасования Фишера-Йетса, которая позволяет сохранить нужное число ненулевых коэффициентов.
4. ${\boldsymbol {z}}=y+cs_{1}$ — вычисление потенциальной подписи ${\boldsymbol {z}}$. Если бы алгоритм подписывания сообщения оканчивался на этом шаге, то подпись была бы небезопасной из-за возможной утечки секретного ключа. Чтобы избежать зависимости подписи от секретного ключа, используется протокол Фиата-Шамира с прерыванием:
   1. Выбора параметра $\beta$ как максимум из коэффициентов $cs_{i}$. Так как в $c$ только 60 $\pm 1$ и наибольший коэффициент в $s_{i}$ — это $\eta$, то $\beta \leq 60\eta$.
   2. Если один из коэффициентов ${\boldsymbol {z}}$ больше, чем $\gamma _{1}-\beta$, то процедура подписи начинается заново. Эта проверка необходима для сохранения безопасности.
   3. Если любой коэффициент младших битов $A{\boldsymbol {z}}-ct$ больше, чем $\gamma _{2}-\beta$, процедура подписи начинается заново. Эта проверка необходима для корректности работы алгоритма и обеспечения безопасности.
5. Подпись — пара $({\boldsymbol {z}},c)$.

Верификация подписи

1. ${\boldsymbol {w_{1}^{'}}}=HighBits(A{\boldsymbol {z}}-ct,2\gamma _{2})$ — вычисление на стороне, проверяющей подпись.
2. Если хотя бы один коэффициент ${\boldsymbol {z}}$ больше, чем $\gamma _{1}-\beta$, то подпись не верна.
3. Если хэш исходного сообщения и ${\boldsymbol {w_{1}^{'}}}$ не равен $c$, то подпись не верна.
4. На этом шаге подпись прошла все проверки и оказалась верной.

Улучшения упрощённой схемы

• Передача матрицы как части публичного ключа занимает слишком много ресурсов памяти, поэтому вместо матрицы можно передать «семя» $\rho$ для генерации нужной матрицы и использованием, например, SHAKE-128;
• после этого возникает другая возможность оптимизации — улучшение развёртывания семени $\rho$ в матрицу $A$. На этом этапе нужно уделить внимание выбору функции хэширования, чтобы дехэширование занимало не слишком много времени, так как матрица используется на этапах и создания подписи, и её верификации;
• в ${\boldsymbol {w_{1}^{'}}}$старшие биты $A{\boldsymbol {z}}-ct$ практически не зависят от младших битов $t$, потому что $t$ умножается на многочлен $c$ с небольшими весами (коэффициентами). Поэтому можно не включать в публичный ключ младшие биты $t$, что позволит ещё больше уменьшить размер публичного ключа. Но из-за этого не всегда можно будет правильно подтвердить подпись, поэтому в подпись также включаются подсказки для проверяющего алгоритма. Эта подсказка содержит в себе ту часть произведения, которую мы потеряли, убрав младшие биты $t$ из публичного ключа. Выигрыш здесь заключается в уменьшении размера публичного ключа и меньшем числе умножений при проверке подписи. Эти изменения позволяют уменьшить размер публичного ключа в 2.5 раза ценой увеличений рзамера подписи не больше, чем на 200 байт;
• можно улучшить скорость матричного умножения в схеме с помощью дискретного преобразования Фурье. Это известный способ улучшения эффективности умножения матриц в задачах и алгоритмах, основанных на решётках. ДПФ позволяет представить произведение двух полиномов как скалярное произведение двух векторов;
• с помощью добавления семени в секретные ключи и использования этого семени в хэшировании сообщения можно сделать $y$ в пункте 1 подписи случайным вектором, а не детерминированным;
• базовые оптимизации пре-хэширования позволяют избежать повторных вычислений хэша «с нуля» при создании подписи;
• векторизация векторных и матричных вычислений способна дать ощутимое преимущество в вычислительной мощности данного алгоритма (25 % и больше);
• так как процедура подписи может выполняться несколько раз, то чтобы избежать определённости создания подписи (детерминированности), можно добавить счётчик в создание подписи и добавлять этот счётчик к хэшу, таким образом, делая процесс создания подписи более случайным, то есть с каждой попыткой хэширования, будет получаться новое значение хэша с одним и тем же исходным сообщением.

Безопасность

Стандартным способом проверки безопасности для цифровых подписей является UF-CMA — это симуляция, где противник получает открытый ключ и имеет доступ к подписывающему свидетелю (оракулу) для подписи сообщений по своему выбору. Задача противника — придумать (сфальсифицировать) правильную подпись нового сообщения. Несколько более сильное требование безопасности, которое иногда полезно — это SUF-CMA (сильная непробиваемость при атаках с использованием выбранных сообщений), которое также позволяет противнику выиграть, создав другую подпись сообщения, которое он уже видел.

В классической модели случайного оракула (свидетеля), Dilithium является SUF-CMA на основе трудности стандартных задач MLWE и MSIS. Редукция, однако, не является жёсткой. Более того, поскольку алгоритм также должен противостоять квантовым атакам, необходимо рассматривать безопасность схемы, когда противник может запросить хэш-функцию на суперпозиции входных данных (то есть, безопасность в квантовой модели случайного оракула — QROM). Поскольку классическое доказательство использует лемму о вилке (которая по сути является раскруткой или размоткой), то редукция не переносится на квантовую среду.

Не известно контпримеров схем, на безопасность которых действительно влияет неприменяемость редукции. Например, такие схемы, как схема Шнорра устанавливают свои параметры, игнорирую нежёсткость редукции. Более того, единственное известное использование дополнительной мощности квантовых алгоритмов против схем, безопасность которых основана на квантово-устойчивых проблемах при классической редукции включают алгоритмы «типа Гровера», которые улучшают исчерпывающий поиск (хотя и было показано, что не может быть доказательство того, что протокол Фиата — Шамира безопасен в QROM).