Криптосистема Миччанчо

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

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

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

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

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

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

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

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

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

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

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

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

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