Полностью гомоморфное шифрование — шифрование, позволяющее для данного шифротекста ,…, каждому человеку (не только держателю ключа) получить шифротекст любой желаемой функции f(,…,) до тех пор, пока данная функция может быть эффективно вычислена. Таким образом такое шифрование позволяет оператору делать механические операции с шифрами, исполнять необходимый алгоритм, без получения самим оператором доступа к зашифрованной информации. Только пользователь зашифровавший свои данные может расшифровать результат вычисления. Кроме-того это обеспечивает мощную функциональность для таких сценариев использования, как облачные вычисления и аналитика больших данных, где требуется обработка больших объемов данных, но конфиденциальная или проприетарная информация должна быть закрыта от третьих лиц.
История Впервые идея полностью гомоморфного шифрования была предложена в 1978 году изобретателями криптографического алгоритма с открытым ключом RSA Рональдом Ривестом и Ади Шамиром совместно с Майклом Дертузосом.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 Однако на начальных этапах попытки создания криптосистемы с таким шифрованием были неудачны. Многие годы было непонятно, возможно ли вообще полностью гомоморфное шифрование, хотя попытки создания такой системы предпринимались неоднократно. Так, например, криптосистема, предложенная в 1982 году Шафи Гольдвассер и Сильвио Микали, имела достаточно высокий уровень криптостойкости, но была лишь частично гомоморфной (гомоморфной только по сложению) и могла зашифровать только один бит.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 Еще одна аддитивно гомоморфная система шифрования была предложена в 1999 году Паскалем Пэйе.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 Прорыв в развитии полностью гомоморфного шифрования приходится на 2009 год, когда Крейг Гентри впервые предложил вариант полностью гомоморфной криптосистемы, основанной на криптографии на решетках.C. Gentry A Fully Homomorphic Encryption Scheme. PhD thesis, Stanford University, 2009. 199 p. URL: https://crypto.stanford.edu/craig/craig-thesis.pdf С тех пор появилось большое количество работ, в которых предлагается модификация криптосистемы Гентри с целью улучшения ее производительности.
Определение Полностью гомоморфное шифрование — криптографический примитив, представляющий собой функцию шифрования, удовлетворяющую дополнительному требованию гомоморфности относительно каких-либо операций над открытыми текстами. Функция шифрования , где m — открытый текст, k — ключ шифрования, гомоморфна относительно операции над открытыми текстами, если существует эффективный алгоритм , который, получив на вход любую пару криптограмм вида , выдает криптограмму такую, что при дешифровании будет получен открытый текст Варновский Н. П., Шокуров А. В. Гомоморфное шифрование. // Труды ИСП РАН . 2007. № 12. URL: http://cyberleninka.ru/article/n/gomomorfnoe-shifrovanie . Аналогично определяется гомоморфизм относительно операции .
В то время, как частично гомоморфные криптосистемы гомоморфны лишь относительно одной операции над открытым текстом (либо сложения, либо умножения), полностью гомоморфные системы поддерживают гомоморфизм относительно обеих операций (как сложения, так и умножения). То есть для них выполнены следующие условия:
Более того, гомоморфности по операциям сложения и умножения достаточно, чтобы система была полностью гомоморфной.Бабенко Л. К., Буртыка Ф. Б., Макаревич О. Б., Трепачева А. В. Защищенные вычисления и гомоморфное шифрование. // III Национальный суперкомпьютерный форум (25-27 ноября 2014, г. Переславль-Залесский). ИПС имени А. К. Айламазяна РАН, 2014. URL: http://2014.nscf.ru/TesisAll/4_Systemnoe_i_promezhytochnoe_PO/01_141_ByrtikaFB.pdf
Ранние полностью гомоморфные системы
Криптосистема Гентри
Криптосистема, созданная , основанная на криптографии на решетках, описывала первую возможную конструкцию для полностью гомоморфной системы. Схема Гентри поддерживала операции сложения и умножения над шифротекстом, что позволяет построить кольца для реализации любых произвольных вычислений.
Конструкция начинается с почти гомоморфной схемы шифрования, которая подходит только для вычисления полиномов малых степеней над зашифрованными данными. (Это ограничено тем, что шифротекст содержит некоторый шум, который растет при операциях сложения и умножения над шифротекстом до тех пор, пока шум не делает результат неразборчивым.) Гентри показал, как модифицировать схему и сделать её гибкой. То есть с помощью перешифрования он смог убрать накопившийся шум и провести над шифротекстом, по крайней мере, ещё одну операцию.
То есть схема позволяет оценивать её алгоритм дешифрирования для, по крайней мере, ещё одной операции. В конце концов, он показал: любая гибкая схема может быть конвертирована в полностью гомоморфную с помощью рекурсивного встраивания в себя саму.
Для «шумной» схемы Гентри процедура модификации схемы в «гибкую» эффективно «обновляет» шифротекст, применяя к нему гомоморфную процедуру дешифрирования, таким образом получая новый текст, который шифрует те же данные, что и раньше, но с меньшим уровнем шума. Периодически при достижении высокого уровня шума «обновляя» шифротекст, возможно производить над ним произвольное число операций без помех. Защищенность своей схемы Гентри обосновал двумя проблемами: проблемой сложности худшего случая и задачей о сумме подмножеств.
В докторской работе Гентри имеется более детально описание.
Несмотря на свою производительность, шифротексты в схеме Гентри остаются компактными, так как их длины не зависят от сложности функции, которая рассчитывается для зашифрованных данных. Однако схема остаётся непрактичной из-за значительного увеличения размера шифротекста и затрат на вычисление в зависимости от уровня защиты. Дамьен Шехли и Рон Штейнфелд представили ряд оптимизаций и улучшений, и впоследствии с Фредериком Веркаутереном, и c , представили первые рабочие реализации полностью гомоморфной схемы шифрования Гентри.
Криптосистема на целых числах В 2010 году Мартин ван Дейк, , и Видон Вайкунтанахан представили вторую полностью гомоморфную систему , которая использовала много принципов криптосистемы Гентри, но не требовала . Вместо этого они показали: можно заменить гомоморфный компонент на идеальных решётках на простую гомоморфную схему, которая использовала бы целые числа. Эта схема является концептуально проще схемы Гентри, но обладает схожими параметрами в плане гомоморфности и эффективности.
Гомоморфный компонент в работе Дейка схож со схемой шифрования, представленной Левьелом и Наккахой в 2008 , а также похож на тот, что был представлен Брамом Кохеном в 1998. Но метод Кохена не является гомоморфным относительно операции сложения. Схема Левьелы-Наккахи поддерживает только операцию сложения и может быть модифицирована для поддержки малого числа операций перемножения. Многие улучшения и оптимизации схем были представлены в ряде работ Джен-Себастиан Корона, Танкрида Лепойнта, Аврадипа Мандалы, и Мехди Тибухи .
Второе поколение гомоморфных криптосистем Несколько новых техник были разработаны начиная с 2011—2012 года Цвиком Бракерски, , Видоном Вайкунтанаханом и другими. Эти разработки привели к ряду более эффективных полностью гомоморфных криптосистем. В их числе: Криптосистема Бракерски-Гентри-Вайкунтанахана (BGV),Z. Brakerski, C. Gentry, and V. Vaikuntanathan. Fully Homomorphic Encryption without Bootstrapping . In ITCS 2012 построенная на технике Бракерски-Вайкунтанахана.Z. Brakerski and V. Vaikuntanathan. Efficient Fully Homomorphic Encryption from (Standard) LWE . In FOCS 2011 (IEEE) Криптосистема Бракерски.Z. Brakerski. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP . In CRYPTO 2012 (Springer) Криптосистема на NTRU созданная Лопез-Альтом,Тромером и Вайкунтанаханом (LTV).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) Криптосистема Гентри-Сахай-Вотерс (GSW).C. Gentry, A. Sahai, and B. Waters. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based . In CRYPTO 2013 (Springer)
Защищенность большинства схем основана на сложности решения проблемы обучения с ошибками. Только у LVT схемы защита реализована на варианте вычислительной NTRU задачи. У всех этих систем в отличие от ранних схем более медленное нарастание шума в процессе гомоморфных вычислений. В результате дополнительной оптимизации, сделанной , и , была получена криптосистема с практически оптимальной асимптотической сложностью: сложность вычисления операций над зашифрованными данными с параметром защиты имеет сложность вычисления лишь .C. Gentry, S. Halevi, and N. P. Smart. Fully Homomorphic Encryption with Polylog Overhead . In EUROCRYPT 2012 (Springer)C. Gentry, S. Halevi, and N. P. Smart. Better Bootstrapping in Fully Homomorphic Encryption . In PKC 2012 (SpringeR)C. Gentry, S. Halevi, and N. P. Smart. Homomorphic Evaluation of the AES Circuit . In CRYPTO 2012 (Springer) Эти оптимизации построены на технике Смарта-Веркаутерена, которая позволяет сжимать набор текстовых переменных в один шифротекст и работать над данными переменными одним потоком. Многие достижения из второго поколения полностью гомоморфных систем также были использованы в криптосистеме на целых числах.
Цвика Бракерски и Видон Вайкунтанахан заметили, что для ряда схем криптосистема GSW показывает слабый рост уровня шума, и, следовательно, большую эффективность, и большую защищенность.Z. Brakerski and V. Vaikuntanathan. Lattice-Based FHE as Secure as PKE . In ITCS 2014 Якоб Алперин-Шерифф и Крис Пейкерт позднее описали эффективную технику преобразования шифротекста в гибкий, которая как раз и использует такой тип схем.J. Alperin-Sheriff and C. Peikert. Faster Bootstrapping with Polynomial Error . In CRYPTO 2014 (Springer) Но этот тип преобразования не совместим с методами сжатия шифротекста, и, таким образом, оптимизации Гентри-Сахай-Вотерс не могут быть применены к ней.
Все криптосистемы второго поколения до сих пор следуют основам конструкции схемы Гентри, а именно используют почти гомоморфную криптосистему с большим уровнем роста шума и далее преобразуют её к полностью гомоморфной криптосистеме с помощью модификации в гибкую схему.
Реализации Первой реализацией полностью гомоморфного шифрования была схема Гентри-Халеви, реализованная на основе вышеуказанной схемы Гентри. На простую битовую операцию ей требовалось 30 минут. После появления второго поколения криптосистем, эта реализация устарела.
В литературе имеется много реализаций почти гомоморфных систем второго поколения. Реализованная Гентри, Хавели и Смартом (GHS) вариация BGV криптосистемы показала результат в 36 часов при расчете сложной схемы, реализующей AES шифрование. Используя техники сжатия шифротекста, эта реализация могла пересчитать эту же схему на 54 разных входах за те же 36 часов, таким образом получив результат в 40 минут на один вход. Расчет AES схемы был выбран как ориентир для нескольких последующих работ,Y. Doroz, Y. Hu, and B. Sunar. Homomorphic AES Evaluation using NTRU . In Financial Cryptography 2014 где удалось заметно снизить время расчета до 4 часов при затрате 7-ми секунд на один вход.
Две реализации второго поколения криптосистем доступны для общественного пользования: Библиотека HElib, сделанная и Виктор Шоуп, которая реализует криптосистему BGV с GHS оптимизацией