Полностью гомоморфное шифрование

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Полностью гомоморфное шифрование — шифрование, позволяющее для данного шифротекста π1,…,πt любому (не только держателю ключа) получить шифротекст любой желаемой функции f(π1,…,πt), до тех пор, пока данная функция может быть эффективно вычислена.

История[править | править код]

Впервые идея полностью гомоморфного шифрования была предложена в 1978 году изобретателями криптографического алгоритма с открытым ключом RSA Рональдом Ривестом и Ади Шамиром совместно с Майклом Дертузосом.[1] Однако на начальных этапах попытки создания криптосистемы с таким шифрованием были неудачны. Многие годы было непонятно, возможно ли вообще полностью гомоморфное шифрование, хотя попытки создания такой системы предпринимались неоднократно. Так, например, криптосистема, предложенная в 1982 году Шафи Гольдвассером и Сильвио Микали, имела достаточно высокий уровень криптостойкости, но была лишь частично гомоморфной (гомоморфной только по сложению), и могла зашифровать только один бит.[2] Еще одна аддитивно гомоморфная система шифрования была предложена в 1999 году Паскалем Пэйе.[3] Прорыв в развитии полностью гомоморфного шифрования приходится на 2009 год, когда Крейг Гентри впервые предложил вариант полностью гомоморфной криптосистемы, основанной на криптографии на решетках.[4] С тех пор появилось большое количество работ, в которых предлагается модификация криптосистемы Гентри с целью улучшения ее производительности.

Определение[править | править код]

Полностью гомоморфное шифрование — криптографический примитив, представляющий собой функцию шифрования, удовлетворяющую дополнительному требованию гомоморфности относительно каких-либо операций над открытыми текстами. Функция шифрования , где m — открытый текст, k — ключ шифрования, гомоморфна относительно операции над открытыми текстами, если существует эффективный алгоритм , который получив на вход любую пару криптограмм вида , выдает криптограмму такую, что при дешифровании будет получен открытый текст [5]. Аналогично определяется гомоморфизм относительно операции .

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

Более того, гомоморфности по операциям сложения и умножения достаточно, чтобы система была полностью гомоморфной.[6]

Ранние полностью гомоморфные системы[править | править код]

Криптосистема Гентри[править | править код]

Основная статья: Криптосистема Джентри

Криптосистема созданная Крейгом Гентри[en] основанная на криптографии на решетках описывала первую возможную конструкцию для полностью гомоморфной системы. Схема Гентри поддерживала операции сложения и умножения над шифротекстом, что позволяет построить кольца для реализации любых произвольных вычислений.

Конструкция начинается с почти гомоморфной схемы шифрования, которая подходит только для вычисления полиномов малых степеней над зашифрованными данными. (Это ограничено тем, что шифротекст содержит некоторый шум, который растет при операциях сложения и умножения над шифротекстом, до тех пор пока шум не делает результат неразборчивым.) Гентри показал как модифицировать схему и сделать её гибкой. То есть С помощью перешифрования он смог убрать накопившийся шум и провести над шифротекстом по крайней мере ещё одну операцию.

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

Для «шумной» схемы Гентри, процедура модификации схемы в «гибкую» эффективно «обновляет» шифротекст, применяя к нему гомоморфную процедуру дешифрирования, таким образом получая новый текст, который шифрует те же данные что и раньше, но с меньшим уровнем шума. «Обновляя» шифротекст периодически, при достижении высокого уровня шума, возможно производить над ним произвольное число операций без помех. Защищенность своей схемы Гентри обосновал двумя проблемами: проблемой сложности худшего случая криптографии на идеальных решетках[en] и задачей о сумме подмножеств.

В докторской работе Гентри[7] имеется более детально описание.

Несмотря на свою производительность, шифротексты в схеме Гентри остаются компактными, так как их длины не зависят от сложности функции, которая рассчитывается для зашифрованных данных. Но схема непрактична из-за резкого роста размера шифротекста и затрат на вычисление в зависимости от уровня защиты. Дамьен Шехли и Рон Штейнфелд представили ряд оптимизаций и улучшений,[8] и впоследствии Найджел Смарт[en] с Фредериком Веркаутереном,[9][10] и Крейг Гентри[en] c Шайем Халеви[en],[11][12] представили первые рабочие реализации полностью гомоморфной схемы шифрования Гентри.

Криптосистема на целых числах[править | править код]

В 2010 году Мартин ван Дейк, Крейг Гентри[en], Шай Халеви[en] and Видон Вайкунтанахан представили вторую полностью гомоморфную систему[13]. Она использовала много принципов криптосистемы Гентри, но не требовала идеальных решёток[en]. Вместо этого, они показали что можно заменить гомоморфный компонент на идеальных решётках на простую гомоморфную схему, которая использовала бы целые числа. Эта схема является концептуально проще схемы Гентри, но обладает схожими параметрами в плане гомоморфности и эффективности.

Гомоморфный компонент в работе Дейка схож со схемой шифрования представленной Левьелом и Наккахой в 2008[14], а так же похож на тот, что был предствлен Брамом Кохеном в 1998[15]. Но метод Кохена не является гомоморфным относительно операции сложения. Схема Левьелы-Наккахи поддерживает только операцию сложения и может быть модифицирована для поддержки малого числа операций перемножения. Многие улучшения и оптимизации схем были представлены в ряде работ Джен-Себастиан Корона, Танкрида Лепойнта, Аврадипа Мандалы, Дэвида Наккхи[en] и Мехди Тибухи[16][17][18][19].

Второе поколение гомоморфных криптосистем[править | править код]

Несколько новых техник были разработаны начиная с 2011—2012 года Цвиком Бракерски, Крейгом Гентри[en], Видоном Вайкунтанаханом и другими. Эти разработки привели к ряду более эффективных полностью гомоморфных криптосистем. В их числе:

  • Криптосистема Бракерски-Гентри-Вайкунтанахана (BGV),[20] построенная на технике Бракерски-Вайкунтанахана.[21]
  • Криптосистема Бракерски.[22]
  • Криптосистема на NTRU созданная Лопез-Альтом,Тромером и Вайкунтанаханом (LTV).[23]
  • Криптосистема Гентри-Сахай-Вотерс (GSW).[24]

Защищенность большинства схем основана на сложности решения проблемы обучения с ошибками. Только у LVT схемы защита реализована на варианте вычислительной NTRU задачи. У всех этих систем в отличие от ранних схем более медленное нарастание шума в процессе гомоморфных вычислений. В результате дополнительной оптимизации сделанной Крейгом Гентри[en], Шаем Хавели[en] и Найджелом Смартом[en] , была получена криптосистема с практически оптимальной асимптотической сложностью: Сложность вычисления операций над зашифрованными данными с параметром защиты имеет сложность вычисления лишь .[25][26][27] Эти оптимизации построены на технике Смарта-Веркаутерена, которая позволяет сжимать набор текстовых переменных в один шифротекст и работать над данными переменными одним потоком.[10] Многие достижения из второго поколения полностью гомоморфных систем так же были использованы в криптосистеме на целых числах.[18][19]

Цвика Бракерски и Видон Вайкунтанахан заметили, что для ряда схем, криптосистема GSW показывает слабый рост уровня шума, и следовательно большую эффективность и большую защищенность.[28] Якоб Алперин-Шерифф и Крис Пейкерт позднее описали эффективную технику преобразования шифротекста в гибкий, которая как раз и использует такой тип схем.[29] Но такой тип преобразования, к сожалению, не совместим с методами сжатия шифротекста, и таким образом оптимизации Гентри-Сахай-Вотерс не могут быть применены к ней[25].

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

Реализации[править | править код]

Первой реализацией полностью гомоморфного шифрования была схема Гентри-Халеви реализованная на основе вышеуказанной схемы Гентри.[12] На простую битовую операцию ей требовалось 30 минут. После появления второго поколения криптосистем, эта реализация устарела.

В литературе имеется много реализаций почти гомоморфных система второго поколения. Реализованная Гентри, Хавели и Смартом (GHS)[27] вариация BGV криптосистемы,[20] показала результат в 36 часов при расчете сложной схемы (реализующей AES шифрование). Используя техники сжатия шифротекста, эта реализация могла пересчитать эту же схему на 54 разных входах за те же 36 часов, таким образом получив результат в 40 минут на один вход. Расчет AES схемы был выбран как ориентир для нескольких последующих работ,[18][30][31] где удалось заметно снизить время расчета до 4 часов, при затрате 7-ми секунд на один вход.

Две реализации второго поколения криптосистем доступны для общественного пользования:

Обе библиотеки являются реализациями полностью гомоморфного шифрования. HElib показывает результат в 5-10 минут для преобразования сжатого шифротекста с порядка 1000 знаков, в гибкий.[34] FHEW преобразует несжатый шифротекст в гибкий за порядка 1/2 секунды на один бит.[35] В конце 2014 обновленная реализация HElib показала результат в 4 минуты для расчета AES схемы для 120 входных потоков, достигнув тем самым удельной скорости в 2 секунды на один поток.[32]

Полностью гомоморфное шифрование в кольце двоичных чисел[править | править код]

Схема полностью гомоморфного шифрования, которую предложил Гентри, может быть рассмотрена на примере вычислений в .[36]

Шифрование[править | править код]

Процесс шифрования данных можно представить следующим образом:

1. Выбирается произвольное нечетное число , являющееся секретным параметром. Пусть .

2. Составляется число такое, что , где — произвольное число. Это значит, что .

3. В процессе шифрования всякому ставится в соответствие число , где выбирается произвольно. Таким образом, . Легко видеть, что , и, значит, злоумышленник сможет определить только четность выхода шифрования.

Расшифрование[править | править код]

Пусть известны зашифрованное число и секрет . Тогда процесс расшифрования данных должен содержать следующие действия:

1.Расшифрование с использованием секретного параметра : , где называется шумом и .

2.Получение исходного зашифрованного бита:

Обоснование[править | править код]

Пусть есть два бита и им в соответствие поставлена пара чисел и . Пусть взят секретный параметр и произведено шифрование данных: и .

Вычисляется сумма этих чисел:

Для суммы этих чисел расшифрованным сообщением будет сумма исходных бит .

Но не зная , расшифровать данные не представляется возможным: .

Аналогично проверяется операция умножения:

К полученным результатам необходимо применить процедуру расшифрования, в результате чего получится следующее:

.

Недостатки[править | править код]

Использование данной полностью гомоморфной схемы шифрования в практических целях на данный момент не представляется возможным, так как в результате производимых вычислений накапливаемая ошибка быстро достигает достаточно больших значений[36]. Возможна даже ситуация, при которой правильно расшифровать данные не удастся вовсе. Это произойдет в случае, если значение ошибки превысит значение . В попытках избежать столкновения с такой проблемой Гентри был разработан механизм самокоррекции шифротекстов (англ. bootstrapping), который в силу своей непрактичности из - за слишком быстрого роста объема шифротекста, не нашел широкого применения. Решить данную проблему возможно, но для достижения поставленной задачи необходимо разработать более сложные алгоритмы вычислений, либо ограничить количество операций над данными.[36]

Применение полностью гомоморфного шифрования[править | править код]

Облачные вычисления[править | править код]

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

Пусть, например, пользователь зашифровал некоторые свои данные и хранит их на удаленном облачном хранилище. В случае, если пользователь намерен каким то образом изменить эти данные, он может либо доверить серверу свой секретный ключ, а, следовательно, и доступ ко всей своей секретной информации, либо скачать зашифрованные данные на свой компьютер, расшифровать, произвести необходимые вычисления и отправить обратно на сервер. Но ни тот, ни другой способ не являются оптимальными. В первом случае нельзя исключить вероятную утечку данных и их попадание к третьим лицам, во втором случае временные затраты на произведение всех необходимых операций могут быть слишком велики. К тому же клиент может попросту не располагать необходимыми вычислительными ресурсами для произведения нужных ему вычислений.[37]

Также по данным международной исследовательской компании IDC, занимающейся изучением мирового рынка информационных технологий и телекоммуникаций, многие компании с недоверием относятся к облачным технологиям, связывая с ними, в первую очередь, большие проблемы по части безопасности хранимых данных. А независимая исследовательская компания Portio Research опубликовала данные, согласно которым 68% руководителей различных европейских IT - компаний не доверяют подобным сервисам. Так, например, руководитель компании G Data Security Labs Ральф Бенцмюллер высказался об облачных сервисах следующим образом: «Если вы не хотите, чтобы ваши данные стали достоянием общественности, не храните их в облачных хранилищах». Поэтому вопрос создания защищенного облачного хранилища с использованием полностью гомоморфной схемы шифрования данных в настоящее время стоит довольно остро..[38].

Прочее[править | править код]

Полностью гомоморфное шифрование используется в поисковых системах, в которых требуется осуществление "приватного поиска", то есть такого поиска, при котором сервер ничего не знает о содержании поискового запроса и возвращает пользователю результат в зашифрованном виде. Помимо уже рассмотренных областей, схемы полностью гомоморфного шифрования могут применяться в системах электронного голосования, например, при использовании подписи вслепую.[6]

Ссылки[править | править код]

  1. R. Rivest, L. Adleman, M. Dertouzos On data banks and privacy homomorphisms. // Foundations of secure computation. 1978. vol.32. no. 4. pp. 169–178. URL: http://luca-giuzzi.unibs.it/corsi/Support/papers-cryptography/RAD78.pdf
  2. S. Goldwasser, S. Micali Probabilistic encryption // Journal of Computer and System Sciences. 1984. vol. 28. no. 2. pp. 270–299. URL: http://groups.csail.mit.edu/cis/pubs/shafi/1984-jcss.pdf
  3. P. Paillier Public-key cryptosystems based on composite degree residuosity classes // Advances in Cryptology - EUROCRYPT’99. 1999. ser. Lecture Notes in Computer Science. vol. 1592. pp. 223-238. URL: https://link.springer.com/chapter/10.1007%2F3-540-48910-X_16
  4. C. Gentry A Fully Homomorphic Encryption Scheme. PhD thesis, Stanford University, 2009. 199 p. URL: https://crypto.stanford.edu/craig/craig-thesis.pdf
  5. Варновский Н.П., Шокуров А.В. Гомоморфное шифрование. // Труды ИСП РАН . 2007. № 12. URL: http://cyberleninka.ru/article/n/gomomorfnoe-shifrovanie
  6. 1 2 3 Бабенко Л.К., Буртыка Ф.Б., Макаревич О.Б., Трепачева А.В. Защищенные вычисления и гомоморфное шифрование. // III Национальный суперкомпьютерный форум (25-27 ноября 2014, г.Переславль-Залесский). ИПС имени А.К. Айламазяна РАН, 2014. URL: http://2014.nscf.ru/TesisAll/4_Systemnoe_i_promezhytochnoe_PO/01_141_ByrtikaFB.pdf
  7. Craig Gentry. A Fully Homomorphic Encryption Scheme (Ph.D. thesis) (PDF).
  8. Stehlé D., Steinfeld R. Faster Fully Homomorphic Encryption (англ.) // Advances in Cryptology — ASIACRYPT 2010: 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 5-9, 2010. Proceedings / M. AbeSpringer Science+Business Media, 2010. — P. 377—394. — 634 p. — (Lecture Notes in Computer Science; Vol. 6477) — ISBN 978-3-642-17372-1 — ISSN 0302-9743doi:10.1007/978-3-642-17373-8_22
  9. Smart N., Vercauteren F. Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes (англ.) // Public Key Cryptography — PKC 2010: 13th International Conference on Practice and Theory in Public Key Cryptography, Paris, France, May 26-28, 2010, Proceedings / P. Q. Nguyen, D. PointchevalSpringer Science+Business Media, 2010. — P. 420—443. — 519 p. — (Lecture Notes in Computer Science; Vol. 6056) — ISBN 978-3-642-13012-0 — ISSN 0302-9743doi:10.1007/978-3-642-13013-7_25
  10. 1 2 Smart N., Vercauteren F. Fully homomorphic SIMD operations (англ.) // Des. Codes Cryptogr.Springer US, 2014. — Vol. 71, Iss. 1. — P. 57–81. — ISSN 0925-1022doi:10.1007/S10623-012-9720-4
  11. Gentry C., Halevi S. Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits (англ.) // Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium onIEEE, 2011. — P. 107–109. — ISBN 978-1-4577-1843-4, 978-0-7695-4571-4 — ISSN 0272-5428doi:10.1109/FOCS.2011.94
  12. 1 2 Gentry C., Halevi S. Implementing Gentry’s Fully-Homomorphic Encryption Scheme (англ.) // Advances in Cryptology — EUROCRYPT 2011: 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, May 15-19, 2011, Proceedings / K. G. PatersonSpringer Science+Business Media, 2011. — P. 129—148. — 628 p. — ISBN 978-3-642-20464-7doi:10.1007/978-3-642-20465-4_9
  13. Dijk M. v., Gentry C., Halevi S., Vaikuntanathan V. Fully Homomorphic Encryption over the Integers (англ.) // Advances in Cryptology – EUROCRYPT 2010: 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30 – June 3, 2010. Proceedings / H. GilbertBerlin: Springer Berlin Heidelberg, 2010. — P. 24—43. — 20 p. — ISBN 978-3-642-13189-9, 978-3-642-13190-5 — doi:10.1007/978-3-642-13190-5_2
  14. Levieil E., Naccache D. Cryptographic Test Correction (англ.) // Public Key Cryptography – PKC 2008: 11th International Workshop on Practice and Theory in Public-Key Cryptography, Barcelona, Spain, March 9-12, 2008, Proceedings / R. CramerSpringer Science+Business Media, 2008. — P. 85—100. — 402 p. — (Lecture Notes in Computer Science; Vol. 4939) — ISBN 978-3-540-78439-5 — ISSN 0302-9743doi:10.1007/978-3-540-78440-1_6
  15. Bram Cohen. Simple Public Key Encryption. Архивировано 7 октября 2011 года.
  16. Coron J., Naccache D., Tibouchi M. Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers (англ.) // Advances in Cryptology — EUROCRYPT 2012: 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012, Proceedings / D. Pointcheval, T. JohanssonSpringer Science+Business Media, 2012. — P. 446—464. — 758 p. — ISBN 978-3-642-29010-7doi:10.1007/978-3-642-29011-4_27
  17. Coron J., Mandal A., Naccache D., Tibouchi M. Fully Homomorphic Encryption over the Integers with Shorter Public Keys (англ.) // Advances in Cryptology — CRYPTO 2011: 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011, Proceedings / P. RogawaySpringer Science+Business Media, 2011. — P. 487—504. — 782 p. — ISBN 978-3-642-22791-2doi:10.1007/978-3-642-22792-9_28
  18. 1 2 3 Jung-hee C., Coron J., Kim J., Lee M. S., Lepoint T., Tibouchi M., Yun A. Batch Fully Homomorphic Encryption over the Integers (англ.) // Advances in Cryptology – EUROCRYPT 2013: 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings / T. Johansson, P. Q. NguyenSpringer Berlin Heidelberg, 2013. — P. 315—335. — 736 p. — ISBN 978-3-642-38347-2doi:10.1007/978-3-642-38348-9
  19. 1 2 Coron J., Lepoint T., Tibouchi M. Scale-Invariant Fully Homomorphic Encryption over the Integers (англ.) // Public-Key Cryptography — PKC 2014: 17th International Conference on Practice and Theory in Public-Key Cryptography, Buenos Aires, Argentina, March 26-28, 2014, Proceedings / H. KrawczykSpringer Science+Business Media, 2014. — P. 311—328. — 686 p. — ISBN 978-3-642-54630-3doi:10.1007/978-3-642-54631-0_18
  20. 1 2 Z. Brakerski, C. Gentry, and V. Vaikuntanathan. Fully Homomorphic Encryption without Bootstrapping. In ITCS 2012
  21. Z. Brakerski and V. Vaikuntanathan. Efficient Fully Homomorphic Encryption from (Standard) LWE. In FOCS 2011 (IEEE)
  22. Z. Brakerski. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. In CRYPTO 2012 (Springer)
  23. A. Lopez-Alt, E. Tromer, and V. Vaikuntanathan. On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption. In STOC 2012 (ACM)
  24. C. Gentry, A. Sahai, and B. Waters. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In CRYPTO 2013 (Springer)
  25. 1 2 C. Gentry, S. Halevi, and N. P. Smart. Fully Homomorphic Encryption with Polylog Overhead. In EUROCRYPT 2012 (Springer)
  26. C. Gentry, S. Halevi, and N. P. Smart. Better Bootstrapping in Fully Homomorphic Encryption. In PKC 2012 (SpringeR)
  27. 1 2 C. Gentry, S. Halevi, and N. P. Smart. Homomorphic Evaluation of the AES Circuit. In CRYPTO 2012 (Springer)
  28. Z. Brakerski and V. Vaikuntanathan. Lattice-Based FHE as Secure as PKE. In ITCS 2014
  29. 1 2 J. Alperin-Sheriff and C. Peikert. Faster Bootstrapping with Polynomial Error. In CRYPTO 2014 (Springer)
  30. Y. Doroz, Y. Hu, and B. Sunar. Homomorphic AES Evaluation using NTRU. In Financial Cryptography 2014
  31. Wei Dai. Accelerating NTRU based Homomorphic Encryption using GPUs.
  32. 1 2 Shai Halevi. HElib: An Implementation of homomorphic encryption. Дата обращения 31 декабря 2014.
  33. Leo Ducas. FHEW: A Fully Homomorphic Encryption library. Дата обращения 31 декабря 2014.
  34. Bootstrapping for HElib. Cryptology ePrint archive. Дата обращения 2 января 2015.
  35. FHE Bootstrapping in less than a second. Cryptology ePrint archive. Дата обращения 2 января 2015.
  36. 1 2 3 А.О. Жиров, О.В. Жирова, С.Ф. Кренделев "Безопасные облачные вычисления с помощью гомоморфной криптографии", http://bit.mephi.ru/wp-content/uploads/2013/2013_1/part_1.pdf Архивная копия от 10 ноября 2016 на Wayback Machine
  37. Бабенко Л.К., Буртыка Ф.Б., Макаревич О.Б., Трепачева А.В. Защищенные вычисления и гомоморфное шифрование. // III Национальный суперкомпьютерный форум (25-27 ноября 2014, г.Переславль-Залесский). ИПС имени А.К. Айламазяна РАН, 2014. URL: http://2014.nscf.ru/TesisAll/4_Systemnoe_i_promezhytochnoe_PO/01_141_ByrtikaFB.pdf
  38. Масштабные утечки данных: конец «облачным» сервисам? // Chip : журнал. — 2011. — № 8 (149). — С. 20—21. — ISSN 1609-4212