10.14489/vkit.2020.12.pp.040-046

DOI: 10.14489/vkit.2020.12.pp.040-046

Кадыков В. Ю., Левина А. Б.
ГОМОМОРФНЫЕ ОПЕРАЦИИ В СИСТЕМАХ ШИФРОВАНИЯ С ПРИМЕНЕНИЕМ РЕШЕТОК ИДЕАЛОВ
(с. 40-46)

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

Ключевые слова: гомоморфное шифрование; решетки идеалов.

Kadykov V. Yu., Levina A. B.
HOMOMORPHIC OPERATIONS WITHIN IDEAL LATTICE BASED ENCRYPTION SYSTEMS
(pp. 40-46)

Abstract. By 2009 the first system of fully homomorphic encryption had been constructed, and it was thought-provoking for many future works based on it. Instead of legacy encryption systems which depend on sharing a key (public or private) among endpoints involved in exchanging en encrypted message the fully homomorphic encryption can keep service without depending on shared keys and does not necessarily need to access the content. Such property allows any third party to operate on the encrypted data without decrypting it in advance. In this work, the possibility of using the ideal lattices for the construction of homomorphic operations is researched with a detailed level of math.The paper represents the analysis method based on the primitive of a union of ideals in lattice space. A segregated analysis between homomorphic and security properties is the advantage of this method. The work will be based on the analysis of generalized operations over ciphertext using the concept of the base reducing element which shares all about the method above. It will be shown how some non-homomorphic encryption systems can be supplemented by homomorphic operations which invoke different parameters choosing. Thus such systems can be decomposed from ciphertext structure to decryption process which will be affected by separately analyzed base reduction elements. Distinct from the encryption scheme the underlying math can be used to analyze only the homomorphic part, particularly under some simplifications. The building of such ideal-based ciphertext is laying on the assumption that ideals can be extracted further. It will be shown that the “remainder theorem” can be one of the principal ways to do this providing a simple estimate of an upper bound security strength of ciphertext structure.

Keywords: Homomorphic encryption; Ideal lattices.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

В. Ю. Кадыков, А. Б. Левина (Национальный исследовательский университет ИТМО, Санкт-Петербург, Россия) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

V. Yu. Kadykov, A. B. Levina (Saint-Petersburg National Research University of Information Technologies, Mechanics and Optics, Saint-Petersburg, Russia) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. On Data Banks and Privacy Homomorphisms / R. L. Rivest et al. // Foundations of Secure Computation. 1978. V. 4, No. 11. P. 169 – 180.
2. Gentry C., Boneh D. A Fully Homomorphic Encryption Scheme. Stanford: Stanford University, 2009. 209 p.
3. A survey on Homomorphic Encryption Schemes: Theory and Implementation / A. Acar, H. Aksu, A. S. Uluagac, M. Conti // ACM Computing Surveys (CSUR). 2018. V. 51, No. 4. P. 1 – 35.
4. Kadykov V. Yu., Levina A. B., Kaplun D. I. New Direction in Cryptography: Homomorphic Encryption // Second International Conference on Advances in Electrical, Electronics and System Engineering (ICAEESE). Roma, Italy, 22–23 Julay 2019. Roma, 2019. P. 142 – 147.
5. Vaikuntanathan V. Computing Blindfolded: New Developments in Fully Homomorphic Encryption // 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. IEEE, Palm Springs, California USA, 22–23 Oct. 2011. Palm Springs, 2011. P. 5 – 16.
6. Searching for Elements in Black-box Fields and Applications / D. Boneh et al. // Crypto. 1996. V. 96. P. 283 – 297.
7. Maurer U., Raub D. Black-box Extension Fields and the Inexistence of Field-homomorphic One-way Permutations // International Conference on the Theory and Application of Cryptology and Information Security. Springer, 2007. P. 427 – 443.
8. Van Dam W., Hallgren S., Ip L. Quantum Algorithms for Some Hidden Shift Problems // SIAM Journal on Computing. 2006. V. 36, No. 3. P. 763 – 778.
9. Rohloff K., Cousins D. B. A Scalable Mplementation of Fully Homomorphic Encryption Built on NTRU // International Conference on Financial Cryptography and Data Security. Barbados, 16 Febr. 2014. Springer, 2014. P. 221 – 234.
10. An Introduction to Mathematical Cryptography / J. Hoffstein, J. Pipher, J. H. Silverman, J. H. Silverman. Springer, 2008. V. 1. 530 p.
11. Fully Homomorphic Encryption Over the Integers / M. Van Dijk, C. Gentry, S. Halevi, V. Vaikuntanathan // Annual International Conference on the Theory and Applications of Cryptographic Techniques. Monaco and Nice, France, 2010, 30 May – 3 June. Springer, 2010. P. 24 – 43.

Eng

1. Rivest R. L. et al. (1978). On Data Banks and Privacy Homomorphisms. Foundations of Secure Computation, Vol. 4, (11), pp. 169 – 180.
2. Gentry C., Boneh D. (2009). A Fully Homomorphic Encryption Scheme. Stanford: Stanford University.
3. Acar A., Aksu H., Uluagac A. S., Conti M. (2018). A survey on Homomorphic Encryption Schemes: Theory and Implementation. ACM Computing Surveys (CSUR), Vol. 51, (4), pp. 1 – 35.
4. Kadykov V. Yu., Levina A. B., Kaplun D. I. (2019). New Direction in Cryptography: Homomorphic Encryption. Second International Conference on Advances in Electrical, Electronics and System Engineering (ICAEESE), pp. 142 – 147. Roma.
5. Vaikuntanathan V. (2011). Computing Blind-folded: New Developments in Fully Homomorphic Encryption. 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp. 5 – 16. Palm Springs.
6. Boneh D. et al. (1996). Searching for Elements in Black-box Fields and Applications. Crypto, Vol. 96, pp. 283 – 297.
7. Maurer U., Raub D. (2007). Black-box Extension Fields and the Inexistence of Field-homomorphic One-way Permutations. International Conference on the Theory and Application of Cryptology and Information Security, pp. 427 – 443. Springer.
8. Van Dam W., Hallgren S., Ip L. (2006). Quantum Algorithms for Some Hidden Shift Problems. SIAM Journal on Computing, Vol. 36, (3), pp. 763 – 778.
9. Rohloff K., Cousins D. B. (2014). A Scalable Mplementation of Fully Homomorphic Encryption Built on NTRU. International Conference on Financial Cryptography and Data Security, pp. 221 – 234. Barbados: Springer.
10. Hoffstein J., Pipher J., Silverman J. H. (2008). An Introduction to Mathematical Cryptography, Vol. 1. Springer.
11. Van Dijk M., Gentry C., Halevi S., Vaikuntanathan V. (2010). Fully Homomorphic Encryption Over the Integers. Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 24 – 43. Monaco and Nice. Springer.

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 350 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.

Для заказа скопируйте doi статьи:

10.14489/vkit.2020.12.pp.040-046

и заполните форму

Отправляя форму вы даете согласие на обработку персональных данных.

Eng

This article is available in electronic format (PDF).

The cost of a single article is 350 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please copy the article doi:

10.14489/vkit.2020.12.pp.040-046

and fill out the form