Криптосистема Миччанчо (Tjnhmkvnvmybg Bnccguck)

Криптосистема Миччанчо — криптосистема, основанная на схеме шифрования GGH, была предложена в 2001 году профессором Университета Калифорнии в Сан-Диего Даниелем Миччанчо.

Схему шифрования GGH опирается на криптографию на решётках, которая считается перспективной для использования в постквантовых системах (поскольку криптосистемы, использующие факторизацию целых чисел, дискретное логарифмирование, дискретное логарифмирование на эллиптических кривых могут быть эффективно взломаны квантовым компьютером при применении алгоритмом Шора). Криптосистема Миччанчо, по факту, является улучшением схемы шифрования GGH, с уменьшением требований к размеру ключа и шифротекста в $N$ раз без ухудшения безопасности системы, где $N$ — размерность решётки. Для типичных криптосистем составляет несколько сотен. В 2004 году Кристоф Людвиг эмпирически показал, что для безопасного использования требуется ${\textstyle N\geq 782}$, к тому же, создание ключа и его дешифровка занимает непозволительно много времени, а сам размер ключа должен быть больше 1 МБ. По этой причине данная криптосистема не может быть использована на практике.

Основные понятия и обозначения

Пусть $\mathrm {B} =\{\mathbf {b} _{1},...,\mathbf {b} _{N}\}$, где $\mathbf {b} _{i}\in \mathbb {R} ^{M},i={\overline {1,N}}$ — набор из $N$ линейно независимых векторов и компоненты каждого из векторов представляют собой целые числа, а $B$ — матрица из этих векторов размера $M\times N$. Далее, теория строится для $M=N$. Решёткой будем называть множество ${\mathcal {L}}(\mathrm {B} )=\{\mathrm {B} x\mid x\in \mathbb {Z} ^{M}\}$.

В силу того, что базис $\mathrm {B}$ может быть не уникальным, принято выбирать в качестве базиса эрмитову нормальную форму, которая для каждой отдельно взятой решётки уникальна. Это значит, что матрица, составленная из векторов базиса, есть верхняя треугольная, все диагональные элементы строго положительны, а остальные элементы удовлетворяют $0\leq b_{ij}<b_{ii}$. Данный вид матриц обладает следующими полезными свойствами. Во-первых, через ортогонализацию Грама — Шмидта такая матрица приводится к диагональному виду с элементами $b_{ii}$ на диагонали. Во-вторых, детерминант такой матрицы равен произведению её диагональных элементов, то есть ${\textstyle \det(\mathrm {B} )=\prod _{i=1}^{n}b_{ii}}$.

Из последнего также следует важное свойство целочисленных решёток:

Пусть произвольные вектора $v$ и $w$ таковы, что $v_{i}\equiv w_{i}\ \mod \det(\mathrm {B} )$. В этом случае $v\in {\mathcal {L}}(\mathrm {B} )$ тогда и только тогда, когда $w\in {\mathcal {L}}(\mathrm {B} )$.

Пусть ${\textstyle {\mathcal {P}}(\mathrm {B} ^{*})=\{\sum _{i}x_{i}\mathbf {b_{i}^{*}} \ |\ 0\leq x_{i}<1\}}$ — прямой параллелепипед, где $x_{i}$ — целочисленные координаты, $\mathbf {b_{i}^{*}}$ — ортогонализованные по процессу Грама — Шмидта базисные векторы, $i={\overline {1,N}}$. Пространство $\mathbb {R} ^{N}$ может быть замощено такими параллелепипедами. Тогда для любого $v\in \mathbb {Z} ^{N}$ существует уникальный вектор $w\in {\mathcal {P}}(\mathrm {B} ^{*})$. Такой вектор называется редуцированным для вектора $v\in \mathbb {Z} ^{N}$ по модулю $\mathrm {B}$. Он получается нахождением относительной позиции $v$ в $z+{\mathcal {P}}(\mathrm {B} ^{*})$, где $z\in {\mathcal {L}}(\mathrm {B} )$.

Данный вектор может быть найден по следующему алгоритму:

1. Найти ${\textstyle \alpha _{i}={\frac {\langle v,b_{i}^{*}\rangle }{\langle b_{i}^{*},b_{i}^{*}\rangle }}}$
2. Вычислить искомый вектор по формуле $w=v-\lfloor \alpha _{i}\rfloor \mathbf {b_{i}} \in {\mathcal {P}}(\mathrm {B} ^{*})$.

Методология

В криптосистемах на решётках ключами являются базисы. Пусть $\mathrm {B}$ и $\mathrm {R}$ — публичный и приватный базисы одной и той же решётки ${\mathcal {L}}={\mathcal {L}}(\mathrm {B} )={\mathcal {L}}\mathrm {(} R)$. Отличие данной криптосистемы от системы шифрования GGH заключается в более оптимальном выборе односторонней функции. Важная особенность функции в криптосистеме Миччанчо — детерминированность. В следующем разделе строится общий класс функций вида GGH.

Класс односторонних функций вида GGH

Для схемы шифрования GGH односторонняя функция принимает вид $c=\mathrm {B} x+\epsilon$, где $c$ — шифротекст, $x$ — целочисленный вектор и $\epsilon$ — вектор ошибки длиной не более $\rho$, ${\frac {1}{2}}\min _{i}(\mathbf {b_{i}^{*}} )\ll \rho ={\frac {1}{2}}\min _{i}(\mathbf {r_{i}^{*}} )$. Последнее необходимо для того, чтобы ошибка не создавала сильных искажений при вычислении с приватным базисом и, наоборот, для вычислений с публичным. Предполагается, что сообщение $m$ кодируется в $\epsilon$, а $x$ выбирается случайно.

Семейство односторонних функций GGH-вида $f_{\beta ,\gamma }$, параметризованное алгоритмами $\gamma$ и $\beta$, удовлетворяет:

1. $\beta$ принимает на вход приватный базис $\mathrm {R}$, а выводит публичный базис $\mathrm {B}$ для той же решётки.
2. $\gamma$ получает $\mathrm {B}$ и $\epsilon$, а возвращает коэффициенты точки решётки $x$
3. Тогда $f_{\beta ,\gamma }$ отображает множество векторов короче $\rho$ следующим образом: $f_{\beta ,\gamma }(\epsilon )=\beta ({\mathsf {R}})\gamma ({\mathsf {R}},\epsilon )+\epsilon$

Если вектор ошибки имеет длину меньше $\rho$, тогда приватный базис $\mathrm {R}$ может быть использован для нахождения точки $\mathrm {B} x$, ближайшей к $f_{\beta ,\gamma }(\epsilon )$, и, соответственно, восстановления $\epsilon$ (задача нахождения ближайшего вектора).

Выбор публичного базиса

Пусть известен «хороший» приватный базис $\mathrm {R}$, то есть с помощью него возможно решить проблему задачу нахождения ближайшего вектора в ${\mathcal {L}}\mathrm {(} R)$, что то же самое — расшифровать шифротекст. Задача — сгенерировать из $\mathrm {R}$ такой публичный базис $\mathrm {B}$, чтобы минимизировать в нём информацию об $\mathrm {R}$. В обычной схеме шифрования GGH для нахождения $\mathrm {B}$ применяется набор случайных преобразований к $\mathrm {R}$. Криптосистема Миччанчо использует в качестве публичного базиса $\mathrm {B}$ эрмитову нормальную форму, то есть $\mathrm {B} =HNF(\mathrm {R} )$ (HNF — Hermite Normal Form). Она уникальна для конкретно заданной решётки, как уже говорилось выше. Это ведёт к тому, что если есть какой-то другой базис для данной решётки $\mathrm {B} '$, то $\mathrm {B} =HNF(\mathrm {R} )=HNF(\mathrm {\mathrm {B} '} )$. Значит, $\mathrm {B}$ содержит об $\mathrm {R}$ не больше информации, чем о $\mathrm {B} '$, на чём и базируется безопасность данной криптосистемы.

Прибавление «случайной» точки решётки

Далее, требуется сымитировать прибавление случайной точки решётки $\mathrm {B} x$. В идеале, эта точка должна выбираться равномерно произвольно среди всех точек решётки. Однако это невозможно ни с практической, ни с теоретической точки зрения. Почти такой же результат получается при использовании редуцированного вектора. Вектор ошибки $\epsilon$ уменьшается по модулю публичного базиса $\mathrm {B}$, чтобы получить шифротекст $c\in {\mathcal {P}}(\mathrm {B} ^{*})$, вместо прибавления случайного вектора. В итоге односторонняя функция задаётся как $f(\epsilon )=\epsilon {\pmod {\mathrm {B} }}$, где $\mathrm {B} =HNF(\mathrm {R} )$. Благодаря верхней треугольной формы матрицы $\mathrm {B}$ данная функция очень проста с вычислительной точки зрения. Применяя рассуждения для вычисления редуцированного вектора, может быть найдена формула $x_{i}=\lfloor {\frac {\epsilon _{i}-\sum _{j>i}b_{ij}x_{j}}{b_{ii}}}\rfloor$, начиная с $x_{N}$, что даёт уникальную точку в параллелепипеде ${\mathcal {P}}(\mathrm {B} ^{*})$.

Резюме

Пусть $\mathrm {R}$ — приватный базис, причём $\rho ={\frac {1}{2}}\min _{i}(\mathbf {r_{i}^{*}} )$ является относительно большим, $\mathrm {B}$ — публичный базис и $\mathrm {B} =HNF(\mathrm {R} )$. Базис $\mathrm {B}$ порождает функцию $f(\epsilon )=\epsilon {\pmod {\mathrm {B} }}$, которая переводит вектора длины меньше $\rho$ в соответствующий $\mathrm {B}$ прямой параллелепипед ${\mathcal {P}}(\mathrm {B} ^{*})$. Ключевые моменты:

1. Даже если изначально $f(\epsilon )$ близка к точке $\epsilon$, после операции редукции получается вектор, близкий к другим точкам решётки.
2. Чтобы восстановить $\epsilon$ по $f(\epsilon )$, необходимо решить задачу задачу нахождения ближайшего вектора, для которой доказана NP-сложность. Поэтому восстановить $\epsilon$, имея только $\mathrm {B}$, почти невозможно, даже для квантовых компьютеров. Однако она эффективно решается, если известен базис $\mathrm {R}$.
3. Ближайшая точка к $f(\epsilon )$ — центр параллелепипеда, в котором содержится $f(\epsilon )$, а он находится легко, зная базис $\mathrm {R}$.

Теоретический анализ

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

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

Имеет место следующее утверждение: для любых функций $\beta ,\gamma$ и для любого алгоритма, который для $f(\epsilon )$ находит об $\epsilon$ какую-то частичную информацию с ненулевой вероятностью, существует эффективный алгоритм со входом $f_{\beta ,\gamma }(\epsilon )$ способный восстановить такую же информацию с такой же вероятностью успеха.

Доказательство: пусть $A$ — алгоритм способный взломать $f$. Даны публичный базис $\mathrm {B}$ = $\beta (\epsilon )$ и шифротекст $c=\mathrm {B} \gamma +\epsilon$. Алгоритма взлома должен попытаться найти какую-нибудь информацию об $\epsilon$. Во-первых, $\mathrm {B} '=HNF(\mathrm {B} )$ и $c'=c{\pmod {B'}}$. Из теоретических результатов в предыдущем разделе следует, что $\mathrm {B} '=HNF(\mathrm {R} )$ и $c'=\mathrm {B} \gamma +\epsilon {\pmod {B'}}=\epsilon {\pmod {B'}}$. Поэтому $B'$ и $c'$ имеют правильное распределение. Применяя к ним алгоритм $A$, получается утверждение теоремы.

Асимптотические оценки памяти

Пусть для приватного ключа выполняется $|r_{ij}|<poly(N)$, тогда размер, занимаемый ключом, оценивается $O(N^{2}\ \lg N^{2})$. Используя неравенство Адамара, а также то, что для публичного базиса и шифротекста GGH системы выполняются оценки $O(N^{2}\ \lg(\det({\mathcal {L}})))=O(N^{2}\ \lg(N))$ и $O(N\ \lg(\det({\mathcal {L}})))=O(N\ \lg(N))$, следует, что оценки на публичный базис и шифротекст нашей системы $O(N^{2}\ \lg(N))$ и $O(N\ \lg(N))$.

Асимптотические оценки времени исполнения

Теоретически, ожидается ускорение работы алгоритма по сравнению с GGH по двум причинам (эмпирические результаты приведены ниже). Во-первых, время шифрования для GGH систем сильно зависит от размера публичного ключа. Теоретические оценки на занимаемую ключом память указывают на её уменьшение, а следовательно и на ускорение шифрования. При этом время работы GGH сравнимо со временем работы схемы RSA. Во-вторых, для генерации ключа исходный алгоритм применяет алгоритм Ленстры — Ленстры — Ловаса к матрицам большой размерности с большими значения элементов, в то время как система Миччанчо использует достаточно простой алгоритм нахождения эрмитовой нормальной формы. Для дешифровки используется алгоритм Бабая, с некоторыми потерями по памяти и точности, но улучшением по времени его можно заменить на более простой алгоритм округления, однако в данной части ускорения по времени исполнения не ожидается.

Эмпирическая оценка безопасности системы

На практике для безопасности данной системы требуется $N\geq 782$. При предположении, что улучшение времени достигает максимальных асимптотических оценок, минимальное необходимое $N$ должно быть больше $2093$. Далее было показано, что публичный ключ должен быть не менее 1MB. Более того, время генерации ключа занимает порядка дня. Процедура шифрования, действительно довольно быстра. Однако дешифровка нестабильна из-за алгоритма Бабая. Это можно преодолеть, но тогда она будет занимать 73 минуты для $N=800$, не включая ортогонализацию. Если выполнить этот шаг заранее, то к расходам на память прибавляется 4.8 MB для той же размерности. Из этих результатов следует, что криптосистема Миччанчо неприменима на практике.

Литература

• Daniele Micciancio, Oded Regev Lattice-based cryptography // Post Quantum Cryptography. — 2009.
• Daniele Micciancio Improving lattice-based cryptosystems using the Hermite normal form // Lecture notes in Сomputer Science. — 2001.
• Christoph Ludwig The Security and Efficiency of Micciancio’s Cryptosystem // IACR Cryptology. — 2004.