Algorithms of electronic digital signature based on algebraic coding

Authors

  • А.А. Кузнецов
  • А.И. Пушкарев
  • А.C. Киян

Keywords:

code cryptosystem, electronic digital signature, post-quantum cryptography

Abstract

The code cryptosystems are considered, the cryptanalysis problem in them is reduced to solving an NP-complex problem of decoding a random linear code. A new scheme of the EDS using algebraic codes is proposed, comparative evaluations of efficiency are carried out for various indicators (stability, complexity of formation and verification of the EDS, volumes of key data, length of signature, etc.).

References

Alfred, J. Menezes, Paul C. van Oorschot, Scott, A. Vanstone. Handbook of Applied Cryptography – CRC Press, 1997. – 794 р.

Горбенко, І.Д., Горбенко, Ю.І. Прикладна криптологія. Теорія. Практика. За-стосування : підручник для вищих навч. закладів. – Харків : Форт, 2013. – 880 с.

Nigel Smart. Cryptography: An Introduction (3rd Edition). – 432 pp. https://www.cs.umd.edu/~waa/414-F11/IntroToCrypto.pdf

ISO/IEC 9796-2:2010 "Information technology – Security techniques – Digital signature schemes giving message recovery – Part 2: Integer factorization based mechanisms".

ISO/IEC 9796-3:2006 "Information technology – Security techniques – Digital signature schemes giving message re-covery – Part 3: Discrete logarithm based mechanisms".

ISO/IEC 14888-1:2008 "Information technology – Security techniques – Digital signatures with appendix – Part 1: General".

ISO/IEC 14888-2:2008 "In-formation technology – Security techniques – Digital signatures with appendix – Part 2: Integer factorization based mechanisms".

ISO/IEC 14888-3:2006 "Information technology – Security techniques – Digital signatures with appendix – Part 3: Discrete logarithm based mechanisms".

ISO/IEC 15946-1:2008 "Infor-mation technology – Security techniques – Cryptographic techniques based on elliptic curves – Part 1: General".

ISO/IEC 15946-5:2009 "Information technology – Security techniques – Cryptographic techniques based on elliptic curves – Part 5: Elliptic curve generation".

David Deutsch and Richard 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. – Р. 553-558.

Cleve, R., Ekert,A., Macchiavello, C., Mosca, M. Quantum algorithms revisited // Proceedings of The Royal Society of London A: Mathematical, Physical and Engineering Sciences, vol. 454, no. 1969. – 1998. – P. 339-354.

Simon, D. R. On the power of quantum computation // Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium. – P. 116-123.

Grover, L. A fast quantum mechanical algorithm for database search. // Proceedings of the 28th annual ACM symposium on the theory of computing (STOC, 96). ACM Press, New York. – 1996. – P. 212–219.

Grover, L. A framework for fast quantum mechanical algorithms // Proceedings of the 13th annual ACM symposium on theory of computing (STOC' 98). ACM Press, New York. – 1998. – P. 53–62.

Shor, P. W. Algorithms for quantum computation: discrete logarithms and factoring // Foundations of Computer Science : Conference Publications. – 1994. – P. 124-134.

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

Neal Koblitz and Alfred J. Menezes. A Riddle Wrapped in an Enigma. https://eprint.iacr.org/2015/1018.pdf

Committee on National Security Systems, Use of public standards for the secure sharing of information among national security systems, Advisory Memorandum 02-15, July 2015. https://cryptome.org/2015/08/CNSS_Advisory_Memo_02-15.pdf.

Bernstein, Daniel J., Buchmann, Johannes, and Dahmen, Erik. Post-Quantum Cryptography. – 2009, Springer-Verlag, Berlin-Heidleberg. – 245 p.

Lily Chen, Stephen Jordan, Yi-Kai Liu, Dustin Moody, Rene Peralta, Ray Perlner, Daniel Smith-Tone. NISTIR 8105. Report on Post-Quantum Cryptography. National Institute of Standards and Technology. http://nvlpubs.nist.gov/nistpubs/ir/2016/NIST.IR.8105.pdf.

Dustin Moody. Post Quantum Cryptography: NIST’s Plan for the Future. National Institute of Standards and Technology. http://csrc.nist.gov/groups/ST/post-quantum-crypto/documents/pqcrypto-2016-presentation.pdf.

McEli-ece R. J. A public-key cryptosystem based on algebraic coding theory. DSN Progress Report 42-44, Jet Pro-pulsion Lab., Pasadena, CA, January-February, 1978. P. 114-116.

Niederreiter, H. Knapsack-type cryp-tosystems and algebraic coding theory // Problem Control and Inform Theory, 1986, v. 15. P. 19-34.

Stasev, Yu. V., Kuznetsov, A. A. Asymmetric Code-Theoretical Schemes Constructed with the Use of Alge-braic Geometric Codes // Cybernetics and Systems Analysis, Volume 41, Issue 3, May 2005, Pages 354 – 363.

Сидельников, В.М. Криптография и теория кодирования // Материалы конф. «Московский университет и развитие криптографии в России». – Москва : МГУ, 2002. – 22 с.

Сидельни-ков ,В.М., Шестаков, С.О. О системе шифрования, построенной на основе обобщенных кодов Рида – Соломона. // Дискретная математика. – 1992. – Т.4.№3. – С.57-63.

Кузнецов, А.А. Алгебраическая теория блоковых кодов и ее приложения в криптографии // Перша міжнар. наук. конф. 25–27 травня 2005р. „Теорія та методи обробки сигналів”. Тези доповідей. – К. : НАУ. – 2005. – С. 6 – 8.

Кузнецов, А.А. Исследование эффективности криптосистем на алгебраических блоковых кодах // Системи обробки інформації. – Харкiв : ХУПС, 2005 – Вип. 4. – С. 202 –206.

Кузнецов, А.А. Исследование помехоустойчивости и криптостойкости теоретико-кодовых схем // Моделювання та інформаційні технології. – Київ : НАНУ, 2005. – №33. – С. 81-84.

Courtois, N., Finiasz, M., and N.Sendrier How to achieve a McEliece-based digital signature scheme // Advances in Cryptology – ASIACRYPT 2001, volume 2248, pages 157–174.

E. Berlekamp, R. McEliece, H. van Tilborg. On the Inherent Intractability of Certain Coding Problems // IEEE Transactions on Information Theory, vol. IT-24, No. 3, May 1978. – Р. 384-386.

Кузнецов, А., Пушкарев, А., Кавун, С., Калашников, В. Несимметричные криптосистемы на основе алгебраического кодирования: современное состояние, существующие противоречия и перспективы практического использования на постквантовый период // Computer science and cybersecurity. – Kharkiv : V.N. Karazin Kharkiv National University, 2016. – Issue 3(3) 2016. – P. 36-60.

Кузнецов, А.А., Пушкарев, А.И., Сватовский, И.И., Шевцов, А.В. Несимметричные криптосистемы на алгебраических кодах для пост-квантового периода // Радиотехника. – 2016. – Вып. 186. – С. 70-90.

Кузнецов, О., Пушкарьов, А., Шевцов, О., Кузнецова, Т. Несиметричне криптографічне перетворення з використанням алгебраїчних блокових кодів // Захист інформації. – Київ : Нац. авіа-ційний ун-т, 2016. – Т. 18, №4, жовтень-грудень 2016. – С. 269-275.

Кузнецов, О.О., Пушкарьов, А.І., Шевцов, О.В, Кузнецова, Т.Ю. Несиметричне криптоперетворення з використанням алгебраїчних блокових кодів // Актуальні задачі та досягнення у галузі кібербезпеки: матеріали Всеукр. наук.-практ. конф., 23–25 листопада 2016 року. – Кропивницький : КНТУ, 2016. – С. 124-127.

Кузнецов О.О., Пушкарьов А.І., Шевцов О.В., Кузнецова Т.Ю. Несиметричні крипто-кодові системи захисту інформації // 71-а наук.-техн. конф. професорсько-викладацького складу, науковців, аспірантів та студентів : матеріали конф. (6-8 грудня 2016 р.) – Одеса : ОНАЗ, 2016. – 84-87 с.

Кузнецов, О.О., Пушкарьов, А.І., Сватовський, І.І., Шевцов, А.В., Кузнецова, Т.Ю. Несиметричні криптосистеми на алгебраїчних блокових кодах // Актуальні питання забезпечення кібербезпеки та захисту інформації: тези доповідей учасників ІІІ Міжнар. наук.-практ. конф., 22-25 лютого 2017 р. – К. : Вид-во Євро-пейського ун-ту, 2017. – С. 108-112.

Кузнецов, А.А., Сватовский, И.И., Шевцов, А.В. Схемы электронной цифровой подписи на основе помехоустойчивых кодов // Труды науч.-техн. конф. с международным участием «Компьютерное моделирование в наукоемких технологиях», 26-31 мая 2016 г. – Харьков : ХНУ имени В.Н. Каразина, 2016. – С. 191-193.

Кузнецов, А., Сватовский, И., Шевцов, А. Электронная цифровая подпись на алгебраических кодах для постквантового периода // Матеріали V-ї міжнар. наук.-техн. конф. “Захист інформації і безпека інформаційних систем”, 2-3 червня 2016 р. – Львів : НУ “Львівська політехніка”, 2016. – С. 122-123.

Кузнецов, А.А., Сватовский, И.И., Шевцов, А.В. Алгоритми цифрового підпису для постквантового періоду із засто-сування алгебраїчних кодів: сучасний стан, існуючі протиріччя та перспективи практичного застосування // Безпека інформації в інформаційно-телекомунікаційних системах : Матеріали міжнар. наук.-практ. конф. Вип. 18, 25-26 травня 2016 р. – К. : Державна служба спеціального зв’язку та захисту інформації України, 2016 – С. 17.

Гоппа, В. Д. Новый класс линейных корректирующих кодов // Проблемы передачи информации. – 1970. – Т. 6, вып. 3. – С. 24–30.

Гоппа, В. Д. На неприводимых кодах достигается пропускная способность ДСК // Проблемы передачи информации. – 1974. – Т. 10, вып. 1. – С. 111–112.

MacWilliams, F. J. and Sloane,N. J. A. The theory of error-correcting codes. – North-Holland, Amsterdam, New York, Oxford, 1977. – 762 pp.

Downloads

How to Cite

Кузнецов, А., Пушкарев, А., & Киян, А. (2017). Algorithms of electronic digital signature based on algebraic coding. Radiotekhnika, 2(189), 59–74. Retrieved from http://rt.nure.ua/article/view/183314

Issue

No. 189 (2017): Radiotekhnika

Section

Articles

License

Authors who publish with this journal agree to the following terms:

1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).