A novel method for developing post-quantum cryptoschemes and a practical signature algorithm

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.

Citation

Moldovyan, N.A. and Moldovyan, D.N. (2021), "A novel method for developing post-quantum cryptoschemes and a practical signature algorithm", Applied Computing and Informatics, Vol. ahead-of-print No. ahead-of-print. https://doi.org/10.1108/ACI-02-2021-0036

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(2ⁿ)), 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: A=(a0, a1, …, am−1) or as a sum of its components: A=a0e0+a1e1+ ⋯+am−1em−1, where ei(i=0, 1, …, m−1) are formal basis vectors.

Usually, the multiplication of two vectors A=∑i=0m−1aiei and B=∑j=0m−1bjej is defined by the following formula:

(1)AB=∑i,j=0m−1aibjeiej,

where the coordinates ai and bi are multiplied as elements of the finite field, for example GF(p), and every of the products eiej is to be substituted by an one-component vector λek indicated in a cell in the intersection of the ith row and jth column of so called basis vector multiplication table (BVMT), for example, see Table 1. The value λ∈ GF(p) is called structural coefficient.

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:

(2)(eiej)ek=ei(ejek)

for all possible triples of basis vectors (ei,ej,ek).

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:

(3)eiej={ei+jmod4, if imod2=0; ei−jmod4, if imod2=1, jmod2=0;λei−jmod4, if imod2=1, jmod2=1.

that defines Table 1a. To construct the second four-dimensional commutative FAA, we propose the following formula:

(4)eiej={λei+j−2mod4, if imod2=0, jmod2=0;ei+j−2mod4, if imod2=0, jmod2=1;ei−j+2mod4, if imod2=1. 

that defines Table 1b. It is easy to show the latter formula (3) sets the satisfiability of condition (2). The validity of the following two statements can be easily verified:

Proposition 1.

The vector E = (1,0,0,0) is the unit of the commutative FAA set by Table 1a.

Proposition 2.

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 μ-dimensional cyclicity with μ = 2, if λ is a quadratic non-residue modulo p, or μ = 4, if λ is a quadratic residue. Notion of the multidimensional cyclicity was introduced in [16], namely, a finite commutative group the minimum generator system (group basis) of which includes μ group elements of the same order is called a μ-dimensional cyclicity group (a group possessing μ-dimensional cyclicity).

To find the value of the order Ω of multiplicative group one is to calculate the number of invertible elements in a FAA, which is equal to Ω. Consider the first FAA. For an invertible vector A vector the vector equation AX = E has a unique solution that is inverses of the vector A and is denoted as A⁻¹. To obtain invertibility condition one can reduce the said vector equation to the following system of four linear equations with the unknown integers x₀, x₁, x₂, and x₃ as the coordinates of the vector X:

(5){a0x0+λa1x1+a2x2+λa3x3=1;a0x1+a1x0+a2x3+a3x2=0;a0x2+λa1x3+a2x0+λa3x1=0;a0x3+a1x2+a2x1+a3x0=0.

The main determinant of the system (5) is

Δ=|a0λa1a2λa3a1a0a3a2a2λa3a0λa1a3a2a1a0|=a0|a0a3a2λa3a0λa1a2a1a0|−λa1|a1a3a2a2a0λa1a3a1a0|+ a2|a1a0a2a2λa3λa1a3a2a0|−λa3|a1a0a3a2λa3a0a3a2a1|= a0(a0(a02−λa12)−a3(λa0a3−λa1a2)+a2(λa1a3−a0a2))−− λa1(a1(a02−λa12)−a3(a0a2−λa1a3)+a2(a1a2−a0a3))++ a2(a1(λa0a3−λa1a2)−a0(a0a2−λa1a3)+a2(a22−λa32))−− λa3(a1(λa1a3−a0a2)−a0(a1a2−a0a3)+a3(a22−λa32))=…== (a02+λa12)2−4λa02a12+(a22+λa32)2−4λa22a32−− 2(a02+λa12)(a22+λa32)+8λa0a1a2a3=…== (a02+λa12−a22−λa32)2−4λ(a0a1−a2a3)2.

If Δ ≠ 0, then the system (5) has unique solution and we have the following invertibility condition:

(6)(a02+λa12−a22−λa32)2−4λ(a0a1−a2a3)2≠0

First, we will calculate the number η of non-invertible vectors and the compute the multiplicative group order as Ω = p⁴ − η. Taking into account the condition (6) we get the following non-invertibility condition

(7)(a02+λa12−a22−λa32)2=4λ(a0a1−a2a3)2.

Proposition 3.

If the structural constant λ is equal to a quadratic non-residue modulo p, then the number of non-invertible vectors in the commutative FAA set by Table 1a equals to η = 2p² − 1 and the multiplicative group order equals to Ω = (p² − 1)².

Proof.

Formula (7) sets the following condition:

{a02+λa12−a22−λa32=0;a0a1−a2a3=0.

For the case a₁ ≠ 0, substituting the value a0=a2a3a1−1 in the first equality we have a22(a32−a12)=λa12(a32−a12). from the latter formula one can see that in this case we have 2p² − 2p non-invertible vectors.

For the case a₁ = 0 we have a₂a₃ = 0. If a₂ = 0, then a02=λa32⇒a0=a3=0 (this gives one more non-invertible vector, namely, the vector (0,0,0,0). If a₃ = 0, then a02=a22⇒a0=±a2 and we have 2(p − 1) additional non-invertible vectors. If a₃ = 0 and a₂ = 0, then a₀ = 0. The latter gives the vector (0,0,0,0).

In sum, for the considered cases one gets η = 2p² − 2p + 2(p − 1) + 1 = 2p² − 1. Therefore, Ω = p⁴ − η = (p² − 1)². Proposition 3 is proven.

Proposition 4.

If the structural constant λ is equal to a quadratic non-residue modulo p, then the number of non-invertible vectors in the commutative FAA set by Table 1a equals to η = 4p³ − 6p² + 4p² − 1 and the multiplicative group order equals to Ω = (p − 1)⁴.

Proof.

Since the structural constant λ is a quadratic residue, formula (7) defines the following two cases:

1. a02+λa12−a22−λa32=2λ(a0a1−a2a3)⇒(a0−λa1)2=(a2−λa3)2⇒ ⇒a0−λa1=±(a2−λa3);

2. a02+λa12−a22−λa32=−2λ(a0a1−a2a3)⇒(a0+λa1)2=(a2+λa3)2⇒ ⇒a0+λa1=±(a2+λa3).

These cases define four conditions for the values of coordinates (a₀, a₁, a₂, a₃) 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

η=p2+p2+2p(p−1)2+2p(p−1)2=4p3−6p2+4p−1.

Therefore, one gets Ω = p⁴ − η = (p − 1)⁴. Proposition 4 is proven.

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 ω = p² − 1 (ω = p − 1), if the value of λ is a quadratic non-residue (residue) modulo p. When developing a digital signature scheme it is assumed that the structural constant is equal to a residue and each of the considered commutative FAAs is defined over the same field GF(p) with characteristic equal to a prime p = 2q + 1, where q is a 256-bit prime.

Suppose the multiplicative group of the first FAA is generated by a basis <B1′,B2′,B3′,B4′>. Then the following four vectors B1=B1′2, B2=B2′2, B3=B3′2, and B4=B4′2 compose a basis of a primary group of order q⁴, which contains q + 1 cyclic groups of order q. Each element V of the said primary group can be uniquely represented as a product of some powers of the elements of the basis <B1, B2, B3, B4>: V=B1i, B2j, B3k, B4h, where i, j, k, h = 0, 1, 2, …, q − 1. The power vector (i, j, k, h) can be called four-dimensional logarithm (or simply logarithm) of the vector V over the basis <B1, B2, B3, B4>. Evidently the value of the logarithm of the vector V depends on the fixed basis, i. e., for different bases the logarithm of a fixed vector V has different values.

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α, where α is a scalar multiplier. Therefore, fixing at random a basis in the first FAA and a basis in the second FAA for the fixed scalar vector S one gets different values of log S.

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 q⁴ − 1 different vectors of the order q. Therefore, with probability ≈1 − q⁻³ a random vector Q of the order q sets a basis <G, Q> of primary group of order q², including q² − 1 different vectors of the order q. Then with probability ≈1 − q⁻² a random vector V of the order q sets a basis <G, Q, V> of primary group of order q³, including q³ − 1 different vectors of the order q. Then with probability ≈1 − q⁻¹ a random vector W of the order q sets a basis <G, Q, V, W> of primary group of order q⁴. Thus, most likely is the case, when two (four) random vectors of order q set a basis of a primary group of order q² (q⁴), 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 (≤q³). 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⁻³ (≈q⁻¹) 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:

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

2. Generate at random three 256-bit integers y₁ < q, y₂ < q, and α < p, where α is a primitive element modulo p, and calculate the first element of the first public key Y1=Gy1Qy2α and the first element of the second public key Y2=Dy1Hy2α.

3. Generate at random three 256-bit integers z₁ < q, z₂ < q, and β < p, where β is a primitive element modulo p, and calculate the second element of the first public key Z1=Gz1Qz2β and the second element of the second public key Z2=Dz1Hz2β.

4. 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 U₁ = G^uγ and the third element of the second public key U₂ = D^uγ.

This algorithm outputs the first 384-byte public key (Y₁, Z₁, U₁) and the second 384-byte public key (Y₁, Z₁, U₁). These two key compose a single 768-byte public key. The private key represents the set of eight 32-byte integers (y₁, y₂, α, z₁, z₂, β, u, γ) and the set of four 128-byte vectors (G, Q, D, H). Total size of the private key is equal to 768 bytes.

To generate (and then verify) a signature to an electronic document M, a secure 256-bit hash function f_H is supposed to be used.

4.1 Signature generation algorithm

1. Generate tree uniformly random integers k < q, t < q, and ρ < p.

2. Calculate the vector R₁ = G^kQ^tρ.

3. Calculate the vector R₂ = D^kH^tρ.

4. Calculate the first signature element e that is a hash-function value calculated from the document M, to which the vectors R₁ and R₂ are concatenated: e = f_H (M, R₁, R₂).

5. Calculate the second signature element s: s=z2−1 (t − y₂e) mod q.

6. Calculate the third signature element d: d = u⁻¹(k − y₁e − z₁s) mod q.

7. Calculate the fourth signature element σ: σ = ρα^−eβ^−sγ^−d mod p.

The signature represents the following set of four 32-byte integers (e, s, d, σ) with total size equal to 128 bytes. Computational complexity of the signature generation procedure can be roughly estimate as four exponentiations in the used four-dimensional FAAs and three exponentiations in GF(p) or as ≈26000 multiplications in GF(p).

4.2 The signature verification algorithm

1. Calculate the vector R1∗=Y1eZ1sU1dσ.

2. Calculate the vector R2∗=Y2eZ2sU2dσ.

3. Compute the hash-function value from the document M to which the vectors R1∗ and R2∗ are concatenated: e* = f_H(M, R1∗, R2∗).

4. 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, σ) that has been computed in full correspondence with the signature generation procedure. Suppose the signature (e, s, d, σ) is submitted to the input of the verification procedure, then we have the following proof of the correctness of the introduced digital signature algorithm:

R1∗=Y1eZ1sU1dσ==Gey1Qey2αeGsz1Qsz2βsGduγdσ==Gey1+sz1+duQey2+sz2αeβsγdρα−eβ−sγ−d==Gey1+sz1+(k−ey1−sz1)Qey2+(t−ey2)ρ==GkQtρ=R1;

R2∗=Y2eZ2sU2dσ==Dey1Hey2αeDsz1Hsz2βsDduγdσ==Dey1+sz1+duHey2+sz2αeβsγdρα−eβ−sγ−d==Dey1+sz1+(k−ey1−sz1)Hey2+(t−ey2)ρ==DkHtρ=R2;{R1∗=R1;R2∗=R2}⇒e*=e

The equality e∗=e means that the input digital signature is accepted as a genuine signature, i.e. the developed signature scheme performs correctly.

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 q³ in the first (second) algebra used as an algebraic carrier, therefore, all possible products Y1iZ1jU1k in the first FAA and Y2iZ2jU2k the second FAA for i, j, k = 0, 1, 2 …, q − 1 run through all the elements of the said primary group and periodic functions F₁ (i,j,k)=Y1iZ1jU1k and F₂ (i,j,k)=Y2iZ2jU2k contain periods having the lengths (aq, bq, cq), where a, b, c ∈ {0, 1}, i.e. these two functions do not contain periods associated with secret values y₁, y₂, α, z₁, z₂, β, u, γ. Thus, the Shor algorithm [1] based on efficiency of a quantum computer to find period length of periodic functions set in a finite cyclic group and possible future quantum algorithm for periodic function set in commutative groups of general type are not directly applicable for breaking the proposed signature scheme.

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.

Table 1

Defining associative vector multiplication operation in the first (a) and second (b) FAAs used as algebraic support (λ ≠ 0)

Table 2

Number of non-invertible vectors relating to every of four conditions

Condition	# of different combinations of coordinates (a0, a1, a2, a3)
a0−λa1=a2−λa3=0	p2 including (0, 0, 0, 0)
a0+λa1=a2+λa3=0	p2 including (0, 0, 0, 0)
a0−λa1=±(a2−λa3)≠0	2p (p − 1)2
a0+λa1=±(a2+λa3)≠0	2p (p − 1)2

Table 3

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