tuzsutТруды учебных заведений связиProceedings of Telecommunication Universities1813-324X2712-8830СПбГУТ10.31854/1813-324X-2021-7-2-85-93tuzsut-168Research ArticleИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ И ТЕЛЕКОММУНИКАЦИИINFORMATION TECHNOLOGIES AND TELECOMMUNICATIONСхема цифровой подписи со скрытой группой, обладающей двухмерной цикличностьюDigital Signature Scheme with Hidden Group Possessing Two-Dimensional Cyclicityhttps://orcid.org/0000-0001-5039-7198МолдовянД. Н.MoldovyanD. N.

Молдовян Дмитрий Николаевич – кандидат технических наук, научный сотрудник лаборатории кибербезопасности и постквантовых криптосистем 

Санкт-Петербург, 199178

St. Petersburg, 199178

mdn.spectr@mail.ruФахрутдиновР. А.FahrutdinovR. Sh.

Фахрутдинов Роман Шафкатович – кандидат технических наук, заведующий лабораторией кибербезопасности и постквантовых криптосистем 

Санкт-Петербург, 199178

St. Petersburg, 199178

fahr@cobra.ruМиринA. Ю.MirinA. Yu.

Мирин Анатолий Юрьевич – кандидат технических наук, старший научный сотрудник лаборатории кибербезопасности и постквантовых криптосистем

Санкт-Петербург, 199178

St. Petersburg, 199178

mirin@cobra.ruКостинаА. А.KostinaA. A.

Костина Анна Александровна – научный сотрудник лаборатории кибербезопасности и постквантовых криптосистем

Санкт-Петербург, 199178

 

 

St. Petersburg, 199178

anna-kostina1805@mail.ruСанкт-Петербургский Федеральный исследовательский центр Российской академии наукРоссияSt. Petersburg Federal Research Center of the Russian Academy of SciencesRussian Federation202125092021728593Copyright © Молдовян Д.Н., Фахрутдинов Р.А., Мирин A.Ю., Костина А.А., 20212021Молдовян Д.Н., Фахрутдинов Р.А., Мирин A.Ю., Костина А.А.Moldovyan D.N., Fahrutdinov R.S., Mirin A.Y., Kostina A.A.This work is licensed under a Creative Commons Attribution 4.0 License.https://tuzs.sut.ru/jour/article/view/168

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

A method is proposed for constructing digital signature schemes based on the hidden discrete logarithm problem, which meet ageneral criterion of post-quantum resistance. The method provides a relatively small size of the public key and signature. Based on the method, a practical digital signature scheme has been developed, in which the exponentiation operation in a hidden group with two-dimensional cyclicity is the basic cryptographic primitive. The algebraic support of a cryptoscheme is a four-dimensional finite non-commutative algebra with associative multiplication operation. By specifying algebra using abasis vector multiplication table with half of empty cells, the performance of signature generation and authentication procedures is improved. A public key is a triple of fourdimensional vectors calculated as images of elements of a hidden group which are mapped using two types of masking operations: 1) mutually commutative with the exponentiation operation and 2) not having this property.

защита информациикомпьютерная безопасностькриптографияцифровая подписьпостквантовая криптосхемазадача дискретного логарифмированияконечная ассоциативная алгебранекоммутативная алгебраскрытая группаinformation protectioncomputer securitycryptographydigital signaturepost-quantum cryptoschemediscrete logarithm problemfinite associative algebranon-commutative algebrahidden groupРабота выполнена при финансовой поддержке РФФИ в рамках научного проекта № 21-57-54001-Вьет_а).This research was funded by RFBR according to the research project 21-57-54001 Viet_a.ReferencesDing J., Steinwandt R. Post-Quantum Cryptography // Revised Selected Papers of the 10th International Conference (PQCrypto 2019, Chongqing, China, 8–10 May 2019). Lecture Notes in Computer Science. Security and Cryptology. Springer, 2019. Vol. 11505. 418 p.Ding J., Steinwandt R. Post-Quantum Cryptography. Revised Selected Papers of the 10th International Conference, PQCrypto 2019, Chongqing, China, 8–10 May 2019. Lecture Notes in Computer Science. Security and Cryptology. Springer; 2019. vol.11505. 418 p.Announcing Request for Nominations for Public-Key Post-Quantum Cryptographic Algorithms // Federal Register. 2016. Vol. 81. No. 244. Available from: https://www.gpo.gov/fdsys/pkg/FR-2016-12-20/pdf/2016-30615.pdf [Accessed 24th May 2021]Announcing Request for Nominations for Public-Key Post-Quantum Cryptographic Algorithms. Federal Register. 2016;81(244). Available from: https://www.gpo.gov/fdsys/pkg/FR-2016-12-20/pdf/2016-30615.pdf [Accessed 24th May 2021]Молдовян А.А., Молдовян Д.Н. Постквантовые протоколы цифровой подписи на основе скрытой задачи дискретного логарифмирования // Вопросы защиты информации. 2019. № 2(125). С. 2332.Moldovyan A.A., Moldovyan D.N. Post-Quantum Digital Signature Protocols Based on the Hidden Discrete Logarithm Problem. Information Security Questions (Voprosy zaŝity informacii). 2019;2(125):23-32.Moldovyan N.A., Moldovyan A.A. Finite Non-commutative Associative Algebras as carriers of Hidden Discrete Logarithm Problem // ВестникЮУрГУ. Серия «Математическое моделирование и программирование». 2019. Т. 12. № 1. С. 66–81. DOI:10.14529/mmp190106Moldovyan N.A., Moldovyan A.A. Finite Non-commutative Associative Algebras as carriers of Hidden Discrete Logarithm Problem. Bulletin of the South Ural State University. Ser. Mathematical Modelling, Programming & Computer Software. 2019;12(1):66–81. DOI:10.14529/mmp190106Молдовян Н.А., Абросимов И.К Постквантовая схема ЭЦП на основе скрытой задачи дискретного логарифмирования в четырехмерной конечной алгебре // Вопросы защиты информации. 2019. № 2. С. 1822.Молдовян Н.А., Молдовян Д.Н. Постквантовая схема ЭЦП на основе скрытой задачи дискретного логарифмирования в четырехмерной конечной алгебре // Вопросы защиты информации. 2019. № 2. С. 18-22.Moldovyan A.A., Moldovyan N.A. Post-quantum signature algorithms based on the hidden discrete logarithm problem // Computer Science Journal of Moldova. 2018. Vol. 26. No. 3(78). PP. 301‒313.Moldovyan A.A., Moldovyan N.A. Post-quantum signature algorithms based on the hidden discrete logarithm problem. Computer Science Journal of Moldova. 2018;26(3(78)):301‒313.Shor P.W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on Quantum Computer // SIAM Review. 1999. Vol. 41. Iss. 2. PP. 303–332. DOI:10.1137/S0036144598347011Shor P.W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on Quantum Computer. SIAM Review. 1999;41(2):303–332. DOI:10.1137/S0036144598347011Ekert A., Jozsa R. Quantum computation and Shor’s factoring algorithm // Reviews of Modern Physics. 1996. Vol. 68. PP. 733. DOI:10.1103/RevModPhys.68.733Ekert A., Jozsa R. Quantum computation and Shor’s factoring algorithm. Reviews of Modern Physics. 1996;68:733. DOI:10.1103/RevModPhys.68.733Jozsa R. Quantum algorithms and the Fourier transform // Proceedings of the Royal Society A. Mathematical, Physical and Engineering Sciences. 1998. Vol. 454. Iss. 1969. PP. 323‒337. DOI:10.1098/rspa.1998.0163Jozsa R. Quantum algorithms and the Fourier transform. Proceedings of the Royal Society A. Mathematical, Physical and Engineering Sciences. 1998;454(1969):323‒337. DOI:10.1098/rspa.1998.0163Moldovyan N.A., Moldovyan A.A. Candidate for practical post-quantum signature scheme // Вестник СанктПетербургского университета. Прикладная математика. Информатика. Процессы управления. 2020. Т. 16. №. 4. С. 455–461. DOI:10.21638/11701/spbu10.2020.410Moldovyan N.A., Moldovyan A.A. Candidate for practical post-quantum signature scheme. Vestnik of St Petersburg University. Applied Mathematics. Computer Science. Control Processes. 2020;16(4):455–461. DOI:10.21638/11701/spbu10. 2020.410Moldovyan N.A. Signature Schemes on Algebras, Satisfying Enhanced Criterion of Post-quantum Security // Buletinul Academiei de Stiinte a Republicii Moldova. Matematica. 2020. No. 2(93). PP. 62‒67.Moldovyan N.A. Signature Schemes on Algebras, Satisfying Enhanced Criterion of Post-quantum Security. Buletinul Academiei de Stiinte a Republicii Moldova. Matematica. 2020;2(93):62‒67.Moldovyan N.A. Fast signatures based on non-cyclic finite groups // Quasigroups and Related Systems. 2010. Vol. 1. No. 18. PP. 83‒94.Moldovyan N.A. Fast signatures based on non-cyclic finite groups. Quasigroups and Related Systems. 2010;1(18):83‒94.Moldovyan N.A., Moldovyanu P.A. New primitives for digital signature algorithms // Quasigroups and Related Systems. 2009. Vol. 2. No. 17. PP. 271‒282.Moldovyan N.A., Moldovyanu P.A. New primitives for digital signature algorithms. Quasigroups and Related Systems. 2009;2(17):271‒282.Фахрутдинов Р.Ш., Мирин А.Ю, Молдовян Д.Н., Костина А.А. Схемы открытого согласования ключей на основе скрытой задачи дискретного логарифмирования // Информационные технологии. 2020. Т. 26. № 10. С. 577‒585. DOI:10.17587/it.26Fahrutdinov R.S., Mirin A. Yu., Moldovyan D.N., Kostina A.A. Public Key ‒ Agreement Schemes Based on the Hidden Discrete Logarithm Problem. Information Technologies (Informacionnye Tehnologii). 2020;26(10):577‒585. DOI:10.17587/it.26Гурьянов Д.Ю., Молдовян Д.Н., Молдовян А.А. Постквантовые схемы цифровой подписи: задание скрытой группы с двухмерной цикличностью // Информатизация и связь. 2020. № 4. С. 75‒82. DOI:10.34219/2078-8320-202011-4-75-82Guryanov D.Yu., Moldovyan D.N., Moldovyan A.A. Post-Quantum Digital Signature Schemes: Setting a Hidden Group with Two-Dimensional Cyclicity. Informatizatsiia i sviaz. 2020;4:75‒82. DOI:10.34219/2078-8320-2020-11-4-75-82Fast-Fourier Lattice-Based Compact Signatures over NTRU // Falcon. URL: https://falcon-sign.info (дата обращения 24.05.2021)Fast-Fourier Lattice-Based Compact Signatures over NTRU. Falcon. URL: https://falcon-sign.info [Accessed 24th May 2021]Dilithium Home // CRYSTALS. Cryptographic Suite for Algebraic Lattices. URL: https://pq-crystals.org/dilithium/index.shtml (дата обращения 24.05.2021)Dilithium Home. CRYSTALS. Cryptographic Suite for Algebraic Lattices. URL: https://pq-crystals.org/dilithium/index. shtml [Accessed 24th May 2021]

The authors declare that there are no conflicts of interest present.