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

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

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

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

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

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

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

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

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

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

Методология

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

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

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

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

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

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

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

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

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

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

Резюме

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

↑ Christoph Ludwig. (англ.) // IACR Cryptology : Article. — 2004.
↑ T. Plantard, M. Rose, W. Susilo. Improvement of Lattice-Based Cryptography Using CRT. — Quantum Communication and Quantum Networking: First International Conference. — 2009. — С. 275—282. — ISBN 9783642117305 .
↑ M. Rose, T. Plantard, F. Susilo. . — Information Security Practice and Experience: 7th International Conference. — 2011. — С. 152—167. — ISBN 9783642210303 . 22 февраля 2019 года.
↑ Thomas Richard Rond. (неопр.) . Master Thesis (2016).
↑ Daniele Micciancio. (англ.) // International Cryptography and Lattices Conference. — 2001. — С. 126—145 . — doi : . 20 июля 2020 года.
Steven Galbraith. (англ.) // Cambridge University Press : Paper. — 2012. 12 февраля 2020 года.
↑ Oded Goldreich, Shafi Goldwasser and Shai Halevi. (англ.) // Advances in Cryptology - CRYPTO. — 1997. 16 июля 2019 года.
Oded Regev. (англ.) : Lattices in Computer Science. — 2004. 1 ноября 2020 года.
Noah Stephens-Davidowitz. (англ.) : NYU, Lattices mini-course. — 2016. 29 октября 2019 года.