Abstract
Purpose
The practical purpose of this research is to propose a candidate for post-quantum signature standard that is free of significant drawback of the finalists of the NIST world competition, which consists in the large size of the signature and the public key. The practical purpose is to propose a fundamentally new method for development of algebraic digital signature algorithms.
Design/methodology/approach
The proposed method is distinguished by the use of two different finite commutative associative algebras as a single algebraic support of the digital signature scheme and setting two different verification equation for a single signature. A single public key is computed as the first and the second public keys, elements of which are computed exponentiating two different generators of cyclic groups in each of the algebras.
Findings
Additionally, a scalar multiplication by a private integer is performed as final step of calculation of every element of the public key. The same powers and the same scalar values are used to compute the first and the second public keys by the same mathematic formulas. Due to such design, the said generators are kept in secret, providing resistance to quantum attacks. Two new finite commutative associative algebras, multiplicative group of which possesses four-dimensional cyclicity, have been proposed as a suitable algebraic support.
Originality/value
The introduced method is novel and includes new techniques for designing algebraic signature schemes that resist quantum attacks. On its base, a new practical post-quantum signature scheme with relatively small size of signature and public key is developed.
Keywords
Citation
Moldovyan, N.A. and Moldovyan, D.N. (2025), "A novel method for developing post-quantum cryptoschemes and a practical signature algorithm", Applied Computing and Informatics, Vol. 21 No. 1/2, pp. 90-100. https://doi.org/10.1108/ACI-02-2021-0036
Publisher
:Emerald Publishing Limited
Copyright © 2021, Nikolay Andreevich Moldovyan and Dmitriy Nikolaevich Moldovyan
License
Published in Applied Computing and Informatics. Published by Emerald Publishing Limited. This article is published under the Creative Commons Attribution (CC BY 4.0) licence. Anyone may reproduce, distribute, translate and create derivative works of this article (for both commercial and non-commercial purposes), subject to full attribution to the original publication and authors. The full terms of this licence may be seen at http://creativecommons.org/licences/by/4.0/legalcode
1. Introduction
Public-key сryptographic algorithms and protocols are of great importance in modern practical informatics and computer science. They provide basic primitives for solving fundamental problems of information security and are a source of new information technologies. In the last three decades, most developed countries have used cryptographic standards for public key distribution and digital signature, based on the computational complexity of the discrete logarithm problem (DLP) and the factorization problem (FP). However, both of these problems can be effectively solved on a quantum computer [1–3], the appearance of which is predicted in the fairly near future.
The implementation of this expectation will mean that the specified cryptographic standards cease to be secure. Therefore, the development of practical public-key post-quantum cryptoschemes that resist quantum attacks (attacks with using quantum and ordinary computers) attracts much attention of the cryptographic community [4]. A notable event was NIST's announcement of a worldwide competition to develop candidates for post-quantum public-key standards for (1) digital signature algorithms and (2) public-key encryption and key-establishment algorithms during 2017–2024 [5].
At the moment, 3 signature schemes and 4 public-key encryption and key-establishment algorithms have been selected as finalists out of 69 initially submitted candidates for post-quantum public-key standards [6]. However, the former have a significant drawback for a wide practical application, which consists in the large size of the signature and the public key.
The article is organized as follows. In Section 2, different approaches to design of post-quantum public key cryptoschemes are mentioned. Section 3 describes the overall idea of the proposed method for development of the post-quantum signature algorithm. Section 4 presents a new algebraic post-quantum signature scheme. Next Section 5 provides preliminary security estimation. Section 6 concludes the paper.
2. Preliminaries
For the development of post-quantum public-key cryptographic algorithms and protocols one should use computationally difficult problems that are different from the FP and DLP, since polynomial algorithms for solving FP and DLP on a quantum computer are known [1–3]. Considerable attention of the developers is paid to the development of cryptoschemes on algebras [6, 7], on Boolean functions [8], on lattices [9] and on linear codes [10, 11].
One of attractive approaches to the development of post-quantum signature algorithm relates to exploiting computational difficulty of the so-called hidden discrete logarithm problem (HDLP) defined usually in non-commutative finite associative algebras (FAAs). Different forms of the HDLP were used to develop signature algorithms on non-commutative FAAs [7, 12, 13]. For the first time, a HDLP-based signature algorithm on a commutative FAA was proposed in [14].
A common feature of the HDLP-based signature algorithms is the use of exponentiation operations in a hidden cyclic group, but the masking mechanisms used to hide this group are fundamentally different when using non-commutative and commutative algebras. More extensive possibilities for setting various forms of the HDLP in non-commutative FAAs are associated with the possibility of setting automorphisms and homomorphisms in non-commutative algebras, which can be used as masking operations. The latter is not possible when using commutative FAAs and other masking mechanisms should be proposed when developing a HDLP-based signature algorithm on commutative algebras.
In this paper, we consider a method for designing post-quantum signature schemes on commutative FAAs characterized in exploiting a novel masking mechanism to hide cyclic groups in which the base exponentiation operations are performed. The main requirement to the FAAs suitable for their using as algebraic support for implementing the introduced method is that their multiplicative group possesses multidimensional cyclicity.
Consider the setting of FAAs. Suppose in a finite m-dimensional vector space over a finite field (ground field GF(p) or extension of the binary field GF(2n)), in which a vector multiplication operation is defined additionally to the scalar multiplication and addition operations. If the vector multiplication is distributive at the left and at the right relatively the addition operation, then the said vector space is called m-dimensional algebra. A vector A is presented as an ordered set of its coordinates:
Usually, the multiplication of two vectors
The use of the exponentiation operation in the procedures of public key computation and of signature generation and verification implies the possibility of using a fast exponentiation algorithm. To ensure the correct operation of the latter, the associativity condition of the multiplication operation must be met. Formula (1) shows that one can define the associative vector multiplication operation imposing the following conditions on the BVMT:
To construct an algebra suitable for our purpose, we used a unified method [15] for defining algebras of arbitrary even dimensions, which results in non-commutative/commutative FAAs of the dimensions m ≥ 6/m = 2, 4. From a single general formula introduced in [15] for case m = 4 we get the following formula for generating a BVMT:
The vector E = (1,0,0,0) is the unit of the commutative FAA set by Table 1a.
The vector E = (0,0,1,0) is the unit of the commutative FAA set by Table 1b.
Each of the defined commutative FAA contains a multiplicative group possessing
To find the value of the order
The main determinant of the system (5) is
If
First, we will calculate the number
If the structural constant
For the case a1 ≠ 0, substituting the value
For the case a1 = 0 we have a2a3 = 0. If a2 = 0, then
In sum, for the considered cases one gets
If the structural constant
Since the structural constant
These cases define four conditions for the values of coordinates (a0, a1, a2, a3) of non-invertible vectors, which are presented in Table 2 together with the number of vectors coordinates of which relates to a fixed condition.
Totally, number of non-invertible vectors is equal to
Therefore, one gets
In a similar way, we can prove that the Propositions 3 and 4 are also valid for the case of the second commutative FAA, in which the vector multiplication operation is defined by Table 1b.
It is easy to see that the multiplicative group of each of the algebras is generated by a group basis containing two (four) vectors of order ω = p2 − 1 (ω = p − 1), if the value of
Suppose the multiplicative group of the first FAA is generated by a basis
Let us make the following remark about the logarithm of the scalar vector, which is essential for understanding the method of constructing post-quantum digital signature schemes described below. Selection of a random basis leads to a random value of the logarithm of the scalar vector S = E
3. Proposed method
The method is based on the idea of selecting random bases of primary groups of order 2 in the first and second algebras, and then calculating the first and second public keys as a product of powers of the elements of the corresponding basis, the same powers being used to calculate corresponding element of the first and second public key. The latter is to provide possibility to generate a single digital signature, for which one verification equation (written for the first public key) and another verification equation (written for the second public key) are satisfied.
Such doubling of the verification equation should force a potential signature forger to calculate the same values of logarithms of the corresponding public-key elements. However, the fact that the corresponding public-key elements are computed using the same powers of the exponentiation operation can be potentially used to compute bases over which the logarithms of the corresponding public-key elements are equal.
Therefore, the technique of scalar multiplication is used. This technique consists in including an additional scalar multiplication of the public-key elements. Different scalar multipliers are used for computing different element of the same public key, but the same scalar multiplier is used for computing corresponding elements of the first and second public keys. Due to scalar multiplications the logarithms of the corresponding elements of public keys (over randomly selected bases in the first and second FAAs) become different. The multiplications by scalars acts as masking operations that hide the 2-dimensional cyclicity groups set by the initially selected bases in each of the commutative FAA.
Introducing an additional signature element we provide correctness of the signature scheme the doubled verification equation complemented with the technique of scalar multiplication.
4. Post-quantum signature scheme
An arbitrary vector G of order q generates a cyclic group including q − 1 vectors of the order q. The multiplicative group of each of the FAAs includes q4 − 1 different vectors of the order q. Therefore, with probability ≈1 − q−3 a random vector Q of the order q sets a basis <G, Q> of primary group of order q2, including q2 − 1 different vectors of the order q. Then with probability ≈1 − q−2 a random vector V of the order q sets a basis <G, Q, V> of primary group of order q3, including q3 − 1 different vectors of the order q. Then with probability ≈1 − q−1 a random vector W of the order q sets a basis <G, Q, V, W> of primary group of order q4. Thus, most likely is the case, when two (four) random vectors of order q set a basis of a primary group of order q2 (q4), which has two-dimensional (four-dimensional) cyclicity. However there is a probability that two (four) random vectors set a generator system of the primary group of order q (≤q3). The latter probability can be called a failure probability.
In each of the commutative FAAs used as algebraic support of the developed signature algorithm, the failure probability is negligibly small, i.e., equals to ≈ q−3 (≈q−1) when setting the basis of two-dimensional (four-dimensional) cyclicity by selection of two (four) random vectors of order q.
Calculation of the first and second public keys that compose a single public key is performed as follows:
Generate two uniformly random vectors G and Q of order q in the first FAA and two uniformly random vectors D and H of order q in the second FAA.
Generate at random three 256-bit integers y1 < q, y2 < q, and
< p, where is a primitive element modulo p, and calculate the first element of the first public key and the first element of the second public key .Generate at random three 256-bit integers z1 < q, z2 < q, and
< p, where is a primitive element modulo p, and calculate the second element of the first public key and the second element of the second public key .Generate at random two 256-bit integers u < q and
< p, where is a primitive element modulo p, and calculate the third element of the first public key U1 = Gu and the third element of the second public key U2 = Du .
This algorithm outputs the first 384-byte public key (Y1, Z1, U1) and the second 384-byte public key (Y1, Z1, U1). These two key compose a single 768-byte public key. The private key represents the set of eight 32-byte integers (y1, y2,
To generate (and then verify) a signature to an electronic document M, a secure 256-bit hash function fH is supposed to be used.
4.1 Signature generation algorithm
Generate tree uniformly random integers k < q, t < q, and ρ < p.
Calculate the vector R1 = GkQtρ.
Calculate the vector R2 = DkHtρ.
Calculate the first signature element e that is a hash-function value calculated from the document M, to which the vectors R1 and R2 are concatenated: e = fH (M, R1, R2).
Calculate the second signature element s:
(t − y2e) mod q.Calculate the third signature element d: d = u−1(k − y1e − z1s) mod q.
Calculate the fourth signature element
: = ρ −e −s −d mod p.
The signature represents the following set of four 32-byte integers (e, s, d,
4.2 The signature verification algorithm
Calculate the vector
σ.Calculate the vector
σ.Compute the hash-function value from the document M to which the vectors
and are concatenated: e* = fH(M, , ).If e* = e, then the signature is genuine, else the signature is rejected.
Computational complexity of the signature verification procedure can be roughly estimate as six exponentiations in the used four-dimensional FAAs or as ≈37250 multiplications in GF(p).
4.3 Signature scheme correctness proof
Consider a signature (e, s, d,
The equality
5. Discussion
We refer the developed digital signature algorithm to type of HDLP-based signature schemes, since the vectors belonging to some primary two-dimensional cyclicity group, which is hidden in a primary four-dimensional cyclicity group, are used in calculating the elements of the public key and generating the signature. In our case, the masking operations are scalar multiplications, which is a new technique for constructing HDLP-based signature schemes.
The technique of doubling the verification equation when designing a signature scheme was previously used in [12, 14], but in the proposed method it is extended to the case of using two different algebras as a single algebraic carrier of the signature scheme. At the same time, it has a new purpose, which is to provide binding of public key elements to a fixed hidden group in each of the used algebras.
The last point is important to ensure that the signature scheme is resistant to signature forgery by a person who has the ability to efficiently calculate a four-dimensional algorithm using a new type of quantum computer that may appear in the future. The resistance of the proposed algorithm to the attacks of the specified alleged person is due to the fact that the signature forger does not know the basis over which it is required to calculate four-dimensional logarithms.
As a substantiation of resistance to quantum attacks, it should be noted that the proposed signature scheme satisfies the general criterion of post-quantum security used to develop HDLP-based signature schemes described in the papers [12–14]. The mentioned criterion is formulated as follows [12]: “Based on the public parameters of the signature scheme, the construction of a periodic function containing a period with the length depending on the discrete logarithm value should be a computationally intractable task.” The fulfillment of this criterion in the developed signature scheme is ensured by the fact that the elements of the first (second) public key form the basis of a primary group of the order q3 in the first (second) algebra used as an algebraic carrier, therefore, all possible products
Our preliminary assessment of the security of the developed signature scheme shows that using a 256-bit value of the prime number q provides 256-bit security to signature forgery. For a more reasonable choice of parameters, it is necessary to perform a more detailed and comprehensive security study, which is an independent task of a separate work.
Using a non-optimized implementation on a common laptop computer with microprocessor Intel Core i7-6567U at 3.3 GHz, the developed HDLP-based signature generation algorithm outputs about 1,500 signatures per second. Its performance can be increased significantly when optimizing the software implementation, however the latter item is outside the scope of this paper. Using the said implementation, correctness of the introduced signature scheme had been experimentally demonstrated.
At present the NIST world competition [4] for the development of post-quantum public-key cryptosystems has entered the third stage [5]. The finalists in the category of post-quantum digital signatures were Falcon [17] and Crystals-Dilithium [16], and Rainbow [18]. It is interesting to compare the proposed signature scheme with the finalists, with other HDLP-based signatures [12, 14], and with 2048-bit RSA signature algorithm [19]. Table 3 presents a rough comparison which uses the published results of comparing the performance of the finalists with each other and with the algorithm RSA-2048. To get performance comparison of the proposed signature scheme with RSA-2048 we had taken into account that the private (public) exponent in RSA-2048 has length about 2048 (256) bits and computational difficulty of one multiplication modulo a 2048-bit can be roughly estimated as 64 multiplications modulo a 257-bit number.
This comparison shows that the proposed signature algorithm has significantly smaller sizes of the public key and signature relative to the finalists of the NIST competition. The exception is the algorithm Rainbow with the minimum signature size (64 bytes), but it has an excessively large public key size (150,000 bytes). At the same time, the above comparison does not take into account the possibility of using optimization mechanisms for specific implementations of the developed signature algorithm, the use of which will increase the performance of both the signature generation procedure and the signature verification procedure by a factor of 3–5.
The main advantage of the proposed algorithm compared to the finalists of the NIST competition is the smaller size of the public key and the signature. However, the finalists have successfully past a long time term of security testing and the proposed algorithm show potential possibility to reduce significantly the size of signature (by a factor of ≈10) and of public key (by a factor of ≈2), independent detailed security study of the introduced signature scheme is needed though.
Nevertheless, the finalists have successfully passed long security testing. Like, the recently introduced HDLP-based post-quantum signature schemes [12, 14], the proposed algorithm only show a potential possibility to significantly reduce the size of the signature and public key. If further independent security investigation confirm the authors' expectations, then we can say that there is a way to solve the said important practical problem. The reader can make a significant contribution to clarifying this issue.
As compared with the analogous [12, 14], the proposed signature scheme provides shorter signatures, a bit higher signature generation performance and a bit lower signature verification performance.
6. Conclusion
A fundamentally new design method and a practical HDLP-based post-quantum digital signature algorithm has been introduced. The proposed method and signature scheme are quite simple to understand. One can suppose that the proposed method opens up the possibility of developing a new class of practical post-quantum signature algorithms. The latter represents a significant interest in the light of the widely conducted researches on the development of candidates for post-quantum digital signature standards.
Defining associative vector multiplication operation in the first (a) and second (b) FAAs used as algebraic support (
![]() |
Number of non-invertible vectors relating to every of four conditions
Condition | # of different combinations of coordinates (a0, a1, a2, a3) |
---|---|
p2 including (0, 0, 0, 0) | |
p2 including (0, 0, 0, 0) | |
2p (p − 1)2 | |
2p (p − 1)2 |
Comparison with some known post-quantum signature schemes
Signature scheme | Signature size (byte) | Public key size (byte) | Signature generation performance (a.u.) | Signature verification performance (a.u.) |
---|---|---|---|---|
Falcon [17 | 1,280 | 1,793 | 50 | 25 |
Dilithium [16 | 2,701 | 1,472 | 15 | 2 |
Rainbow | 64 | 150,000 | – | – |
HDLP-based [12 | 192 | 768 | 50 | 80 |
HDLP-based [14 | 192 | 512 | 40 | 80 |
2048-bit RSA | 256 | 288 | 10 | 90 |
Proposed | 128 | 768 | 70 | 50 |
References
1.Shor PW. Polynomial-time algorithms for prime factorization and discrete logarithms on quantum computer. SIAM J Comput. 1997; 26: 1484-509.
2.Ekert A, Jozsa R. Quantum computation and Shor's factoring algorithm. Rev Mod Phys. 1996; 68: 733-52.
3.Smolin JA, Smith G, Vargo A. Oversimplifying quantum factoring. Nature. 2013; 499(7457): 163-65.
4.Federal Register. Announcing request for nominations for public-key post-quantum cryptographic algorithms. Available from: https://www.gpo.gov/fdsys/pkg/FR-2016-12-20/pdf/2016-30615.pdf (accessed 13 February 2021).
5.Round 3 Finalists. Public-key encryption and key-establishment algorithms. Available from: https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions (accessed 13 February 2021).
6.Kuzmin AS, Markov VT, Mikhalev AA, Mikhalev AV, Nechaev AA. Cryptographic algorithms on groups and algebras. J Math Sci. 2017; 223(5): 629-41.
7.Moldovyan NA, Moldovyan AA. Finite non-commutative associative algebras as carriers of hidden Discrete logarithm problem. Bull South Ural State Univ Ser Math Model Program Comp Softw. 2019; 12(1): 66-81. doi: 10.14529/mmp190106.
8.Agibalov GP. ElGamal cryptosystems on Boolean functions. Prikl Diskr Mat. 2018(42): 57-65. doi: 10.17223/20710410/42/4.
9.Hoffstein J, Pipher J, Schanck JM, Silverman JH, Whyte W, Zhang Z. Choosing parameters for NTRU encrypt. Cryptographers' Track at the RSA Conference − CTA-RSA 2017. Springer LNCS. 2017; 10159: 3-18.
10.Alamelou Q, Blazy O, Cauchie S, Gaborit P. A code-based group signature scheme. Des Codes Cryptogr. 2017; 82(1−2): 469-93.
11.Kosolapov YV, Turchenko OY. On the construction of a semantically secure modification of the McEliece cryptosystem. Prikl Diskr Mat. 2019(45): 33-43. doi 10.17223/20710410/45/4.
12.Moldovyan NA, Moldovyan AA. Candidate for practical post-quantum signature scheme. Vestnik Saint Petersburg Univ Appl Math Comp Sci Control Process. 2020; 16(4): 455-61. doi: 10.21638/11701/spbu10.2020.410.
13.Moldovyan DN, Moldovyan AA, Moldovyan NA. An enhanced version of the hidden discrete logarithm problem and its algebraic support. Quasigr Relat Syst. 2020; 28(2): 269-84. Available from: http://www.quasigroups.eu/.
14.Moldovyan DN, Moldovyan AA, Moldovyan NA. A novel method for development of post-quantum digital signature schemes. Informatsionno-upravliaiushchie sistemy [Inform Control Syst], 2020(6): 21-29. doi: 10.31799/1684-8853-2020-6-21-29.
15.Moldovyan NA. A unified method for setting finite non-commutative associative algebras and their properties. Quasigr Relat Syst. 2018; 26(2): 263-70. http://www.quasigroups.eu/.
16.Ducas L, Kiltz E, Lepoint T, Lyubashevsky V, Schwabe P, Seiler G, Stehlé D. CRYSTALS-Dilithium: a lattice-based Digital signature scheme. Available from: https://eprint.iacr.org/2017/633.pdf https://pq-crystals.org/dilithium/index.shtml (accessed 15 February 2021).
17.Fast-Fourier lattice-based compact signatures over NTRU. https://falcon-sign.info/ (accessed 15 February 2021).
18.Ding J, Schmidt D. Rainbow, a new multivariable polynomial signature scheme. In: Ioannidis J, Keromytis A, Yung M (Eds) Applied cryptography and network security. ACNS 2005. Lecture notes in computer science. Springer, Berlin, Heidelberg. 2005; 3531: 164-175.
19.Rivest RL, Shamir A, Adleman LM. A method for obtaining digital signatures and public key cryptosystems. Commun ACM. 1978; 21: 120-26.