Схеми на основі кодів для цифрових підписів

Alexandr Kuznetsov Харківський національний університет імені В. Н. Каразіна, м. Харків
Anastasia Kiian Харківський національний університет імені В.Н. Каразіна, м. Харків
Ivan Belozertsev Харківський національний університет імені В.Н. Каразіна, м. Харків
Mykola Pastukhov Університет митної справи та фінансів, м. Дніпро
Dmytro Prokopovych-Tkachenko Університет митної справи та фінансів, м. Дніпро

Ключові слова: постквантова криптографія;, цифровий підпис;, криптографія на основі кодів;, квантова безпека;

Анотація

Стаття присвячена розгляду особливостей побудови і використання схем електронного цифрового підпису, заснованих на використанні кодів, виправляючих помилки, а саме найпоширенішої схеми, яка базується на цьому підході, CFS і нової запропонованої схеми. Функціонування цих схем безпосередньо залежить від використовуваної кодової криптосистеми: перша в своїй основі містить принципи кодової криптосистеме Нідеррайтера, друга передбачає використання криптосистеми Мак-Еліса, що до недавнього моменту вважалося неможливим. Детально розглянуті алгоритми формування та перевірки підпису згідно обох схем, описані покроково. У роботі проведені дослідження ефективності алгоритмів з точки зору обсягу необхідних ключових даних і довжини сформованого підпису, результати якого представлені за допомогою аналітичних співвідношень і на конкретних прикладах в графічному вигляді. Також було проаналізовано стійкість розглянутих схем до класичного і квантового криптоаналізу, останній з яких є актуальною тематикою в еру стрімкого розвитку сфери пост-квантової криптографії. Розглянуты схеми мають доказову стійкість до обох видів криптоанализу, однак при використанні квантових комп'ютерів необхідно значно збільшувати довжини ключів, що є вагомим недостакі. Виявлено факт, що запропонована схема має незаперечну перевагу перед використовуваної схемою CFS - захист від специфічних атак таких, як одночасна заміна двох елементів підпису і швидка фальсифікація, за рахунок додавання додаткового елемента в сформований підпис. Протягом дослідження виділені переваги, недоліки і перспективи використання запропонованої схеми і схеми CFS в умовах застосування квантових комп'ютерів.

Завантаження

##plugins.generic.usageStats.noStats##

Біографії авторів

Alexandr Kuznetsov, Харківський національний університет імені В. Н. Каразіна, м. Харків

д.т.н., проф., академік Академії наук прикладної радіоелектроніки

Anastasia Kiian, Харківський національний університет імені В.Н. Каразіна, м. Харків

студентка факультету комп'ютерних наук

Ivan Belozertsev, Харківський національний університет імені В.Н. Каразіна, м. Харків

студент факультету комп'ютерних наук

Mykola Pastukhov, Університет митної справи та фінансів, м. Дніпро

к.т.н., доцент

Dmytro Prokopovych-Tkachenko, Університет митної справи та фінансів, м. Дніпро

к.т.н., завідувач кафедрою кібербезпеки

Посилання

A.J. Menezes, P.C. van Oorschot, S.A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1997, 794 р.

N. Ferguson and B. Schneier. Practical Cryptography. John Wiley & Sons, 2003, 432 p.

D. Bernstein, J. Buchmann and E.Dahmen. Post-Quantum Cryptography. Springer-Verlag, Berlin-Heidleberg, 2009, 245 p.

J. Proos and Ch. Zalka. “Shor’s discrete logarithm quantum algorithm for elliptic curves”. [On-line]:https://arxiv.org/abs/quant-ph/0301141.

D. Deutsch and R. Jozsa. “Rapid solutions of problems by quantum computation”. Proceedings of The Royal Society of London A: Mathematical, Physical and Engineering Sciences, Vol. 439, No. 1907. – 1992. pp. 553-558.

P.W. Shor. “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”. Foundations of Computer Science: Conference Publications, 1997, pp. 1484-1509.

Niederreiter, H. “Knapsack-type cryptosystems and algebraic coding theory”. Problem Control and Inform Theory, 1986, V. 15. pp. 19-34.

Yu.V. Stasev, A.A. Kuznetsov. “Asymmetric code-theoretical schemes constructed with the use of algebraic geometric codes”. Kibernetika i Sistemnyi Analiz, No. 3, pp. 47-57, May-June 2005.

A. Kuznetsov, I. Svatovskij, N. Kiyan and A. Pushkar'ov. "Code-based public-key cryptosystems for the post-quantum period, "2017 4th International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T), Kharkov, 2017, pp. 125-130.

A. Kuznetsov, R. Serhiienko and D. Prokopovych-Tkachenko. "Construction of cascade codes in the frequency domain, "2017 4-th International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T), Kharkov, 2017, pp. 131-136.

Yu.V. Stasev, A.A. Kuznetsov. “Asymmetric Code-Theoretical Schemes Constructed with the Use of Algebraic Geometric Codes.” Cybernetics and Systems Analysis, Vol. 41, Issue 3, pp. 354-363, May 2005.

M. Finiasz and N. Sendrier. “Security bounds for the design of codebased cryptosystems”. In M. Matsui, ed., Advances in Cryp-tology, ASIACRYPT 2009, Vol. 5912 of Lecture Notes in Computer Science. -Springer Berlin Heidelberg, 2009, pp. 88-105.

N.Courtois, M.Finiasz and N.Sendrier. “How to achieve a McEliece-based digital signature scheme”. In Advances in Cryptology - ASIACRYPT 2001, Vol. 2248, pp. 157–174.

M. Finiasz “Parallel-CFS: Strengthening the CFS McEliece-based signature scheme”. In Biryukov A., Gong G., Stinson D., eds.: Selected Areas in Cryptography. Vol. 6544 of LNCS., Springer (2010) pp.159-170.

J. Stern “A new identification scheme based on syndrome decoding”. In Advances in Cryptology - CRYPTO’93, Vol. 773 of LNCS. Springer Verlag (1994).

R. J. McEliece “A public-key cryptosystem based on algebraic coding theory”. DSN Progress Report 42-44, Jet Propulsion Lab., Pasadena, CA, January-February, 1978, pp. 114-116.

V. M. Sidel'nikov “Kriptografiya i teoriya kodirovaniya”. Materialy konferentsii «Moskovskii universitet i razvitie kriptografii v Rossii», MGU. – 2002. – 22 p. (in Russian).

S. Sander “Study of McElice cryptosystem”. [On-line]: https://courses.cs.ut.ee/MTAT.07.022/2015_spring/uploads/Main/sander-report-s15.pdf.

Li, Y. X., Deng, R.H., Wang, X.M. “On the equivalence of McEliece’s and Niederreiter’s public-key cryptosystems”. [On-line]: https://ieeexplore.ieee.org/document/272496/.

Clark, G.C., Cain, J.B. Error-Correction Coding for Digital Communications. Springer, 1981, 432 p.