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