Introduction

M ultilinear maps 1 that provide many applications in cryptography, was proposed as an extension of bilinear maps. Unlike bilinear maps, which are known to be constructed using pairing of elliptic curves, there was no method to construct a multilinear maps before the year 2013. This long-standing open problem was finally solved by Garg et al. 2. They proposed the concept of graded encoding schemes, which is an approximate construction of multilinear maps. In their work, ideal lattices are used to build an instantiation of graded encoding schemes which is called GGH13.

Graded encoding schemes are one of the most important cryptographic tools that provide many applications in cryptography such as secret sharing scheme 3, witness encryption 4, multipartite key exchange 2, functional encryption 5, obfuscation 67, aggregate signature scheme 8 and so on. In this paper, we offer another application of graded encoding schemes in signature schemes.

Digital signature schemes 91011 are useful cryptographic primitives in practice. They provide many uses for data security in a variety of applications, including authenticity and non-repudiation, securing software updates, the use in secure communication protocols SSL/TLS and more. In one-time digital signature schemes the signer is limited to sign a single message 12. These schemes are important cryptographic primitives that used as the core of the design of many-time digital signature schemes. One-time signature schemes have other important applications like digital signatures with forward security property 1314, network routing protocols 15 and so on.

So far, several techniques have been presented for constructing one-time digital signature schemes, one of the most interesting of which is the Winternitz one-time signature (WOTS) scheme 16. One-time signature schemes designed using this technique play important roles in the design of both stateless and stateful many-time signature schemes 171819. For example, if a Merkle signature scheme is built using a WOTS type signature scheme, there is no need to put the public verification key of WOTS scheme in the signature 14. In addition, in WOTS type signature schemes, it is possible to make a trade-off between the runtime and the size of signature 202122.

Using the concept of "function chain", we can give a good description of WOTS scheme. A function chain, using a function (family), produces a chain of values starting from a given point. The main idea of WOTS scheme is the use of a limited number of function chains, that are all calculated starting from random values. These values are in fact the private signing key of WOTS scheme. The public verification key is also the final values of each function chain. Finally, to calculate the signature, the message is mapped to one intermediate value of each chain.

Related Work

Along the years, several different versions of WOTS scheme have been presented for various purposes. The main idea of the WOTS scheme was first presented in 16. Using this basic idea, the one-time digital signature schemes 2324 were designed using an undetectable, collision resistant hash function. Afterwards, a WOTS type signature scheme was introduced that achieve existential unforgeability under adaptive chosen message attacks (EU-CMA) security using a pseudorandom function family 25.

Under the name WOTS + , Hülsing 26 later introduced a WOTS type signature scheme based on minimal security requirements i.e. undetectable, secondpreimage resistant, one-way hash functions. In this scheme, using the bitmasks, the need for collision resistant hash functions has been resolved. The security proof of WOTS + is tight, which allows the signature size to be reduced compared to the previous WOTS type signature schemes. Therefore, WOTS + has been given more attention than previous WOTS type signature schemes. For example, the one-time signature which is used in the structure of stateless many-time signature schemes SPHINCS 19 and SPHINCS + 22 is WOTS + . The variations of WOTS scheme that have been described so far are all vulnerable to multitarget attacks. More precisely, if an adversary has several targets to attack them, then the probability of being able to attack at least one of them is more than he can attack exactly one. There is another WOTS type signature scheme which is referred to as WOTS-T 20. This scheme is considered as an improved version of WOTS + that resists against multi-target attacks. The major difference between WOTS-T and WOTS + , which makes WOTS-T resistant to multitarget attacks, is that it uses an addressing scheme. Using this, a new bitmask is produced every time the used hash function is called.

As discussed above, using the concept of function chain, there exists a good description of WOTS scheme. Considering this fact, the difference between all WOTS type signature schemes is in the method that the used function chain is constructed. In the function chain used in each of the WOTS type signature schemes, a function has been used that must be repeated a certain number of times in order to generate the intermediate values of the chains. The total number of production of each intermediate value in the key generation, signature and verification algorithms of this signature schemes is two. Thus, reducing the number of required intermediate values, can reduce the number of operations required for these algorithms.

In this work, we propose WOTS-GES, a new variant of the Winternitz one time signature scheme in which the need for computing all of the intermediate values of the chains is eliminated. More precisely, in each key generation, signature and verification algorithms of the proposed signature scheme, it is necessary to calculate only one intermediate value in each function chain. This significantly reduces the number of required operations needed to calculate these algorithms. To achieve this results, we have used the concept of "leveled" multilinear maps which is also referred to as graded encoding schemes. We also show how the used graded encoding scheme can be instantiated using GGH13.

The rest of the paper is as follows. In Section 2, we review the required concepts. In Section 3, we give description of the generic WOTS scheme. Section 4, describes WOTS-GES based on graded encoding schemes. The security of WOTS-GES is proposed in Section 5. In Section 6, the instantiation of WOTS-GES using GGH13 is discussed and finally in Section 7, conclusions are provided.

Preliminaries

This section reviews some required concepts which are used throughout this paper. Most of the content ISeCure in this section is devoted to graded encoding schemes. But first of all, we provide a simple definition of multilinear maps 1. Definition 2.1. Suppose G 1 , . . . , G k and G T be groups of prime order q. Then, a k-multilinear map e : G 1 × . . . × G k −→ G T is a map with the following properties:

(1) Multilinear: For a 1 , . . . , a k ∈ Z * q and arbitrary elements

. . , g k ) can be computed efficiently.

Graded Encoding Schemes

Garg et al. 2 proposed the concept of graded encoding schemes, which is an approximate construction of multilinear maps as follows:

| α ∈ R} be disjoint. Using this assumption, a k-graded encoding scheme GES(R, S) can be defined with the following procedures:

• InstGen(1 λ , k) : The inputs of randomized "instance-generation" procedure are a security parameter λ and also multilinearity parameter k. The corresponding output is (params, P zt ) in which P zt and params are a zero-test parameter and description of the k-graded encoding scheme, respectively. • Samp(params) : The input of randomized "ring sampler" procedure is params. The output of this procedure is a ∈ S (α) 0 that is a "level-zero encoding" (Here α ∈ R is a random and nearly uniform element).

• Enc(params, i, a) : The inputs of (possibly randomized) "encoding" procedure are params, an index i ≤ k and also a "level-zero" encoding

that is a "level-i" encoding for the same element α ∈ R.

Obviously for 1 ≤ i ≤ k, in order to obtain a level-i encoding, we first get a level-0 encoding of α using the ring sampler procedure and then get a level-i encoding of α using the encoding procedure.

• Add(params, i, u 1 , u 2 ) : The inputs of "addition" procedure are params, an index i ≤ k and two level-i encodings

More generally, for a collection of encodings

• Neg(params, i, u 1 ) : The inputs of "negation" procedure are params, an index i ≤ k and a level-i encodings

. This procedure computes Neg(params, i, u 1 ) = −u 1 ∈ S (−α1) i in which −α 1 is negation in the ring R.

• Mul(params, i 1 , u 1 , i 2 , u 2 ) : The inputs of "multiplication" procedure are params, indices

and also a level-i 2 encoding

i2 . The output of this procedure is

in which α 1 · α 2 is multiplication in the ring R and i 1 + i 2 is integer addition.

More generally, for a collection of h encodings u j ∈ S (αj ) ij

• isZero(params, P zt , u) : The inputs of "zero-test" procedure are params, P zt and u. The output of this procedure is 1 if u ∈ S (0) k and 0 otherwise.

• Ext(params, P zt , u) : The inputs of "extraction" procedure are params, P zt and u ∈ S (α)

k , The output of this procedure is s ∈ {0, 1} λ with the following properties: a) For every α ∈ R and two level-k encodings

(1) b) The following distribution over {0, 1} λ is nearly uniform (λ is the security parameter):

which is a k-graded encoding scheme that is parameterized by λ and the multilinearity parameter k ≤ poly(λ). GGH13 is a realization of a k-graded encoding scheme with several changes to the above definition. The important change relevant to our signature scheme is in the extraction procedure: the probability that the output of the extraction procedure of GGH13 is the same for two different level-k encodings of α is not 1. Thus, the property a) of the extraction procedure is replaced by a weaker requirement: a ) Suppose that a ← Samp(params) with a ∈ S (α) 0 . Then, if the (randomized) encoding procedure is run twice on a to obtain two level-k encodings

In this paper, we work with the Definition 2.2, in which the probability that the output of the extraction procedure is the same λ bit string for two different level-k encodings of α is 1. If we want to use the extraction procedure of GGH13, we must consider the negligible probability that Ext(params, P zt , u 1 ) = Ext(params, P zt , u 2 ). Thus, for every α ∈ R, we can use Ext(params, P zt , S (α) k ) to denote this λ bit string.

Remark 2.1. We can assume that a level 1 encoding of 1 ∈ R is published as part of the instancegeneration procedure, namely an element y ∈ S (1) 1 27.

Graded Discrete-Logarithm (GDL) Problem

The analog of discrete logarithm problem in a kgraded encoding scheme GES(R, S) can be defined as the following: consider a level-i encoding

in which 1 ≤ i ≤ k and α ∈ R, it must be hard to output a level-j encoding u j ∈ S (α) j , where j < i. Here, the value i is chosen uniformly at random from the interval [1, k].

More formally, the following experiment can be defined between a challenger C and an adversary B:

Experiment Exp GDL GES (B, λ): (1) Using λ and also the multilinearity parameter k, the challenger C runs (params, P zt ) ← InstGen(1 λ , k) to get description of a k-graded encoding scheme. (2) Now, C firstly runs a ∈ S (α) 0 ← Samp(params) to get a level-zero encoding of a random and nearly uniform element α ∈ R. The challenger C also runs u i ← Enc(params, i, a) to get a level-i encoding u i ∈ S (α) i . Next, C sends (params, P zt , u i ) to the adversary B. (3) Finally, B outputs a value u j . (4) The output is defined to be 1 iff u j ∈ S (α) j and j < i.

The success probability of an adversary B in the experiment Exp GDL GES (B, λ) can be defined as follows.

We say that the GDL problem is hard, if for each polynomial time adversary B running in time ≤ t, Succ GDL GES (B, λ) is a negligible function of λ. In other words,

Note that according to the Remark 2.1, the adversary B can simply get a level-j encoding u j ∈ S (α) j in the above experiment, by running the multiplication procedure

where i < j

Digital Signature Schemes

Here, we give some required preliminaries about digital signature schemes and also security of these schemes. In the remainder of the paper, we fix some notation in order to simplify the explanation: We denote by x $ ← X , if x is chosen randomly from the set X . We also write log for log 2 .

Definition 2.3. Considering a message space M, a digital signature scheme Dss can be defined using the probabilistic polynomial time (PPT) algorithms (Kg, Sign, Vf):

(1) Key generation algorithm Kg(1 n ) takes n as the security parameter and outputs a private signing key sk and a public verification key pk. (2) Signature algorithm Sign(sk, M ) takes as input a message M and also the private signing key sk. Then, if M ∈ M, the algorithm outputs a signature σ for M under sk. (3) Verification algorithm Vf(pk, σ, M ) takes as input the message M , the signature σ and the public verification key pk. The algorithm outputs 1 iff σ is a valid signature on M under pk.

In a Dss = (Kg, Sign, Vf), for every sk, pk which are outputs of Kg(1 n ) and every M ∈ M, the following correctness condition must be satisfied:

EU-CMA Security

We now define "existential unforgeability under adaptive chosen message attacks (EU-CMA)" which is the standard security notion for any digital signature scheme Dss = (Kg, Sign, Vf). EU-CMA security can be defined using the following experiment between a challenger C and an adversary A. In the following, we use the notation Dss(1 n ) for a Dss = (Kg, Sign, Vf) with the security parameter n.

(1) C runs the key generation algorithm Kg(1 n ) to generate a key pair (sk, pk) and sends the public verification key pk to A. (2) Suppose that Sign(sk, ·) be an oracle which for every message M ∈ M, returns the signature Sign(sk, M ). Here, we denote by A Sign(sk,·) the oracle access to Sign(sk, ·) for A. Let also that {(M i , σ i )} q i=1 be the query-answer pairs of Sign(sk, ·). (3) The adversary then outputs (M , σ ). (4) The output of Exp EU-CMA Dss(1 n ) (A) is defined to be 1 iff Vf(M , σ , pk) = 1 and M / ∈ {M i } q i=1 . We define the success probability of A in the experiment Exp EU-CMA Dss(1 n ) (A) as

Now, we give the definition of EU-CMA security as follows.

Definition 2.4. Let n, t, q ∈ N and t, q = Poly(n). We say that a signature scheme Dss = (Kg, Sign, Vf) is EU-CMA-secure, if for all PPT adversaries A Sign(sk,·) running in time at most t and making at most q queries, the maximum success probability InSec EU-CMA (Dss(1 n ); t, q) is a negligible function of n:

Note that for any one-time signature (OTS) scheme, the number of oracle queries of A in the above experiment is restricted to one, i.e. q = 1.

Description of the Generic WOTS

Here, we give description of the generic WOTS scheme. Before defining WOTS, we first recall the definition of function chain. Definition 3.1. Let n ∈ N , D and K be the security parameter, domain and key space, respectively such that the length of every X ∈ D and ck ∈ K be polynomial in n. A function chain C = (I, E) consists of the following PPT algorithms:

• The initialization algorithm I(1 n , λ) takes as input a chain length parameter λ ∈ N and also the security parameter n and outputs a public value ck ∈ K which is called "chain key". • The evaluation algorithm E i,j ck (X) takes as input a public chain key ck, an interval i, j ∈ N, 0 ≤ i < j ≤ λ, and a value X ∈ D which is the ith value of the chain and outputs Y ∈ D, the jth value of the chain.

For every n, λ ∈ N, every ck ∈ K which is output of I(1 n , λ), every i, j, m ∈ N such that 0 ≤ i ≤ j ≤ m ≤ λ and every X ∈ D, it must hold that

We now describe the generic W-OTS using a function chain C = (I, E). This digital signature is parameterized by

• m : the binary message length.

• n : the security parameter.

• w > 1 : the Winternitz parameter. This parameter determines the time-memory trade-off.

• l: the number of elements in a W-OTS signature, public verification key and private signing key, which is computed as

Key Generation Algorithm (Kg(1 n )): On input of the security parameter n, this algorithm chooses the private signing key sk = (sk 1 , . . . , sk l ) $ ← D l . Next, a public chain key ck is obtained using the initialization algorithm I(1 n , λ) of the function chain. Finally, the public verification key pk can be computed as pk = (pk 0 , pk 1 , . . . , pk l ) = (ck, E 0,w−1

Signature Algorithm (Sign(sk, M )): This algorithm takes as input a message M ∈ {0, 1} n and the private signing key sk. Firstly, the base w representation of M is computed, i.e. M = (b 1 , . . . , b l1 ) such that b i ∈ {0, . . . , w − 1}. Next, the checksum

and also its base w representation C = (b l1+1 , . . . , b l ) such that b i ∈ {0, . . . , w − 1}, is computed (Note that C ≤ l 1 (w − 1)). Now, the signature is computed as

Verification Algorithm (Vf(pk, σ, M )): This algorithm takes as input the message M , the signature σ and also the public verification key pk. Firstly, the b i , 1 ≤ i ≤ l are computed as above. Next, if the following comparison holds, the verification algorithm returns true and false otherwise:

WOTS-GES

Here, we propose our digital signature scheme WOTS-GES(k, m) based on a k-graded encoding scheme GES(R, S) with the security parameter λ.

As mentioned before, this signature scheme is a new variant of WOTS scheme. Like other versions of WOTS, WOTS-GES(k, m) is parameterized by

• m : the binary message length.

• w > 1 : the Winternitz parameter. Here we suppose that w − 1 is equal to the multilinearity parameter k of the k-graded encoding scheme, i.e. w − 1 = k.

• l: This parameter is calculated using the parameters m and w, as described in the previous section.

Please note that according to the Remark 2.1, we can consider that there is a level 1 encoding of 1, i.e. 1 1 ∈ S (1)

1 . It is assumed that in the pre-computation phase, the encoding procedure Enc(params, i, 1 1 ) is run to obtain the level-i encoding 1 i ∈ S

(1) i , where 2 ≤ i ≤ k.

Key Generation Algorithm (Kg(GES(R, S))):

This algorithm takes as input the description of the k-graded encoding scheme GES(R, S). Then, the randomized ring sampler procedure Samp(params) is run to obtain l level-zero encodings a j ∈ S (αj ) 0 , where α 1 , . . . , α l ∈ R are random and nearly uniform elements and 1 ≤ j ≤ l. The private signing key sk = (a 1 , . . . , a l ) consists of this level-zero encodings.

Next for 1 ≤ j ≤ l, the key generation algorithm runs the encoding procedure Enc(params, k, a j ) to get l level-k encodings u jk ∈ S (αj ) k . Finally, the extraction procedure is run to obtain pk j = Ext(params, P zt , u jk ). Now, the public verification key pk is defined as pk = (pk 1 , . . . , pk l ). The key generation algorithm is shown in Figure 1.

u lk a l sk pk bj . Now, the signature σ is defined as

The signature algorithm is shown in Figure 2. Let B = M C, then we can conclude from the checksum that if M = M be any other message, the corresponding B consists of at least one b j < b j , where 1 ≤ j ≤ l. Figure 2. A schematic representation of signature algorithm Verification Algorithm (Vf(pk, σ, M )): This algorithm which is shown in Figure 3, takes as input the message M , the signature σ and also the public verification key pk. In this algorithm for 1 ≤ j ≤ l:

(1) Firstly, the b j s are computed as described above. (2) Then, the verification algorithm runs the multiplication procedure Mul(params, b j , u jbj , k − b j , 1 k−bj ) to compute the level-k encoding u jk ∈ S (αj ) k . (3) Finally, the extraction procedure is run to obtain pk j = Ext(params, P zt , u jk ). Now, if the following comparison holds, the verification algorithm returns true and false otherwise:

Security of WOTS-GES

Here, we prove the security of WOTS-GES. We explain how an adversary for WOTS-GES can be used to construct an adversary to solve the GDL problem. More formally, the GDL problem is reduced to the EU-CMA security of WOTS-GES. Lemma 1. Let k, m ∈ N. Then, if there is any PPT adversary A who can break the proposed digital signature scheme WOTS-GES(k, m), then there exists a PPT adversary B that is a solver for the GDL problem such that Figure 3. A schematic representation of verification algorithm Proof. Consider a PPT adversary A which acts according to the Experiment Exp EU-CMA Dss(1 n ) (A) against the security of WOTS-GES(k, m), such that his success probability Succ EU-CMA Dss(1 n ) (A) = ε A is non-negligible. In the rest of the proof, we will define an adversary B which acts according to the Experiment Exp GDL GES (B, λ) to solve the GDL problem in polynomial time with a non-negligible success probability Succ GDL GES (B, λ) = ε B and uses A as a sub-routine (Note that we have n = λ):

(1) Based on λ and the multilinearity parameter k, the challenger of the Experiment Exp GDL GES (B, λ) (that is C) runs (params, P zt ) ← InstGen(1 λ , k) to get an explanation of a k-graded encoding scheme GES(R, S). Now, the challenger C firstly runs a ← Samp(params) to obtain a level-zero encoding a ∈ S (α) 0 , where α ∈ R is a random and nearly uniform element. Then, C runs u i ← Enc(params, i, a) to get a level-i encoding u i ∈ S (α) i . Next, C sends (params, P zt , u i ) to the adversary B.

(2) Now, B is used as a challenger for A in the Experiment Exp EU-CMA Dss(1 n ) (A). So, B executes the WOTS-GES key generation algorithm Kg(GES(R, S)) to obtain a private signing key sk = (a 1 , . . . , a l ), where a j ∈ S (αj ) 0 are l level-zero encodings and α 1 , . . . , α l ∈ R are random and nearly uniform elements and also a public verification key pk = (pk 1 , . . . , pk l ). Suppose that (M, σ) be the query-answer pair of Sign(sk, ·) in the Step 2 of the experiment Exp k . Afterwards, B runs the extraction procedure to compute pk γ = Ext(params, P zt , u k ) Consequently, the manipulated public verification key pk is obtained as pk = (pk 1 , . . . , pk γ , . . . , pk l ). Note that the private signing key is also changed as sk = (a 1 , . . . , a γ , . . . , a l ), where a γ is unknown. Now, B sends the manipulated public verification key pk to A (the start of the Experiment Exp EU-CMA Dss(1 n ) (A)). (B, λ)). In the following, the success probability of the adversary B is calculated: As we saw in Step 2c, B can only answer the A's query M , if i ≤ b γ . To make computation of the success probability easier, we only consider a certain success case, i.e. i = b γ . As i was selected randomly with uniform distribution from the interval [1, k], the case happens with probability k −1 .

We also pointed out that the corresponding B of the successful forgery (M , σ ) must contain at least one b γ < b γ , where 1 ≤ γ ≤ l. This happens for γ = γ with probability l −1 . Thus we have b γ < b γ . Consequently, we conclude that b γ < i with probability (kl) −1 and therefore the condition in Step 2d is fulfilled. Hence, the success probability of the adversary A can be bounded as follows:

Note that because of the Equation 1 of the extraction procedure, changing the public verification key generation method to place our challenge, does not change the public verification key. More precisely, if we choose either the key generation algorithm of WOTS-GES(k, m) or the method which is used in the proof to produce public verification key, we obtain an equal value for this key. Thus, the proof is completed.

We now conclude the following theorem using Lemma 1: Theorem 1. Suppose that k, m ∈ N. Then, we can bound the insecurity of WOTS-GES against an EU-CMA attack by

with t = t + 5l.

Proof. Firstly note that the Equation 7 can be simply derived from Equation 6 and also from Definitions 2 and 5. The time t = t + 5l is also the maximum runtime required by the adversary A (which behaves according to the Definition 2.4) plus the time required to execute the three algorithms of WOTS-GES once (follow the proof of Lemma 1).

Instantiation using GGH13

To use WOTS-GES, graded encoding scheme GES(R, S) must be instantiated. In this section, we discuss how GES(R, S) can be instantiated using GGH13.

The graded encoding scheme GGH13 is parameterized by λ and also multilinearity parameter k ≤ poly(λ). Using these parameters, consider the cyclotomic ring R = Z <X n +1> , in which n = ˜ O(kλ 2 ) is a power of 2. Also, let that the modulus q = 2 kλ defines the quotient ring R q = R qR . Finally, consider the quotient ring QR = R I in which I =< g > is a principal prime ideal and g is a secret short vector drawn from the discrete Gaussian distribution g ← D Z n ,σ in which σ = ˜ O( √ n). There is also another secret vector z ∈ R q , that selected uniformly at random.

In the graded encoding scheme GGH13, the quotient ring QR = R I plays the role of ring R in Definition 2.2. More precisely, elements of QR are what are encoded.

A level-zero encoding of an arbitrary cost r + I ∈ QR is a short vector of r + I. It can be proved that Step WOTS schemes 162023242526 proposed scheme Public verification key generation

the size of level-zero encodings is bounded by λn 2 (with high probability) 27. On the other hand, the private signing key sk = (a 1 , . . . , a l ) of the signature scheme WOTS-GES consists of l level-zero encodings. Consequently, the size of private signing key sk is bounded by lλn 2 .

Also, a level-i encoding of a cost r +I ∈ QR, where 1 ≤ i ≤ k, is a vector of the form c z i ∈ R q in which c ∈ r + I and c< q 1 8 . Thus, the size of c z i ∈ R q is bounded by qn. On the other hand, we know that the signature σ = (σ 1 , . . . , σ l ) of a given message M using WOTS-GES, consists of l level-i encodings, where 0 ≤ i ≤ k. Therefore, signature σ consists of l level-i encodings which size of each is at most either λn 2 or qn.

Finally, as described in Definition 2.2, the output of the extraction procedure is a λ bit string. On the other hand, the public verification key pk = (pk 1 , . . . , pk l ) is made up of l extraction procedure outputs. Thus, the size of the public verification key is lλ bits.

In 28, GGHLite, an efficient version of GGH13 is presented in which the size of some parameters has been improved. Thus, instantiating the used graded encoding scheme of WOTS-GES using GGHLite can improve the efficiency of WOTS-GES.

Conclusion

Here, we provide a comparison for the number of operations required by the key generation, signature and verification algorithms of WOTS-GES scheme and other WOTS scheme variants in the literature 162023242526. We have summarized the results in Table 1.

In this table, we have assumed that the Winternitz parameter minus one is equal to the multilinearity parameter k of the used k-graded encoding scheme, i.e. w − 1 = k. We have also used the following notations to analyze the complexities of the proposed scheme:

• T fc : The time required to execute one iteration of the used function chain.

• T enc : The time required to execute the encoding procedure of the used k-graded encoding scheme.

• T ext : The time required to execute the extraction procedure of the used k-graded encoding scheme.

• T mul : The time required to execute the multiplication procedure of the used k-graded encoding scheme.

From the comparison in the table, we can see that the number of operations required by the three algorithms of WOTS-GES is less than that of other WOTS scheme variants. In 29, the first practical implementation of graded encoding schemes is presented in which the efficiency of GGHLite has also been improved. Using our results along with the practical implementations of graded encoding schemes, we can obtain an efficient one-time digital signature scheme for various applications 131415.

A schematic representation of key generation algo- rithmSignature Algorithm (Sign(sk, M )): This algo- rithm takes as input a message M ∈ {0, 1} n and also the private signing key sk = (a 1 , . . . , a l ). Firstly, the base w representation of M is computed, i.e. M = (b 1 , . . . , b l1 ) such that b i ∈ {0, . . . , w − 1}. Next, the checksumC = l1 i=1 (w − 1 − b i )and also its base w representation C = (b l1+1 , . . . , b l ) such that b i ∈ {0, . . . , w − 1}, is computed. After- wards for 1 ≤ j ≤ l, the signature algorithm runs the encoding procedure Enc(params, b j , a j ) to get the level-b j encodings u jbj ∈ S (αj )

EU-CMA Dss(1 n ) (A) and B = M C = (b 1 , . . . , b l ). Let also that (M , σ ) be the output of the ad- versary A in the Step 3 of this experiment and B = M C = (b 1 , . . . , b l ). Because of the checksum, the corresponding B of the suc- cessful forgery (M , σ ) must contain at least one b γ < b γ , where 1 ≤ γ ≤ l. More precisely, the γ-th components of σ = (σ 1 , . . . , σ l ) and σ = (σ 1 , . . . , σ l ) i.e. σ γ and σ γ are a level-b γ encoding σ γ ∈ S (αγ ) bγ and a level-b γ encoding σ γ ∈ S (αγ ) b γ , respectively, where 1 ≤ γ ≤ l. In the following, the adversary B tries to conjec- ture the location of σ γ and place the level-i encoding u i ∈ S (α) i there. Hence, he will re- ply the signature query and finally extract a level-j encoding u j ∈ S (α) j using the successful forgery σ , where 0 ≤ j < i: (a) The adversary B selects the position of a component of the private signing key sk = (a 1 , . . . , a l ) choosing the index 1 ≤ γ ≤ l uniformly at random. (b) B considers the level-i encoding u i ∈ S (α) i challenge as the level-i encoding of an unknown level-zero encoding a γ = a. Next, B runs the multiplication procedure Mul(params, i, u i , k − i, 1 k−i ) to compute the level-k encoding u k ∈ S (α)

(c) Note that B only knows the level-j en- codings u j ∈ S (α) j , where i ≤ j ≤ k as he can run the multiplication procedure Mul(params, i, u i , j − i, 1 j −i ) to compute the level-j encoding u j ∈ S (α) j . So, B can only answer the A's query M , if i ≤ b γ . (d) Also, the successful forgery (M , σ ) is only helpful if b γ < i. In this case, the adversary B announces the level-b γ en- coding u b γ ∈ S (α) b γ as its output (Step 3 of the Experiment Exp GDL GES

References

1. Jean-, Aumasson Philippe, Endignoux Guillaume. Improving stateless hash-based signatures. Cryptographers' Track at the RSA Conference. 2018;219-242.
2. Ananth Prabhanjan, Jain Aayush, Sahai Amit. Robust transforming combiners from indistinguishability obfuscation to functional encryption. Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2017;91-121.
3. Aumasson Jean-Philippe, Daniel J, Bernstein Christoph, Dobraunig Maria, Eichlseder Scott, Fluhrer Stefan-Lukas, Gazdag Andreas, Hülsing Panos, Kampanakis Stefan, Kölbl Tanja, Lange 2019.
4. Lin Huijia, Tessaro Stefano. Indistinguishability obfuscation from trilinear maps and blockwise local prgs. Annual International Cryptology Conference. 2017;630-660.
5. Malkin Tal, Micciancio Daniele, Miner Sara. Efficient generic forward-secure signatures with an unbounded number of time periods. International Conference on the Theory and Applications of Cryptographic Techniques. 2002;400-417.
6. Hevia Alejandro, Micciancio Daniele. The provable security of graph-based one-time signatures and extensions to algebraic signature schemes. International Conference on the Theory and Application of Cryptology and Information Security. 2002;379-396.
7. Boneh Dan, Silverberg Alice. Applications of multilinear forms to cryptography. Contemporary Mathematics. 2003; 324:71-90.
8. Garg Sanjam, Gentry Craig, Halevi Shai. Candidate multilinear maps from ideal lattices. Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2013;1-17.
9. Ralph C Merkle A certified digital signature. Conference on the Theory and Application of Cryptology. 1989;218-238.
10. Hülsing Andreas, Rausch Lea, Buchmann Johannes. Optimal parameters for xmss mt. International Conference on Availability, Reliability, and Security. 2013;194-208.
11. ¨ Ozgür Dagdelen David, Galindo Pascal, Véron Extended security arguments for signature schemes. Designs, Codes and Cryptography. 2016; 78:441-461.
12. Hülsing Andreas, Busold Christoph, Buchmann Johannes. Forward secure signatures on smart cards. International Conference on Selected Areas in Cryptography. 2012;66-80.
13. Garg Sanjam. Candidate Multilinear Maps. University of California Los Angeles; 2013.
14. Lamport Leslie. Constructing digital signatures from a one-way function. 1979.
15. Hauser Ralf, Przygienda Tony, Tsudik Gene. Reducing the cost of security in link-state routing. Proceedings of SNDSS'97: Internet Society 1997 Symposium on Network and Distributed System Security. 1997;93-99.
16. Garg Sanjam, Gentry Craig, Halevi Shai, Wichs Daniel. On the implausibility of differinginputs obfuscation and extractable witness encryption with auxiliary input. Algorithmica. 2017; 79(4):1353-1373.
17. Hohenberger Susan, Sahai Amit, Waters Brent. Full domain hash from (leveled) multilinear maps and identity-based aggregate signatures. Annual Cryptology Conference. 2013;494-512.
18. Yu Jia, Xia Hui, Zhao Huawei, Hao Rong, Fu Zhangjie, Cheng Xiangguo. Forwardsecure identity-based signature scheme in untrusted update environments. Wireless Personal Communications. 2016; 86(3):1467-1491.
19. Buchmann Johannes, Dahmen Erik, Ereth Sarah, Hülsing Andreas, Rückert Markus. On the security of the winternitz one-time signature scheme. International conference on cryptology in Africa. 2011;363-378.
20. Garg Sanjam, Gentry Craig, Halevi Shai. Mariana Raykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. SIAM Journal on Computing. 2016; 45(3):882-929.
21. Hülsing Andreas, Rijneveld Joost, Song Fang. Mitigating multi-target attacks in hashbased signatures. Public-Key Cryptography-PKC 2016. 2016;387-416.
22. Massoud Hadian Dehkordi Hossein, Oraei How to construct a verifiable multi-secret sharing scheme based on graded encoding schemes. IET Information Security. 2019; 13(4):343-351.
23. Martin R Albrecht Catalin, Cocis Fabien, Laguillaumie Adeline, Langlois Implementing candidate graded encoding schemes from ideal lattices. International Conference on the Theory and Application of Cryptology and Information Security. 2015;752-775.
24. Li Daofeng, Chen Haiqiang, Zhong Cheng, Li Taoshen, Wang Feng. A new self-certified signature scheme based on ntrus ing for smart mobile communications. Wireless Personal Communications. 2017; 96(3):4263-4278.
25. Buchmann Johannes, Dahmen Erik, Hülsing Andreas. Xmss-a practical forward secure signature scheme based on minimal security assumptions. International Workshop on PostQuantum Cryptography. 2011;117-129.
26. Langlois Adeline, Stehlé Damien, Steinfeld Ron. Gghlite: More efficient multilinear maps from ideal lattices. Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2014;239-256.
27. Dods Chris, Nigel P, Smart Martijn, Stam Hash based digital signature schemes. IMA International Conference on Cryptography and Coding. 2005;96-115.
28. Hülsing Andreas. W-ots+-shorter signatures for hash-based signature schemes. International Conference on Cryptology in Africa. 2013;173-188.
29. Daniel J, Bernstein Daira, Hopwood Andreas, Hülsing Tanja, Lange Ruben, Niederhagen Louiza, Papachristodoulou Michael, Schneider Peter, Schwabe Zooko, Wilcox -O&apos;, Hearn Sphincs: practical stateless hash-based signatures. Annual international conference on the theory and applications of cryptographic techniques. 2015;368-397.