СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ
1. Фихманас Р.Ф., Фридберг П.Ш. Метод Хоу расчёта ёмкости тел и его связь с вариационными принципами // ЖТФ. - 1970. - Т.40. - вып.6. - С. 1327-1328.
2. Признак Дирихле [Электронный ресурс] : Википедия - Свободная энциклопедия : [сайт]. URL: http://ru.wikipedia.о^^Ы/Признак_Дирихле (дата обращения: 24.12.2009).
3. Иоссель Ю. Я., Кочанов Э. С., Струнский М. Г. Расчет электрической емкости. 2-е изд., перераб. и доп. СПб. : Энергоиздат. Ленингр. отд-ние, 1981. 288 с.
4. Лаврентьев М. А., Шабат Б. В. Методы теории функции комплексного переменного. - 4-е изд., перераб. и доп. М. : Наука, 1973. 749 с.
5. Двайт Г. Б. Таблицы интегралов и другие математические формулы / Г. Б. Двайт; перевод с англ. Н. В. Леви; под ред. К. А. Семендяева. 5-е изд. М. : Наука : Главная редакция физико-математической литературы, 1978. 224 с.
УДК 003.26.09:512.5
СИСТЕМЫ ШИФРОВАНИЯ ОСНОВАННЫЕ НА ЗАДАЧАХ ТЕОРИИ РЕШЕТОК
В.С. Усатюк, аспирант О.В. Кузьмин, доктор физико-математических наук
Братский государственный университет г. Братск, Россия
В работе представлен обзор достижений динамично развивающейся отрасли криптографии, а именно шифрования, основанного на задачах теории решеток. Работа содержит необходимые базовые определения, описание основных задач теории решеток, а так же представлены основные преимущества этого класса криптографии - свойство криптостойкости по отношению к квантовым и молекулярным вычислителям и возможность реализации гомоморфного шифрования на основе идеальных решеток.
Ключевые слова: решетка, шифрование, хеш-функция, квантовая и молекулярная криптостойкость.
Развитие теории распределенных вычислений в сочетании с ростом производительности ЭВМ вызвало необходимость в значительном увеличении криптостойкости хеш-функций, а так же протоколов ассиметричного шифрования (RSA, ECC). Все это привело к увеличению длины ключа (дайджеста хеш-функции), а так же к значительному росту вычислительной сложности шифрования.
В свою очередь алгебры, основанные на молекулярных [1, с. 63] и квантовых вычислителях [2, с. 200] позволили реализовать алгоритмы расшифровки сообщений и поиск коллизии за полиномиальное время, для задач NP* coNP(= P) класса. В результате возникла
необходимость в теоретических исследованиях и практической реализации нового поколения криптографических протоколов и примитивов - основанных на NP-полных задачах, не позволяющих реализовывать обращение таковых задач быстрее, чем с субэкспоненциальной сложностью [3].
Перспективными кандидатами на роль таковых задач, стали задачи теории решеток. Перед тем, как непосредственно перейти к изложению формулировки этих задач, введем необходимый набор определений.
Решетка - дискретная аддитивная подгруппа, заданная на множестве R", т. е. решетку L можно представить как множество целочисленных линейно независимых базисных векторов
n
B = {b1,...,bn } с Rn, L = ^ bi ■ Z = {Bx : x e Zn } , (рис. 1). У решетки может быть множество
i=1
n
базисов, L = ^ai ■ Z, (рис. 2).
i=1
• *
Рис. 1. Решетка с базисом {b1;b2} е B Рис. 2. Решетка с базисом {a1,a2} е B
На рисунках 3, 4 показаны фундаментальные параллелепипеды образованные базисами. Площади (объемы в многомерном случае) фундаментальных параллелепипедов образованных всевозможными базисами одной решетки Ь, det(Ь) будут равны. Т.е. detЬ инвариант
решетки.
Рис. 3, 4. Фундаментальные параллелепипеды, образованные базисами
Под кратчайшим вектором решетки будем понимать вектор с координатами l (L) = min llx - yll = min ||х|| (рис. 5). Тогда многомерным обобщением этого понятия
х,уеЬ,хФ y хеЬ,хФ 0
будет l (L) - ограниченное минимальным r, для которого размерность решетки внутри шара радиуса г больше либо равна к (рис. 6).
Рис. 5. Кратчайший вектор Рис. 6. Кратчайший базис решетки Ь в Я2
Таким образом, познакомившись с основными определениями теории решеток, перечислим некоторые из задач этой теории активно применяемых в криптографии:
1. По базису решетки, найти кратчайший ненулевой вектор (shortest vector problem, SVP), (рис. 7);
2. По базису решетки, найти ненулевой вектор не превосходящий g ■ 1i(L) (shortest vector problem, SVPg ), (рис. 8);
Рис. 7. Пример SVP-задачи в R2 Рис. 8. Пример SVPy -задачи в R
3. По базису решетки, заданному вектору j , найти ближайший вектор b к вектору j (Closes Vector Problem, CVP), (рис. 9);
4. По базису решетки, заданному вектору j, найти вектор, находящийся на расстоянии l £ g (Closes Vector Problem, CVPg);
5. Найти m линейно независимых векторов Bm в решетки, для которых
maxllBxJI £ 1n (Shortest Independent Vector Problem, SIVP), (рис. 10)
i
Рис. 9. Пример CVP -задачи в R2 Рис. 10. Пример SIVP -задачи в R2
6. Найти m линейно независимых векторов в базисе решетки Bxm, для которых max||BxJ| £ g1n (Shortest Independent Vector Problem, SIVPg);
7. Поиск кратчайшего расстояния между векторами в базисе решетки; по заданному базису ответить на вопрос, не превосходит ли кратчайший вектор норму N (Decisional SVP, GapSVP) ;
8. По базису решетки, заданному вектору j и e > 0 ответить на вопрос о существовании вектора v в решетке, близкого к вектору j с точностью до e (Decisional CVP, GAPCVP);
9. По базису решетки, в котором кратчайший вектор в k-раз меньше другого кратчайшего линейно независимого вектора, найти кратчайший вектор (Unique Shortest Vector Problem, uSVP), (рис. 11);
10. Дана решетка с минимальным расстоянием l (необязательно известным), по базису B
и вектору j такому, что р (B, j) < g найти вектор в решетке (Bounded Distance Decoding, BDD), (рис. 12).
• _
J =
v •
< »-»-s~
Рис. 11. Пример uSVP-задачи
Рис. 12. Пример BDD-задачи
Теория решеток считалась завершенной, будучи исследованной Лагранжем, Гауссом, Дирихле и другими выдающимися математиками. Не смотря на тот факт, что до 1996 г. оценки сложности отсутствовали и единственное, что было известно - CVP является NP-полной [4].
В 1996 г. венгерский математик-исследователь IBM Миклос Айтаи в своей работе [5] показал, что [6]:
- возможно построить одностороннюю функцию на основе SVP-задачи; более поздние исследователи улучшили результат до «односторонней функции с секретом» (trapdoor function, [7]) - вариантом односторонней функции, быстро обращаемой (по сравнению со скоростью получения образа функции) при наличии дополнительных сведений;
- переформулированная в вероятностный вариант задачи о рюкзаке, SVP-задача не имеет вероятностного полиномиального алгоритма решения, т. е. не разрешима за полиномиальное время на молекулярных и квантовых вычислителях;
- среди всего класса NP-задач, SVP-задача является самой сложной, т.е. является NP-полной задачей.
Работа Айтая продемонстрировала преимущество протоколов шифрования и криптографических примитивов на основе задач теории решеток перед традиционными системами шифрования, основанными на хеш-функциях содержащих коллизии, задачах факторизации чисел (RSA) и дискретного логарифмирования (ECC) принадлежащих NP* coNP-классу.
На основе задач GapSVP и SIVP Айтаем в 1996 г. [5] были предложены методы реализации свободных от коллизий хеш-функций. Опишем эту хеш-функцию Айтая подробнее, так как остальные алгоритмы шифрования построены по аналогии.
Функция Айтая - это функция вида fa (x) = Ax modq, где A e Znm и x e {0,1}m. Например, при q = 10, n = 4, m = 7:
fa (x) = Ax mod q =
(1 2 3 4 5 6 71
0 5 6 8 4 3 0
1 7 3 7 3 2 9
V 4 8 2 5 2 1 4 0
( 0 ^ 1 0 1 1
0 0
mod10 = (1 7 7 5).
Параметры криптографии задаются из следующих соображений: n - основной параметр, определяющий защищенность q = no(1), m = O(n logn) > n log2 q , последнее обусловлено тем, что при n>>m задача обращения легко разрешима. Для n = 1024,q = 232,m = 65536. Т.е. функция Айтая fa(x)- сжимает m-исходных бит в n log2 q < m, в данном случае 65536 в 32768 бит.
Покажем связь с теорией решеток: ядром множества A е Znm является решетка L(A) = {z е Zm : Az = 0(modq)} . Тогда коллизия хеш-функции (fa (x) = fa (y), x Ф y) станет вектором вида z = x - y е {-1,0,1}: Az = Ax - Ay = 0modq или же, zt е L(A) с нормой ||z|| = max|zj = 1. Т.е. поиск коллизий хеш-функции Айтая fa (x) соответствует решению
SVP-задачи в решетке L.
Коллектив ученых Голдштейн-Голдвассер-Халеви (GGH) в 1997 [8] предложил вариант хеш-функции на основе псевдокуба, построенного на векторах некоторой решетки L .
Мисиансио и Рэджев [9], [10, сл. 56-60] предложили общий подход к шифрованию, основанный на добавлении шумов в решетку, что позволяет получить решетку, неотличимую от равномерного распределения. Затем, путем разбиения решетки на ячейки, построить отображение, позволяющее реализовать свободную от коллизий хеш-функцию и протокол ассиметричного шифрования. Эта концепция определила современное направление развития криптографии на основе теории решеток.
Циклическая решетка - решетка вида А = [ А А ], А е , т.е. решетка,
характеризующаяся некоторой постоянной структурой, получаемой в результате перестановки элементов по некоторому правилу, например:
) а") . а(0 ■
A1 =
a
a
jJ )
Ji )
Jf)
A1 | A2 | A3 =
7 1 4 3 0 2 3 4 9 3 5 1
3 7 1 4 4 0 2 3 5 9 3 5
4 3 7 1 3 4 0 2 1 5 9 3
1 4 3 7 2 3 4 0 3 1 5 9
" "-1 1
Крис Пеинкерт и Алон Розен в 2006 г. [11] предложили свой вариант хеш-функции, основанной на круговой общей 81УР-задаче на циклических решетках: заданный вектор
определен целочисленным полиномом Р(а) Ф 0mod(а" — 1), необходимо найти множество или подмножество линейно независимых векторов с нормой пропорциональной величине нормы общих векторов полинома и решетки. Хеш-функция Пеинкерта-Розена обладает важными свойствами, которые выделяют ее среди всех остальных функций: линейной зависимостью длины образа хеш-функции от ее прообраза и линейным ростом сложности вычислений по времени.
Одновременно с созданием криптографических примитивов были предложены следующие системы ассиметричного шифрования на основе решеток размерности " :
- система Л^аьБшогк основанная на и8УР-задаче, с публичным ключом длины "4;
- система Оо№е1сЬ-ОоЫша88ег-На1еу1 (ООН) основанная на приближенн
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.