Полностью Гомоморфное Шифрование

Международный журнал по вопросам   безопасности и ее приложения 
Том 6, № 2, апрель 2012 г.

 

 

                                                Полностью   Гомоморфное Шифрование.

Полностью гомоморфное схемы шифрования на странице  [3, 6], в этой  статьи производится атака и находят эквивалентный секретный ключ и непосредственно восстанавливают текст из зашифрованного текста для решетки размерности n= 2048 с решеткой алгоритмом сокращения. Учитывая в среднем случае поведение LLL 
В [8] верна, то их схемы также не является безопасным для n = 8192. 
Ключевые слова: Полностью Гомоморфные шифрования, криптоанализ, главный идеальной решетки, решетки сокращения.

 

1 .Ведение .

Ривест ,Адлеман , и Дертоузос в первые представили концепцию гомоморфного шифрования , которая широко используется в криптографии .Это стало ненадежным в 2009 когда Джентри построил первую  полное  гомоморфное шифрование на основе идеальной решетки . После того, как представлены схемы Смарт и Веркатерен [3] были усовершенствованы ПГШ с меньшим зашифрованный текстом и ключом, используя главный идеал решетки. Дейк, Джентри, Халеви и Вайканаф предложили схему  простого полностью гомоморфного шифрования над целыми числами ,безопасность которых зависит от прочности примерных решений GCD над целыми числами. Шахи и Стенфилд  улучшили Джентривскую полностью 
гомоморфную схему и получить быструю полностью гомоморфную схему. Схожую 
Джентри и Галеви реализовали схему Джентри, применяя основную идеальную решетку. 
Безопасности ПГШ зависит от прочности предположение о нахождении небольшой 
основной идеальной решетки, учитывая ее форму HNF или двух элементов формы. Этот документ будет 
приводить две решетки атак ПГШ в [3, 6].

1. Наши Результаты.

В следующей атаке, мы используем конкретные параметры ПГШ в [3, 6]. За 
полиномиальное время, блок решетки сокращения алгоритма [7], мы находим эквивалентный секретный ключ при n = 2048 об GUI в [3, 6]. Учитывая средние поведение при LLL [8], 
соотношение составляет примерно , где 380 является размером бита  коэффициентов в генератор многочлена [6]. В результате, наши первый 
результат показывает, ПГШ в [3, 6] не являются безопасными для n = 8192. 
Наш второй результат непосредственно восстанавливает текст из зашифрованного при n= 2048, 8192  
применениеv усредненного поведения при LLL алгоритма[8].

2. Структура .

В разделе 2 приведены некоторые обозначения и решетки алгоритмов сокращения. Раздел 3, 4 
анализ безопасности ПГШ в [3, 6]. Раздел 5 представляет нападение напрямую с  
восстановление текста из шифротекста для ПГШ [3, 6]. Раздел 6 завершает работу  
и дает две открытые проблемы.

 

2.Подготовительные работы .

2.1 Обозначения .

Пусть n будут безопасные параметры  , [n]={0,1….,n}. Пусть R –кольцо целочисленных многочленов 
модулю f_n(x) , т.е, R=n[x]/f(x) ,где f_n(x) неприводимый многочлен степени n над целыми числами .

Пусть  R_p  обозначает кольцо многочленов n_p[x]/f(x)    по модулю p. Для обозначим через

бесконечностью критериев   вектор коэффициентов многочлена u c коэффициентами по модулю 2. Для кольца R, его расширение множитель в n , то есть,

где ´ является умножения над R.

2.2  Алгоритм решетки сокращения.

Учитывая основные решетки b₁…,b_n , одна из самых известных проблем алгоритмов 
теории решеток, чтобы найти короткий ненулевой вектор. В настоящее время не существует алгоритма  для решения за полиномиального время за кратчайший ненулевой вектор в данной решетке. Наиболее 
знаменитый LLL алгоритм [9] считает, вектор, аппроксимирующие большие   множества  2^(n-1)/2..

В 1987, Шнорром [10] введено сокращение иерархии решетки, обобщающий 
LLL снижение до Коркина-Золотарёва сокращение, которое получается за полиномиальное время 
алгоритма (4k²)^n/2k  для приближенного множества решеток любого ранга. Время работы 
алгоритма Шнорра является поли (размер основы) × HKZ (2k), где HKZ (2k) равен O(2^2k). Чтобы гарантировать 
вычисление возможно, мы будем выбирать  k=16 в следующем.

Теорема  2.1 (Теорема 2.6 [10])

Каждый блок 2k-приведенный базис ,b₁...,b_mk решетки L удовлетворяет где b другая постоянная решетки использования в алгоритме анализа Шнорра. 
Гама Ховген, Кой и Нгуен [7] улучшили приближения множителя Шнорра  2k -уменьшили  
в и доказали следующие результат через Ранкинову 
постоянную. 
Теорема 2.2 (теорема 2, 3 [7]) Для всех к ³ 2, константа Шнорра b_k удовлетворяет: 
Асимптотически удовлетворяет  
В частности, для всех к £ 100. 
Теорема 2.3 ([8]). Предположим, что средняя поведения при LLL это истина, то первый 
вектор b₁ вLLL приведенного базиса выполняется в в среднем на L.

3. Криптоанализ схемы Smart-Vercauteren .

 
3.1 Полностью Гомоморфные Шифрование 
Алгоритма генерации ключей (KeyGen).

(1)Выберите случайный многочлен   такое, что  
является h-разрядным целым числом, u(х) = 1mod2 и р = Det (Rot (u(х))) это простые  числа. 
(2) Вычисляем . Пусть является единственным корнем d(X). 
(3) Применим XGCD-алгоритм над Q [X] для получения  такие, что 
 
(4) Предположим что b = (V (X) Mod X)mod(2р). 
(5) Выходной открытый  ключ pk = (р, a), тайный ключ sk = (р, b). 
Алгоритм шифрования (ENC). Учитывая публичный ключ pk и m Î {0,1}, выбираем небольшой случайный 
многочлен r(х), где ||r(х)||_¥ является m-битное целое. Выходной зашифрованный  текст .

 
Алгоритм расшифровки (DEC). Учитывая секретный ключ sk и зашифрованного текста c, расшифровывается долго  
Все остальные детали ПГШ опущены (см. [3]).

3,2 Криптоанализ Smart-Vercauteren ПГШ.

По генерации ключа , g = (х) является  простым элементом  в норме числового поля K 
определяется f_n(x), и a является корнем f_n(x)modp. А именно, мы получаем идеал 
 
На поверхности, необходимо получить секретный ключ v(х), чтобы атаковать ПГШ. В самом деле, если получится небольшой несколькими W (X) = d (х) ´ V (х) и v(х), где d (х) является полиномом с небольшим целым  коэффициентом , можно непосредственно расшифровать зашифрованный текст. Так как , значит  
, где .Таким образом,  
через g = 1. Так, один случайным образом выбираем малый коэффициент многочлена С (х), генерируем 
зашифрованный текст C = C (a) по модулю р, и решаем выше уравнения. Как только узнаем w(х)b 
, можно расшифровать зашифрованный текст произвольно с небольшой помехой. Таким образом, нам нужно только представить алгоритм, который генерирует подходящий многочлен w(х).

Теорема 3.1. Учитывая, главный идеал в p либо два элемента (р, a) или HNF представление, 
существует полиномиальный алгоритм, который находит время и (х) = d (х) ´ v(х) над таким, что

Доказательство. Так как a является корнем по модулю р, так что . Легко проверить, . Предположим, .Одина конструкция  
следующий решетки М.

Чтобы уменьшить решетку  М,  называем алгоритм решетки сокращения [7,10]. По теореме 2.1 
2.2, получаем w(х) = d (х) ´ v(х) такой, что  
 
Напомним, что w(х) Î R, так как . ■

При n= 2048, k = 16 и h > 298, .Теперь, если  
тогда можно правильно восстановить бит в зашифрованном тексте.

Пример 3.1 Пусть и из которых следует :

Таким образом, и открытый ключ .По pk вычисляем один Для получения w(х), строится решетка M 
и вызывает LLL алгоритм в M. В самом деле, можно найти точное решение и v(х) приведем  небольшой 
пример. Без ограничения обобщённости , предположим, что Для простоты мы вычислим 

Чтобы найти [d (х)]₂, сначала вычисляет зашифрованный текст.

Поскольку

Таким образом, расшифровывает зашифрованный с помощью секретного ключа эквивалентным

 

4. Криптоанализ схемы Джентри-Халеви Шейма. 
4,1 Полностью Гомоморфные Шифрование. 
Алгоритма генерации ключей (KeyGen). 
(1) Выберите случайный многочлен , где каждая запись u и есть h-битная 
целое число, а р = Det (Rot (u(х))) это нечетное число. 
(2) Используем XGCD-алгоритм над Q [X] для получения  таких, что 
 
(3) Убедитесь, что u(х) является правильным многочленом генерации. Здесь u(х) является хорошим, если Эрмита нормальная форма имеет следующий вид.

(4) Выход открытого ключа pk=(p,a), и секретного ключа sk=(p,(v(x)).

Алгоритм шифрования (ENC). Учитывая публичный ключ pk и бит m Î {0,1}, выбираем небольшой случайный 
многочлен r(х), где ||r(х)||_¥ =1 Выходной зашифрованный  текст .

 
Алгоритм расшифровки (DEC). Учитывая секретный ключ sk и зашифрованного текста c, выбрать нечетный коэффициент V₁ от V (X), расшифровываем немного  
Все остальные детали ПГШ опущены (см. [6]).

В ПГШ [6], и u(х) является произвольно правильными многочленами генерирующих и р может быть 
составным числом. Кроме того, алгоритм расшифровки используется только операция по модулю 
над целыми числами.

 

4,2 Криптоанализ Джентри-Халеви ПГШ. 
По алгоритма дешифровки в [6], вектор зашифрованного текста будет с = (с, 0, ..., 0). Таким образом, 
С другой стороны, у нас есть 
, где является дробной частью, и   будет  малым вектором r и . Таким образом, . То есть, для любого дешифруемого зашифрованного с. 
Мы применим тот же метод в разделе 3, которая находит небольшой множитель w(х) = d (х) ´ V (X) 
секретного ключа v(х). Когда все элементы меньше, чем р / 2, мы можем 
восстановить бит сообщение зашифрованного текста С следующим образом: b = 1, если 
иначе b= 0. Таким образом, мы находит W (X) = d (х) ´ v(х) на [х] 
по теореме 3.1.. 
При n = 2048, к = 16 и h = 380, мы можем восстановить бит сообщение зашифрованного текста 
способом выше .Кроме того, мы также можем восстановить бит сообщениz шифротекста для 
N = 8196, h = 380 по теореме 2.3.

 

Пример 4.1 Пусть n = 4,  
Мы оцениваем a = 836836133, , 
. Это не трудно проверить, что атака выше работает. ■

 

 
5. Восстановление  читаемого текста от зашифрованного текста. 
Учитывая публичный ключ рк = (р, a) из ПГШ [3, 6] и читаемый  текст  бит м Î {0,1}, шифрование 
алгоритма выдает зашифрованный текст .Новая решетка построена следующим образом.

 

Занятие LLL получает пониженной основой C такой B, что U = B ´ C. В силу теоремы 2.3, первый 
вектор С₁ из C выполняется где . 
Легко видеть, что . При n £ 8192,    и U₁₁ с вероятностью 1/2, 
cстранно, мы получим читаемый текст . В самом деле, другие строки также является возможным, если .Когда U₁₁ нечетное , мы можем создать другую решетку B с заменой с кс, напомним LLL, чтобы получить нижней основой C из B, проверим 
что не U₁₁нечетное, где к малое нечетное .

В целях реализации ПГШ, шифртекстов секретного битного ключа в [6] просто использоватьm = 1. Таким образом, можно использовать описанный выше метод, чтобы расшифровать эти шифртексты.

 

6. Заключение и нерешённые проблемы. 
Мы анализируем безопасность схемы в [3, 6]. В основном мы показали, что их схемы 
не являются безопасными для n £ 8192 в [3, 6], применяя решетку алгоритмf сокращения. Тем не менее, 
мы заметили, что   для блока решетки, со крашения алгоритма ,необходимо слишком много времени и пространства и большой размерности и больших чисел . Мы планируем дальнейшее совершенствование рассмотренной выше метод решеточной атаки , чтобы действительно ПГШ задачи в [6]. 
Еще один открытый вопрос состоит в построении новой ПГШ, скрывая главный идеал решетки, 
чтобы избежать рассмотренную выше атаку сокращения решетки.

 

 

 

 

 

 

 

Литература .

[1] R. Rivest, L. Adleman and M. Dertouzos, ”On data banks and privacy homomorphisms”, In Foundations of Secure Computation, pp. 169-180, (1978).

[2] C. Gentry, ”Fully homomorphic encryption using ideal lattices”, STOC 2009, pp. 169-178, (2009).

[3] N. P. Smart and F. Vercauteren, ”Fully homomorphic encryption with relatively small key and ciphertext sizes”, PKC 2010, LNCS 6056, pp. 420-443, (2010).

[4] M. van Dijk, C. Gentry, S. Halevi and V. Vaikuntanathan, ”Fully homomorphic encryption over the integers”, Eurocrypt 2010, LNCS 6110, pp. 24-43, (2010).

[5] D. Stehle and R. Steinfeld, ”Faster Fully Homomorphic Encryption”, Asiacrypt 2010, LNCS 6477, pp. 377- 394, (2010).

[6] C. Gentry and S. Halevi, ”Implementing Gentry’s fully-homomorphic encryption scheme”, EUROCRYPT 2011, LNCS 6632, pp. 129-148, (2011).

[7] N. Gama, N. Howgrave-Graham, H. Koy and P. Q. Nguyen, ”Rankin’s constant and blockwise lattice reduction”, CRYPTO 2006, pp. 112–130, (2006).

[8] P. Q. Nguyen and D. Stehle, ”LLL on the average”, ANTS VII, 2006, LNCS 4076, pp. 238-256, (2006).

[9] H. W. Lenstra Jr., A. K. Lenstra and L. Lov´asz, ”Factoring polynomials with rational coefficients”, Mathematische Annalen 261, pp. 515-534, (1982).

[10] C. P. Schnorr, ”A hierarchy of polynomial time lattice basis reduction algorithms”, Theoretical Computer Science, 53, pp. 201-224, (1987).

[11] Miklos Ajtai, R. Kumar and D.