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

{{плохое оформление|дата=2021-06-29}}
{{короткая преамбула|дата=2021-06-29}}
'''Полностью гомоморфное шифрование''' — шифрование, позволяющее для данного [[шифротекст]]а ''{{math|π}}{{sub|1}},…,{{math|π}}{{sub|t}}'' каждому человеку (не только держателю ключа) получить шифротекст любой желаемой функции ''f({{math|π}}{{sub|1}},…,{{math|π}}{{sub|t}})'' до тех пор, пока данная функция может быть эффективно вычислена.

== История ==
Впервые идея полностью гомоморфного шифрования была предложена в 1978 году изобретателями криптографического алгоритма с открытым ключом [[RSA]] [[Ривест, Рональд Линн|Рональдом Ривестом]] и [[Шамир, Ади|Ади Шамиром]] совместно с [[Дертузос, Михалис|Майклом Дертузосом]].<ref>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 {{Wayback|url=http://luca-giuzzi.unibs.it/corsi/Support/papers-cryptography/RAD78.pdf |date=20160604140154 }}</ref> Однако на начальных этапах попытки создания криптосистемы с таким шифрованием были неудачны. Многие годы было непонятно, возможно ли вообще полностью гомоморфное шифрование, хотя попытки создания такой системы предпринимались неоднократно.
Так, например, криптосистема, предложенная в 1982 году [[Шафи Гольдвассер]] и [[Сильвио Микали]], имела достаточно высокий уровень криптостойкости, но была лишь частично гомоморфной (гомоморфной только по сложению) и могла зашифровать только один бит.<ref>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 {{Wayback|url=http://groups.csail.mit.edu/cis/pubs/shafi/1984-jcss.pdf |date=20160328011754 }}</ref> Еще одна аддитивно гомоморфная система шифрования была предложена в 1999 году [[Паскаль Пайе|Паскалем Пэйе]].<ref>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 {{Wayback|url=https://link.springer.com/chapter/10.1007%2F3-540-48910-X_16 |date=20170209082503 }}</ref> Прорыв в развитии полностью гомоморфного шифрования приходится на 2009 год, когда [[Крейг Гентри]] впервые предложил вариант полностью гомоморфной криптосистемы, основанной на криптографии на решетках.<ref>C. Gentry A Fully Homomorphic Encryption Scheme. PhD thesis, Stanford University, 2009. 199 p. URL: https://crypto.stanford.edu/craig/craig-thesis.pdf {{Wayback|url=https://crypto.stanford.edu/craig/craig-thesis.pdf |date=20170205211838 }}</ref> С тех пор появилось большое количество работ, в которых предлагается модификация криптосистемы Гентри с целью улучшения ее производительности.

== Определение ==
'''Полностью гомоморфное шифрование''' — криптографический примитив, представляющий собой функцию шифрования, удовлетворяющую дополнительному требованию гомоморфности относительно каких-либо операций над открытыми текстами.
Функция шифрования <math>E(k,m)</math>, где m — открытый текст, k — ключ шифрования, гомоморфна относительно операции <math>*</math> над открытыми текстами, если существует эффективный алгоритм <math>M</math>, который, получив на вход любую пару криптограмм вида <math>E(k,m_1), E(k,m_2)</math>, выдает криптограмму <math>c</math> такую, что при дешифровании <math>c</math> будет получен открытый текст <math>m_1*m_2</math><ref>Варновский Н. П., Шокуров А. В. Гомоморфное шифрование. // Труды ИСП РАН . 2007. № 12. URL: http://cyberleninka.ru/article/n/gomomorfnoe-shifrovanie {{Wayback|url=http://cyberleninka.ru/article/n/gomomorfnoe-shifrovanie |date=20161109084040 }}</ref>. Аналогично определяется гомоморфизм относительно операции <math>+</math>.

В то время, как частично гомоморфные криптосистемы гомоморфны лишь относительно одной операции над открытым текстом (либо сложения, либо умножения), полностью гомоморфные системы поддерживают гомоморфизм относительно обеих операций (как сложения, так и умножения)<ref name=autogenerated1 />. То есть для них выполнены следующие условия:
<math>\left\{\begin{matrix} Dec(Enc(m_1) \otimes Enc(m_2)) = m_1 * m_2 \\ Dec(Enc(m_1) \oplus Enc(m_2)) = m_1 + m_2\end{matrix}\right.</math>

Более того, гомоморфности по операциям сложения и умножения достаточно, чтобы система была полностью гомоморфной.<ref name=autogenerated1>Бабенко Л. К., Буртыка Ф. Б., Макаревич О. Б., Трепачева А. В. Защищенные вычисления и гомоморфное шифрование. // III Национальный суперкомпьютерный форум (25-27 ноября 2014, г. Переславль-Залесский). ИПС имени А. К. Айламазяна РАН, 2014. URL: http://2014.nscf.ru/TesisAll/4_Systemnoe_i_promezhytochnoe_PO/01_141_ByrtikaFB.pdf {{Wayback|url=http://2014.nscf.ru/TesisAll/4_Systemnoe_i_promezhytochnoe_PO/01_141_ByrtikaFB.pdf |date=20160411151422 }}</ref>

== Ранние полностью гомоморфные системы ==

=== Криптосистема Гентри ===
{{Main|Криптосистема Джентри}}

Криптосистема, созданная {{нп5|Крейг Гентри| Крейгом Гентри||Craig Gentry (computer scientist)}}, основанная на [[Криптография на решётках|криптографии на решетках]], описывала первую возможную конструкцию для полностью гомоморфной системы. Схема Гентри поддерживала операции сложения и умножения над шифротекстом, что позволяет построить кольца для реализации любых произвольных вычислений.

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

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

Для «шумной» схемы Гентри процедура модификации схемы в «гибкую» эффективно «обновляет» шифротекст, применяя к нему гомоморфную процедуру дешифрирования, таким образом получая новый текст, который шифрует те же данные, что и раньше, но с меньшим уровнем шума. Периодически при достижении высокого уровня шума «обновляя» шифротекст, возможно производить над ним произвольное число операций без помех.
Защищенность своей схемы Гентри обосновал двумя проблемами: проблемой сложности худшего случая {{нп5|Криптография на идеальных решётках|криптографии на идеальных решетках|en|Ideal lattice cryptography}} и [[Задача о сумме подмножеств|задачей о сумме подмножеств.]]

В докторской работе Гентри<ref>{{cite web
|title=A Fully Homomorphic Encryption Scheme (Ph.D. thesis)
|url=http://crypto.stanford.edu/craig/
|author=Craig Gentry
|format=PDF
|access-date=2015-11-17
|archive-date=2009-11-01
|archive-url=https://web.archive.org/web/20091101133048/http://crypto.stanford.edu/craig/
|deadlink=no
}}</ref>
имеется более детально описание.

Несмотря на свою производительность, шифротексты в схеме Гентри остаются компактными, так как их длины не зависят от сложности функции, которая рассчитывается для зашифрованных данных. Однако схема остаётся непрактичной из-за значительного увеличения размера шифротекста и затрат на вычисление в зависимости от уровня защиты. [[Дамьен Шехли]] и [[Рон Штейнфелд]] представили ряд оптимизаций и улучшений,<ref>{{source|Q28002556|ref=Stehlé, Steinfeld|ref-year=2010}} <!-- Faster Fully Homomorphic Encryption // Advances in Cryptology — ASIACRYPT 2010 --></ref> и впоследствии {{нп5|Найджел Смарт|Найджел Смарт||Nigel Smart (cryptographer)}} с [[Фредерик Веркаутерен|Фредериком Веркаутереном]],<ref>{{source|Q28002578|ref=Smart, Vercauteren|ref-year=2010}} <!-- Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes // Public Key Cryptography — PKC 2010 --></ref><ref name=SV11>{{source|Q28002584|ref=Smart, Vercauteren|ref-year=2014}} <!-- Fully homomorphic SIMD operations // Designs, Codes and Cryptography --></ref> и {{нп5|Крейг Гентри|Крейг Гентри||Craig Gentry (computer scientist)}} c {{нп5|Шай Халеви|Шайем Халеви||Shai Halevi}},<ref>{{source|Q28002612|ref=Gentry, Halevi|ref-year=2011}} <!-- Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits // Foundations of Computer Science — FOCS 2011 --></ref><ref name=GH11>{{source|Q28002629|ref=Gentry, Halevi|ref-year=2011}} <!-- Implementing Gentry’s Fully-Homomorphic Encryption Scheme // Advances in Cryptology — EUROCRYPT 2011 --></ref> представили первые рабочие реализации полностью гомоморфной схемы шифрования Гентри.

=== Криптосистема на целых числах ===
В 2010 году [[Мартин ван Дейк]], {{нп5|Крейг Гентри|Крейг Гентри||Craig Gentry (computer scientist)}}, {{нп5|Шай Халеви|Шай Халеви||Shai Halevi}} и [[Vinod Vaikuntanathan|Видон Вайкунтанахан]] представили вторую полностью гомоморфную систему<ref>{{source|Q28002636|ref=Dijk, Gentry, Halevi et al.|ref-year=2010}} <!-- Fully Homomorphic Encryption over the Integers // Advances in Cryptology — EUROCRYPT 2010 --></ref>.
Она использовала много принципов криптосистемы Гентри, но не требовала {{нп5|Криптография на идеальных решётках|идеальных решёток||Ideal lattice cryptography}}. Вместо этого они показали: можно заменить гомоморфный компонент на идеальных решётках на простую гомоморфную схему, которая использовала бы целые числа. Эта схема является концептуально проще схемы Гентри, но обладает схожими параметрами в плане гомоморфности и эффективности.

Гомоморфный компонент в работе Дейка схож со схемой шифрования, представленной Левьелом и Наккахой в 2008<ref>{{source|Q28002648|ref=Levieil, Naccache|ref-year=2008}} <!-- Cryptographic Test Correction // Public Key Cryptography — PKC 2008 --></ref>, а также похож на тот, что был представлен [[Bram Cohen|Брамом Кохеном]] в 1998<ref>
{{cite web
 |title       = Simple Public Key Encryption
 |url         = http://bramcohen.com/simple_public_key.html
 |author      = Bram Cohen
 |archiveurl  = https://web.archive.org/web/20111007060226/http://bramcohen.com/simple_public_key.html
 |archivedate = 2011-10-07
}}</ref>.
Но метод Кохена не является гомоморфным относительно операции сложения. Схема Левьелы-Наккахи поддерживает только операцию сложения и может быть модифицирована для поддержки малого числа операций перемножения. Многие улучшения и оптимизации схем были представлены в ряде работ [[Jean-Sébastien Coron|Джен-Себастиан Корона]], [[Tancrède Lepoint|Танкрида Лепойнта]], [[Avradip Mandal|Аврадипа Мандалы]], {{нп5|Дэвид Наккаха|Дэвида Наккхи||David Naccache}} и [[Mehdi Tibouchi|Мехди Тибухи]]<ref name=CNT12>{{source|Q28002956|ref=Coron, Naccache, Tibouchi|ref-year=2012}} <!-- Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers // Advances in Cryptology — EUROCRYPT 2012 --></ref><ref name=CMNT11>{{source|Q28002982|ref=Coron, Mandal, Naccache et al.|ref-year=2011}} <!-- Fully Homomorphic Encryption over the Integers with Shorter Public Keys // Advances in Cryptology — CRYPTO 2011 --></ref><ref name=CLT13>{{source|Q28003159|ref=Cheon, Coron, Kim et al.|ref-year=2013}} <!-- Batch Fully Homomorphic Encryption over the Integers // Advances in Cryptology — EUROCRYPT 2013 --></ref><ref name=CLT14>{{source|Q28003169|ref=Coron, Lepoint, Tibouchi|ref-year=2014}} <!-- Scale-Invariant Fully Homomorphic Encryption over the Integers // Public-Key Cryptography — PKC 2014 --></ref>.

== Второе поколение гомоморфных криптосистем ==
Несколько новых техник были разработаны начиная с 2011—2012 года [[Zvika Brakerski|Цвиком Бракерски]], {{нп5|Крейг Гентри| Крейгом Гентри||Craig Gentry (computer scientist)}}, [[Vinod Vaikuntanathan|Видоном Вайкунтанаханом]] и другими. Эти разработки привели к ряду более эффективных полностью гомоморфных криптосистем. В их числе:
* Криптосистема Бракерски-Гентри-Вайкунтанахана (BGV),<ref name=BGV12>Z. Brakerski, C. Gentry, and V. Vaikuntanathan. [http://eprint.iacr.org/2011/277 Fully Homomorphic Encryption without Bootstrapping] {{Wayback|url=http://eprint.iacr.org/2011/277 |date=20151117025426 }}. In ''ITCS 2012''</ref> построенная на технике Бракерски-Вайкунтанахана.<ref name=BV11b>Z. Brakerski and V. Vaikuntanathan. [http://eprint.iacr.org/2011/344 Efficient Fully Homomorphic Encryption from (Standard) LWE] {{Wayback|url=http://eprint.iacr.org/2011/344 |date=20151117014911 }}. In ''FOCS 2011'' (IEEE)</ref>
* Криптосистема Бракерски.<ref name=Bra12>Z. Brakerski. [http://eprint.iacr.org/2012/078 Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP] {{Wayback|url=http://eprint.iacr.org/2012/078 |date=20151117031125 }}. In ''CRYPTO 2012'' (Springer)</ref>
* Криптосистема на [[NTRUEncrypt|NTRU]] созданная Лопез-Альтом,Тромером и Вайкунтанаханом (LTV).<ref name=LTV12>A. Lopez-Alt, E. Tromer, and V. Vaikuntanathan. [https://eprint.iacr.org/2013/094 On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption] {{Wayback|url=https://eprint.iacr.org/2013/094 |date=20160303221039 }}. In ''STOC 2012'' (ACM)</ref>
* Криптосистема Гентри-Сахай-Вотерс (GSW).<ref name=GSW13>C. Gentry, A. Sahai, and B. Waters. [http://eprint.iacr.org/2013/340 Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based] {{Wayback|url=http://eprint.iacr.org/2013/340 |date=20151117024703 }}. In ''CRYPTO 2013'' (Springer)</ref>

Защищенность большинства схем основана на сложности решения проблемы [[Обучение с ошибками|обучения с ошибками]]. Только у LVT схемы защита реализована на варианте вычислительной [[NTRUEncrypt|NTRU]] задачи. У всех этих систем в отличие от ранних схем более медленное нарастание шума в процессе гомоморфных вычислений. В результате дополнительной оптимизации, сделанной {{нп5|Крейг Гентри| Крейгом Гентри||Craig Gentry (computer scientist)}}, {{нп5|Шай Хавели|Шаем Хавели||Shai Halevi}} и {{нп5|Найджел Смарт|Найджелом Смартом||Nigel Smart (cryptographer)}} , была получена криптосистема с практически оптимальной асимптотической сложностью: сложность вычисления <math>T</math> операций над зашифрованными данными с параметром защиты <math>k</math> имеет сложность вычисления лишь <math>T\cdot polylog(k)</math>.<ref name=GHS12a>C. Gentry, S. Halevi, and N. P. Smart. [http://eprint.iacr.org/2011/566 Fully Homomorphic Encryption with Polylog Overhead] {{Wayback|url=http://eprint.iacr.org/2011/566 |date=20150102221020 }}. In ''EUROCRYPT 2012'' (Springer)</ref><ref name=GHS12b>C. Gentry, S. Halevi, and N. P. Smart. [http://eprint.iacr.org/2011/680 Better Bootstrapping in Fully Homomorphic Encryption] {{Wayback|url=http://eprint.iacr.org/2011/680 |date=20150102221113 }}. In ''PKC 2012'' (SpringeR)</ref><ref name=GHS12c>C. Gentry, S. Halevi, and N. P. Smart. [http://eprint.iacr.org/2012/099 Homomorphic Evaluation of the AES Circuit] {{Wayback|url=http://eprint.iacr.org/2012/099 |date=20150102221841 }}. In ''CRYPTO 2012'' (Springer)</ref>
Эти оптимизации построены на технике Смарта-Веркаутерена, которая позволяет сжимать набор текстовых переменных в один шифротекст и работать над данными переменными [[SIMD|одним потоком]].<ref name=SV11/>
Многие достижения из второго поколения полностью гомоморфных систем также были использованы в криптосистеме на целых числах.<ref name=CLT13/><ref name=CLT14/>

[[Zvika Brakerski|Цвика Бракерски]] и [[Vinod Vaikuntanathan|Видон Вайкунтанахан]] заметили, что для ряда схем криптосистема GSW показывает слабый рост уровня шума, и, следовательно, большую эффективность, и большую защищенность.<ref>Z. Brakerski and V. Vaikuntanathan. [http://eprint.iacr.org/2013/541 Lattice-Based FHE as Secure as PKE] {{Wayback|url=http://eprint.iacr.org/2013/541 |date=20151119044321 }}. In ''ITCS 2014''</ref>
[[Якоб Алперин-Шерифф]] и [[Крис Пейкерт]] позднее описали эффективную технику преобразования шифротекста в гибкий, которая как раз и использует такой тип схем.<ref name=AP14>J. Alperin-Sheriff and C. Peikert. [http://eprint.iacr.org/2014/094 Faster Bootstrapping with Polynomial Error] {{Wayback|url=http://eprint.iacr.org/2014/094 |date=20151119045843 }}. In ''CRYPTO 2014'' (Springer)</ref>
Но этот тип преобразования не совместим с методами сжатия шифротекста, и, таким образом, оптимизации Гентри-Сахай-Вотерс не могут быть применены к ней<ref name=GHS12a/>.

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

=== Реализации ===
Первой реализацией полностью гомоморфного шифрования была схема Гентри-Халеви, реализованная на основе вышеуказанной схемы Гентри.<ref name=GH11/> На простую битовую операцию ей требовалось 30 минут. После появления второго поколения криптосистем, эта реализация устарела.

В литературе имеется много реализаций почти гомоморфных систем второго поколения. Реализованная Гентри, Хавели и Смартом (GHS)<ref name=GHS12c/> вариация BGV криптосистемы<ref name=BGV12/> показала результат в 36 часов при расчете сложной схемы, реализующей [[Advanced Encryption Standard|AES]] шифрование. Используя техники сжатия шифротекста, эта реализация могла пересчитать эту же схему на 54 разных входах за те же 36 часов, таким образом получив результат в 40 минут на один вход. Расчет AES схемы был выбран как ориентир для нескольких последующих работ,<ref name=CLT13/><ref>Y. Doroz, Y. Hu, and B. Sunar. [http://eprint.iacr.org/2014/039 Homomorphic AES Evaluation using NTRU] {{Wayback|url=http://eprint.iacr.org/2014/039 |date=20151119044322 }}. In ''Financial Cryptography 2014''</ref><ref>{{cite web|title=Accelerating NTRU based Homomorphic Encryption using GPUs|url=http://eprint.iacr.org/2014/389|author=Wei Dai|author2=Yarkin Doroz|author3=Berk Sunar|access-date=2015-11-18|archive-date=2015-11-19|archive-url=https://web.archive.org/web/20151119053133/http://eprint.iacr.org/2014/389|deadlink=no}}</ref> где удалось заметно снизить время расчета до 4 часов при затрате 7-ми секунд на один вход.

Две реализации второго поколения криптосистем доступны для общественного пользования:
* Библиотека HElib<ref name="HElib">{{cite web
|title=HElib: An Implementation of homomorphic encryption
|url=https://github.com/shaih/HElib
|author=Shai Halevi
|author2=Victor Shoup
|accessdate=2014-12-31
|archive-date=2016-05-21
|archive-url=https://web.archive.org/web/20160521142452/https://github.com/shaih/HElib
|deadlink=no
}}</ref>, сделанная {{нп5|Шай Хавели|Шаем Хавели||Shai Halevi}} и [[Виктор Шоуп]], которая реализует криптосистему BGV с GHS оптимизацией
* Библиотека FHEW<ref name="FHEW">{{cite web
|title=FHEW: A Fully Homomorphic Encryption library
|url=https://github.com/lducas/FHEW
|author=Leo Ducas
|author2=Daniele Micciancio
|accessdate=2014-12-31
|archive-date=2016-05-21
|archive-url=https://web.archive.org/web/20160521142723/https://github.com/lducas/FHEW
|deadlink=no
}}</ref>, сделанная [[Лео Дуглас]] и [[Даниэль Миккианакио]], которая является реализацией комбинации [[Обучение с ошибками|криптосистемы обучения с ошибками Регева]] и техники создания гибкой схемы Алперин-Шериффа и Пейкерта .<ref name="AP14" />
Обе библиотеки являются реализациями полностью гомоморфного шифрования. HElib показывает результат в 5-10 минут для преобразования сжатого шифротекста с порядка 1000 знаков в гибкий.<ref name="HS14b">{{cite web|last1=Halevi|first1=Shai|last2=Shoup|first2=Victor|title=Bootstrapping for HElib|url=http://eprint.iacr.org/2014/873|website=Cryptology ePrint archive|accessdate=2015-01-02|archive-date=2015-11-19|archive-url=https://web.archive.org/web/20151119060406/http://eprint.iacr.org/2014/873|deadlink=no}}</ref> FHEW преобразует несжатый шифротекст в гибкий за порядка 1/2 секунды на один бит.<ref name="DM14">{{cite web|last1=Ducas|first1=Léo|last2=Micciancio|first2=Daniele|title=FHE Bootstrapping in less than a second|url=http://eprint.iacr.org/2014/816|website=Cryptology ePrint archive|accessdate=2015-01-02|archive-date=2015-11-19|archive-url=https://web.archive.org/web/20151119041209/http://eprint.iacr.org/2014/816|deadlink=no}}</ref>
В конце 2014 обновленная реализация HElib показала результат в 4 минуты для расчета AES схемы для 120 входных потоков, достигнув тем самым удельной скорости в 2 секунды на один поток.<ref name="HElib" />

== Полностью гомоморфное шифрование в кольце двоичных чисел ==
{{стиль раздела|дата=2016-12-19}}
Схема полностью гомоморфного шифрования, которую предложил [[Крейг Гентри|Гентри]], может быть рассмотрена на примере вычислений в <math>\Z_2</math>.<ref name=autogenerated2>А. О. Жиров, О. В. Жирова, С. Ф. Кренделев «Безопасные облачные вычисления с помощью гомоморфной криптографии», http://bit.mephi.ru/wp-content/uploads/2013/2013_1/part_1.pdf {{Wayback|url=http://bit.mephi.ru/wp-content/uploads/2013/2013_1/part_1.pdf |date=20161110110440 }}</ref>

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

1. Выбирается произвольное нечетное [[число]] <math>p = 2k + 1</math>, являющееся секретным параметром. Пусть <math>m\in\left\{0,1\right\}</math>.

2. Составляется число <math>z \in \Z_2</math> такое, что <math>z = 2r + m</math>, где <math>r</math> — произвольное число. Это значит, что <math>z = m\ mod\ 2</math>.

3. В процессе шифрования всякому <math>m</math> ставится в соответствие число <math>c = z + pq</math>, где <math>q</math> выбирается произвольно.
Таким образом, <math>c = 2r + m + (2k + 1)*q</math>. Легко видеть, что <math>c\ mod\ 2 = (m + q)\ mod\ 2</math>, значит, злоумышленник сможет определить только четность выхода шифрования.

=== Расшифрование ===
Пусть известны зашифрованное число <math>c</math> и секрет <math>p</math>, тогда процесс расшифрования данных должен содержать следующие действия:

1.Расшифрование с использованием секретного параметра <math>p</math>: <math>r = c\ mod\ p = (z + pq)\ mod\ p = z\ mod\ p + (pq)\ mod\ p</math>, где <math>r = c\ mod\ p</math> называется шумом и <math>z\in\left(-{p\over 2}, {p\over 2}\right)</math>.

2.Получение исходного зашифрованного [[бит]]а: <math>m = r\ mod\ 2</math>

=== Обоснование ===
Пусть есть два бита <math>m_1, m_2\in\Z_2</math>, и им в соответствие поставлена пара чисел <math>z_1 = 2r_1 + m_1</math> и <math>z_2 = 2r_2 + m_2</math>.
Пусть взят секретный параметр <math>p = 2k + 1</math> и произведено шифрование данных: <math>c_1 = z_1 + pq_1</math> и <math>c_2 = z_2 + pq_2</math>.

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

<math>c_1 + c_2 = z_1 + pq_1 + z_2 + pq_2 = z_1 + z_2 + p(q_1 + q_2) = 2r_1 + m_1 + 2r_2 + m_2 + (2k + 1)(q_1 + q_2)</math>

Для суммы этих чисел расшифрованным сообщением будет сумма исходных бит <math>m_1, m_2 :

((c_1 + c_2)\ mod\ p)\ mod\ 2 = (2(r_1 + r_2) + m_1 + m_2)\ mod\ 2 = m_1 + m_2</math>.

Но, не зная <math>p</math>, расшифровать данные не представляется возможным: <math>((c_1 + c_2)\ mod\ p)\ mod\ 2 = m_1 + m_2 + q_1 + q_2</math>.

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

<math>c_1c_2 = (z_1 + pq_1)(z_2 + pq_2) = z_1z_2 + p(z_1q_2 + z_2q_1) + p^2q_1q_2 = (2r_1 + m_1)(2r_2 + m_2) + </math>

<math> + (2k + 1)((2r_1 + m_1)q_2 + (2r_2 + m_2)q_1) = 4r_1r_2 + 2(r_1m_2 + r_2m_1) + m_1m_2 +</math>

<math> 2k(2r_1q_2 + m_1q_2 + 2r_2q_1 + m_2q_1) + 2r_1q_2 + m_1q_2 + 2r_2q_1 + m_2q_1</math>

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

<math>((c_1c_2)\ mod\ p)\ mod\ 2 = (4r_1r_2 + 2(r_1m_2 + r_2m_1) + m_1m_2)\ mod\ 2 = m_1m_2</math>.

=== Недостатки ===
Использование данной полностью гомоморфной схемы шифрования в практических целях на данный момент не представляется возможным, так как в результате производимых вычислений накапливаемая ошибка <math>r</math> быстро достигает достаточно больших значений<ref name=autogenerated2 />. Возможна даже ситуация, при которой правильно расшифровать данные не удастся вовсе. Это произойдет в случае, если значение ошибки <math>r</math> превысит значение <math>p</math>. В попытках избежать столкновения с такой проблемой Гентри был разработан механизм самокоррекции шифротекстов (англ. bootstrapping), который в силу своей непрактичности из-за слишком быстрого роста объема шифротекста не нашел широкого применения. Решить данную проблему возможно, но для достижения поставленной задачи необходимо разработать более сложные алгоритмы вычислений либо ограничить количество операций над данными.<ref name=autogenerated2 />

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

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

Например, пользователь зашифровал некоторые свои данные и хранит их на удалённом облачном хранилище. Если пользователь намерен каким-либо образом изменить эти данные, он может либо доверить серверу свой секретный ключ, а следовательно, и доступ ко всей своей секретной информации, либо загрузить зашифрованные данные на свой компьютер, расшифровать их, выполнить необходимые вычисления и вернуть на сервер, но ни тот, ни другой способ не являются оптимальными. В первом случае невозможно исключить возможность утечки данных и доступа к ним третьих лиц, во втором случае время, необходимое для выполнения всех необходимых операций, может быть слишком большим. К тому же клиент может попросту не располагать необходимыми вычислительными ресурсами для произведения нужных ему вычислений.<ref name=autogenerated1 />

Также по данным международной исследовательской компании [[International Data Corporation|IDC]], занимающейся изучением мирового рынка [[Информационные технологии|информационных технологий]] и [[Электросвязь|телекоммуникаций]], многие компании с недоверием относятся к облачным технологиям, связывая с ними, в первую очередь, большие проблемы по части безопасности хранимых данных. А независимая исследовательская компания [[Portio Research]] опубликовала данные, согласно которым 68 % руководителей различных европейских IT не доверяют подобным сервисам. Так, например, руководитель компании [[G-DATA|G Data Security Labs]] Ральф Бенцмюллер высказался об облачных сервисах следующим образом: «Если вы не хотите, чтобы ваши данные стали достоянием общественности, не храните их в облачных хранилищах». Поэтому вопрос создания защищенного облачного хранилища с использованием полностью гомоморфной схемы шифрования данных в настоящее время стоит довольно остро<ref>Масштабные утечки данных: конец «облачным» сервисам? // Chip : журнал. — 2011. — № 8 (149). — С. 20—21. — ISSN 1609-4212</ref>.

=== Прочее ===
Полностью гомоморфное шифрование используется в поисковых системах, в которых требуется осуществление «приватного поиска», то есть такого поиска, при котором сервер ничего не знает о содержании поискового запроса и возвращает пользователю результат в зашифрованном виде. Помимо уже рассмотренных областей схемы полностью гомоморфного шифрования могут применяться в системах [[Электронное голосование|электронного голосования]], например, при использовании [[Слепая подпись|подписи вслепую]].<ref name=autogenerated1 />

== Ссылки ==
{{примечания|2}}

[[Категория:Криптография]]