Digital Signature Scheme with Hidden Group Possessing Two-Dimensional Cyclicity

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.

1. 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.

2. 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]

3. 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.

4. Moldovyan 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

5. Молдовян Н.А., Молдовян Д.Н. Постквантовая схема ЭЦП на основе скрытой задачи дискретного логарифмирования в четырехмерной конечной алгебре // Вопросы защиты информации. 2019. № 2. С. 18-22.

6. 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.

7. Shor P.W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on Quantum Computer. SIAM Review. 1999;41(2):303–332. DOI:10.1137/S0036144598347011

8. Ekert A., Jozsa R. Quantum computation and Shor’s factoring algorithm. Reviews of Modern Physics. 1996;68:733. DOI:10.1103/RevModPhys.68.733

9. Jozsa 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.0163

10. Moldovyan 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.410

11. 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.

12. Moldovyan N.A. Fast signatures based on non-cyclic finite groups. Quasigroups and Related Systems. 2010;1(18):83‒94.

13. Moldovyan N.A., Moldovyanu P.A. New primitives for digital signature algorithms. Quasigroups and Related Systems. 2009;2(17):271‒282.

14. Fahrutdinov 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

15. Guryanov 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-82

16. Fast-Fourier Lattice-Based Compact Signatures over NTRU. Falcon. URL: https://falcon-sign.info [Accessed 24th May 2021]

17. Dilithium Home. CRYSTALS. Cryptographic Suite for Algebraic Lattices. URL: https://pq-crystals.org/dilithium/index. shtml [Accessed 24th May 2021]