Systems and Means of Informatics
2021, Volume 31, Issue 4, pp 38-47
POST-QUANTUM SIGNATURE SCHEME ON MATRIX ALGEBRA
- D. N. Moldovyan
- A. A. Moldovyan
- N. A. Moldovyan
Abstract
The paper considers the use of a finite multiplicative group of invertible matrices of dimension 2 x 2 set over the field GF(p) as algebraic carrier of the digital signature schemes based on the computational difficulty of the hidden discrete logarithm problem and satisfying the general criterion of post-quantum resistance. The existence of a sufficiently large number of commutative subgroups with two-dimensional cyclicity is shown. This fact is used in the construction of a specific signature scheme which is of interest as a post-quantum cryptosystem.
In the introduced digital signature scheme, a new form of the hidden discrete logarithm problem is applied. The said form is characterized by the use of a commutative group with two-dimensional cyclicity as a hidden group and masking operations of two different types: (i) having the property of mutual commutativity with the exponentiation operation and (ii) free from this property.
To ensure the correct operation of the cryptographic scheme, a special type of verification equation is used in the signature authentication procedure, and when generating a signature, one of the elements of the latter is calculated as a root of quadratic equation.
[+] References (7)
- Shor, P. W. 1997. Polynomial-time algorithms for prime factorization and discrete logarithms on quantum computer. SIAM J. Comput. 26:1484-1509.
- Jozsa, R. 1998. Quantum algorithms and the Fourier transform. Proc. R. Soc. Lon. Ser. A 454:323-337.
- Federal Register. Announcing Request for Nominations for Public-Key Post-Quantum Cryptographic Algorithms. Available at: https://www.govinfo.gov/content/pkg/FR- 2016-12-20/pdf/2016-30615.pdf (accessed September 20, 2021).
- Ding, J., and R. Steinwandt, eds. 2019. Post-quantum cryptography. Lecture notes in computer science ser. Springer. Vol. 11505. 420 p.
- Moldovyan, A. A., andN. A. Moldovyan. 2019. Novyeformy skrytoyzadachi diskretnogo logarifmirovaniya [New forms of defining the hidden discrete logarithm problem]. Trudy SPIIRAN [SPIIRAS Proceedings] 18(2):504-530.
- Moldovyan, D.N., A. A. Moldovyan, andN. A. Moldovyan. 2020. Digital signature scheme with doubled verification equation. Computer Science J. Moldova 28:80-103.
- Moldovyan, N. A. 2010. Fast signatures based on non-cyclic finite groups. Quasigroups Related Systems 18:83-94.
[+] About this article
Title
POST-QUANTUM SIGNATURE SCHEME ON MATRIX ALGEBRA
Journal
Systems and Means of Informatics
Volume 31, Issue 4, pp 38-47
Cover Date
2021-12-10
DOI
10.14357/08696527210404
Print ISSN
0869-6527
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
finite group of matrices; computationally difficult problem; discrete logarithm; digital signature; post-quantum cryptography
Authors
D. N. Moldovyan  , A. A. Moldovyan , and N. A. Moldovyan
Author Affiliations
St. Petersburg Institute for Informatics and Automation of the Russian Academy of Sciences, St. Petersburg Federal Research Center of the Russian Academy of Sciences, 39, 14th Line V.O., St. Petersburg 199178, Russian Federation
|