Математика и математическое моделирование. 2022; : 31-51
О классификации n-разделимых функций многих переменных над конечными полями и одной задаче олимпиады NSUCrypto’2019
https://doi.org/10.24108/mathm.0122.0000262Аннотация
Одной из важных проблем, возникающих при проектировании и практической реализации криптосистем, является противодействие атакам по побочным каналам. Нередко алгоритмы, стойкость которых с чисто математической точки зрения не вызывает больших сомнений, оказываются уязвимыми к таким атакам при их реализации на конкретном физическом устройстве.
Техника разделений функций и отображений является эффективным инструментом для создания реализаций криптографических алгоритмов, защищенных от атак по побочным каналам. В настоящей статье исследуются неполные разделения булевых отображений и отображений над конечными полями. В рамках данной работы дано полное описание множества функций от n переменных, допускающих разделения на функции от n-1 переменной. Полученные результаты обобщаются на случай отображений над произвольными конечными полями.
Основными результатами данной работы являются следующие: введено и исследовано понятие "слабого неполного n-разделения"; установлена его связь с классическим понятием n-разделения, обоснованы его преимущества с точки зрения алгебраической структуры; установлен и доказан критерий существования слабого неполного n-разделения для произвольной функции над произвольным полем; дано явное описание функций от m переменных, допускающих n-разделения для случая конечных полей произвольной характеристики в терминах алгебраической нормальной формы; получены точные и простые описания для граничных случаев n = 2, n=m и двоичных полей; получен полный ответ на вопрос о представимости S-блока шифра AES в виде разделения.
Указанные результаты могут быть использованы для построения реализаций криптографических алгоритмов, защищенных от атак по побочным каналам. Также данный подход позволяет в ряде случаев обнаружить и количественно оценить принципиальную уязвимость конкретных криптографических конструкций к атакам по побочным каналам.
Также данные результаты могут быть интересны с теоретической точки зрения. В частности, представляется интересным их применение для решения задачи эффективной декомпозиции функций. Данная функциональность может быть применена, например, в современных системах компьютерной алгебры, символьных вычислений и машинного обучения.
Список литературы
1. Tokareva N.N., Gorodilova A.A., Agievich S.V., Idrisova V.A., Kolomeec N.A., Kutsenko A.V., Oblaukhov A.K., Shushuev G.I. Mathematical methods in solutions of the problems presented at the Third International Student’s Olympiad in Cryptography // Прикладная дискретная математика. 2018. № 40. С. 34-58. DOI: 10.17223/20710410/40/4
2. Gorodilova A.A., Agievich S.V., Carlet C., Gorkunov E.V., Idrisova V.A., Kolomeec N.A., Kutsenko A.V., Nikova S., Oblaukhov A.K., Picek S., Preneel B., Rijmen V., Tokareva N.N. Problems and solutions from the Fourth International Student’s Olympiad in Cryptography (NSUCRYPTO) // Cryptologia. 2019. Vol. 43. No. 2. Pp. 138-174. DOI: 10.1080/01611194.2018.1517834
3. Городилова А.А., Токарева Н.Н., Агиевич С.В., Карле К., Горкунов Е.В., Идрисова В.А., Коломеец Н.А., Куценко А.В., Лебедев Р.К., Никова С., Облаухов А.К., Панкратова И.А., Пудовкина М.А., Реймен В., Удовенко А.Н. О шестой международной олимпиаде по криптографии NSUCRYPTO // Дискретный анализ и исследование операций. 2020. Т. 27. № 4. С. 21–57. DOI: 10.33048/daio.2020.27.689
4. Nikova S., Rechberger C., Rijmen V. Threshold implementations against side-channel attacks and glitches // Information and communications security: 8th Intern. conf. on information and communications security: ICICS 2006 (Raleigh, NC, USA, December 4-7, 2006): Proc. B.: Springer, 2006. Pp. 529–545. DOI: 10.1007/11935308_38
5. Bilgin B., Gierlichs B., Nikova S., Nikov V., Rijmen V. Higher-order threshold implementations // Advances in cryptology -- ASIACRYPT 2014 – 20th Intern. conf. on the theory and application of cryptology and information security (Kaoshiung, Taiwan, R.O.C., December 7-11, 2014): Proc. Pt. II. B.: Springer, 2014. Pp. 326–343. DOI: 10.1007/978-3-662-45608-8_18
6. De Cnudde T., Reparaz O., Bilgin B., Nikova S., Nikov V., Rijmen V. Masking AES with d + 1 Shares in Hardware // 2016 ACM workshop on theory of implementation security: TIS’2016 (Vienna, Austria, October 24, 2016): Proc. N.Y.: ACM, 2016. P. 43. DOI: 10.1145/2996366.2996428
7. Dhooghe S., Nikova S., Rijmen V. Threshold implementations in the robust probing model // 2019 ACM workshop on theory of implementation security: TIS’2019 (London, UK, November 11, 2019): Proc. N.Y.: ACM, 2019. Pp. 30-37. DOI: 10.1145/3338467.3358949
8. Dworkin M.J., Barker E.B., Nechvatal J.R., Foti J., Bassham L.E., Roback E., Dray J.F.jr. Advanced Encryption Standard (AES). Federal Inf. Process. Stds. (NIST FIPS) - 197. Published November 26, 2001. DOI: 10.6028/NIST.FIPS.197
9. Daemen J., Rijmen V. The design of Rijndael. AES – The Advanced Encryption Standard. B.: Springer, 2002. 238 p. DOI: 10.1007/978-3-662-04722-4
10. Murphy S., Robshaw M.J.B. Essential algebraic structure within the AES // Advances in cryptology — CRYPTO 2002: 22nd Annual intern. cryptology conf. (Santa Barbara, CA, USA, August 18-22, 2002): Proc. B.: Springer, 2002. Pp. 1-16. DOI:10.1007/3-540-45708-9_1
Mathematics and Mathematical Modeling. 2022; : 31-51
Regarding Classification of n-sharing of Multivariate Mappings over Finite Fields and One NSUCrypto'2019 Olympiad Problem
https://doi.org/10.24108/mathm.0122.0000262Abstract
A problem of great importance that arises in designing and implementation of a cryptosystem is countering side channel attacks. Often an appropriate mathematical algorithm, implemented on a specific physical device to work in the physical environment, becomes vulnerable to such attacks.
The “function sharing” technique is a prospective and efficient way to avoid this problem. In the paper we investigate “non-complete sharing” of Boolean functions and mappings, and functions and mappings over finite fields and provide a complete description of the set of functions with n variables, which have sharing.
The main findings are the following: introducing and investigating a new concept of “weak” non-complete n-sharing, establishing its connection with “weak” and “classical” n-sharing, and substantiating its advantages from the algebraic point-of-view as well as establishing and proving a criterion for the existence of weak non-complete n-sharing for an arbitrary function. The results also include an explicit description of a set of functions which have weak sharing in terms of algebraic normal form, obtaining the precise and simple descriptions for the boundary (“border”) cases: n = 2, n=m and binary fields. Applying these results to the AES S-box allows complete solving the problem, i.e. a complete answer to the question of a representability of the S-box of the AES cipher as a sharing is available. We believe that the same way can be successful for other cryptographic algorithms.
References
1. Tokareva N.N., Gorodilova A.A., Agievich S.V., Idrisova V.A., Kolomeec N.A., Kutsenko A.V., Oblaukhov A.K., Shushuev G.I. Mathematical methods in solutions of the problems presented at the Third International Student’s Olympiad in Cryptography // Prikladnaya diskretnaya matematika. 2018. № 40. S. 34-58. DOI: 10.17223/20710410/40/4
2. Gorodilova A.A., Agievich S.V., Carlet C., Gorkunov E.V., Idrisova V.A., Kolomeec N.A., Kutsenko A.V., Nikova S., Oblaukhov A.K., Picek S., Preneel B., Rijmen V., Tokareva N.N. Problems and solutions from the Fourth International Student’s Olympiad in Cryptography (NSUCRYPTO) // Cryptologia. 2019. Vol. 43. No. 2. Pp. 138-174. DOI: 10.1080/01611194.2018.1517834
3. Gorodilova A.A., Tokareva N.N., Agievich S.V., Karle K., Gorkunov E.V., Idrisova V.A., Kolomeets N.A., Kutsenko A.V., Lebedev R.K., Nikova S., Oblaukhov A.K., Pankratova I.A., Pudovkina M.A., Reimen V., Udovenko A.N. O shestoi mezhdunarodnoi olimpiade po kriptografii NSUCRYPTO // Diskretnyi analiz i issledovanie operatsii. 2020. T. 27. № 4. S. 21–57. DOI: 10.33048/daio.2020.27.689
4. Nikova S., Rechberger C., Rijmen V. Threshold implementations against side-channel attacks and glitches // Information and communications security: 8th Intern. conf. on information and communications security: ICICS 2006 (Raleigh, NC, USA, December 4-7, 2006): Proc. B.: Springer, 2006. Pp. 529–545. DOI: 10.1007/11935308_38
5. Bilgin B., Gierlichs B., Nikova S., Nikov V., Rijmen V. Higher-order threshold implementations // Advances in cryptology -- ASIACRYPT 2014 – 20th Intern. conf. on the theory and application of cryptology and information security (Kaoshiung, Taiwan, R.O.C., December 7-11, 2014): Proc. Pt. II. B.: Springer, 2014. Pp. 326–343. DOI: 10.1007/978-3-662-45608-8_18
6. De Cnudde T., Reparaz O., Bilgin B., Nikova S., Nikov V., Rijmen V. Masking AES with d + 1 Shares in Hardware // 2016 ACM workshop on theory of implementation security: TIS’2016 (Vienna, Austria, October 24, 2016): Proc. N.Y.: ACM, 2016. P. 43. DOI: 10.1145/2996366.2996428
7. Dhooghe S., Nikova S., Rijmen V. Threshold implementations in the robust probing model // 2019 ACM workshop on theory of implementation security: TIS’2019 (London, UK, November 11, 2019): Proc. N.Y.: ACM, 2019. Pp. 30-37. DOI: 10.1145/3338467.3358949
8. Dworkin M.J., Barker E.B., Nechvatal J.R., Foti J., Bassham L.E., Roback E., Dray J.F.jr. Advanced Encryption Standard (AES). Federal Inf. Process. Stds. (NIST FIPS) - 197. Published November 26, 2001. DOI: 10.6028/NIST.FIPS.197
9. Daemen J., Rijmen V. The design of Rijndael. AES – The Advanced Encryption Standard. B.: Springer, 2002. 238 p. DOI: 10.1007/978-3-662-04722-4
10. Murphy S., Robshaw M.J.B. Essential algebraic structure within the AES // Advances in cryptology — CRYPTO 2002: 22nd Annual intern. cryptology conf. (Santa Barbara, CA, USA, August 18-22, 2002): Proc. B.: Springer, 2002. Pp. 1-16. DOI:10.1007/3-540-45708-9_1
